I think that particular C FAQ needs fixing or
amplification; it certainly does not agree with
what I, and many others---even Wikipedia---understand
as "integer overflow".
I summarize with details I have used in lectures for
the past 40 years (less the last 5 after I turned 80):
Old wise man of computing! What you are saying is valid, but you have to
distinguish the abstract language-level situation of integer overflow from the
one that happens in CPU's.
For most modern CPU's, if integers a and b are
restricted to binary forms with k bits, then
the carry bit is that in the (k+1) position
should a,b and c=a+b be expressed with k+1 bits,
even though most compilers, particularly C
and Fortran, may cause storage and processing
the result of c=a+b in k-bit form---in effect,
take the result mod 2^k.
Yes, this is all very well and true. On most C compilers for mainstream
architectures, integer overflow has actual semantics like this: it wraps around
and its effect is reversible.
But, the fact is that in the programming language, the behavior is undefined,
and integer overflow is simply any situation where some operation would compute
a signed integral value that falls outside of the domain of its type (or its
default promoted type). For example, adding two ints such that the result isn't
in the range INT_MIN through INT_MAX.
So as an engineer, you have to gather all these facts in order to make a
decision whether you are going to write code that relies on the processor
semantics of overflow, or whether you will avoid the overflow.
As an engineer, you have to consider the tradeoffs. Here is one:
If you depend on the machine semantics of overflow, then you cannot turn on
overflow detection as a global code generation option for the entire project.
This is too bad, because it could help you catch situations where overflow is
unintended.
You may still be able to do this on a file by file basis, depending on your
compiler. C has no way of expressing code generation requests at the level of
functions or expressions. Implementations may provide that as extensions, but
typically the best you can do is control this at the invocation of a compiler
for each translation unit.
This thread started out with someone asking how to detect overflow. Presumably,
he regards overflow as an error. It would be a grave mistake to implement this
error checking in such a way that it requires you to disable any error checking
that the compiler provides!
If check_overflow is implemented in such a way that it triggers overflow, then
hopefully it will be possible to turn off the overflow checks just for the
translation unit that defines the check_oveflow, and enable it everywhere else.
That's still an extra burden for the future maintainers who may want to port
the program. Ideally they should just be able to turn on any option for
catching some undefined behavior, globally for the entire codebase, and not
have to deal with exceptions that arise.
And what if overflow trapping is available as flag in the CPU? Then if you want
that on a per-module basis, the generated code has to save, set and restore
that flag everywhere. You need that in the calling conventions, i.e. the rule
that functions must not clobber the overflow-generation flag, etc.
Can anyone provide a C version simpler than
((a<0)==(b<0)) ? (a<0) : (a+b>=0);
But what does that have to do with overflow? Carry isn't overflow; at least
not for the signed types that you are working with.
Let a = b = -1. The ternary antecent is true, and hence (a < 0) is returned,
which is 1, so there is carry. But -1 + -1 is just -2. This addition does not
overflow.
The carry you are talking about here is the the special unsigned signed carry
(or borrow) for multi-precision addition (or subtraction) operations, where the
-1 + -1 is regarded as the addition of two large unsigned numbers, and not the
addition of one less than zero to itself!
Why on earth would you use signed numbers in C, to detect the overflow in the
the corresponding unsigned arithmetic???
You're relying on the signed addition a + b to behave like unsigned addition,
which may be true in two's complement systems, where the compiler hasn't
generated code to implement overflow traps.
But it takes so little effort to just use the unsigned types which are provided
in the C language for the purpose of making this kind of computation portable!
If U is unsigned int, then ~U gives you a portable ones-complement, and ~U+1 a
portable twos complement, etc. Your carry check can be implemented using bit
tests.
The MC68000 architecture manual defines ``overflow'' (V condition code) as
``Set if there was an arithmetic overflow. This implies that the result is not
representable in the operand size.'' See? A CPU architecture document still has
the concept of a result not fitting into an operand!
The V condition code is computed like this:
V = Sm^Dm^Rm' v Sm'^Dm'^Rm
Where Sm, Dm and Rm refer to the source, destination and result operands'
most significant bits, ^ and v are AND and OR, and ' is complement (my
notation, the manual uses a bar over the operand). So according to this we can
do it like:
// a + b are unsigned types; MSB_MASK and MSB_SHIFT defined sanely
// depending on the size of the data you are representing within
// the unsigned type.
// overflow: 1 or 0
(((a & b & ~(a+b)) | (~a & ~b & (a+b))) & MSB_MASK) >> MSB_SHIFT;
There is a chance that this even runs faster than some simpler, but less
portable, expression involving the ternary operator, because it doesn't involve
any conditional execution. I.e. the source doesn't appear simpler, but there
isn't necessary a performance penalty.
Also since no ternary operator is used, in situation where a and b are
constants, this becomes a C constant expression. Constant expressions cannot
contain the ternary operator.
So the above gives us a way to do an overflow check for signed addition, which
is emulated inside unsigned types. We can also code the unsigned overflow,
a.k.a. carry:
C = Sm^Dm v Rm'^Dm v Sm^Rm' (MC68K architecture manual)
i.e.
(((a & b) | (a & ~(a+b)) | (b & ~(a+b))) ^ MSB_MASK) >> MSB_SHIFT
A more common way in C to test whether unsigned addition overflows is to see
whether the result fails to be greater than either operand.
// a and b are some unsigned type that doesn't promote to a signed one
if (a + b > a && a + b > b) {
// didn't wrap
}
But this is unnecessarily strong. This weaker test is sufficient:
if (a + b > a) {
// didn't wrap
}
If b is large enough such that the addition wraps, there is no way it can wrap
so far that the result is greater than a. The largest possible value of b can
only wrap the result as far as a - 1. All other values of b land the result in
the range 0 through a - 2, or else they do not overflow.
To get the carry bit as a 0 or 1 value is simple:
// a and b are unsigned types that do not promote to a signed type
unsigned carry = (a + b < a);
Contrast this with your way of doing this within the signed types:
// a and b are (obviously) signed types
unsigned carry = ((a<0)==(b<0)) ? (a<0) : (a+b>=0);
This is more complicated, less portable and hostile toward maintainers who want
to generate code that traps overflow.
for getting the carry bit when a,b,c are
viewed as least-absolute residues of 2^32?
But from a C programming point of view, your use of the signed type is
inconsistent with the regard for these quantities as being positive residues of
a Mersenne number.
The unsigned types in C are exactly for this type of purpose.
