Test whether sum of two integers might overflow

From C traps and pitfalls

If a and b are two integer v开发者_如何学Cariables, known to be non-negative then to test whether a+b might overflow use:

     if ((int) ((unsigned) a + (unsigned) b) < 0 )
        complain();

I didn't get that how comparing the sum of both integers with zero will let you know that there is an overflow?

The code you saw for testing for overflow is just bogus.

For signed integers, you must test like this:

if (a^b < 0) overflow=0; /* opposite signs can't overflow */
else if (a>0) overflow=(b>INT_MAX-a);
else overflow=(b<INT_MIN-a);

Note that the cases can be simplified a lot if one of the two numbers is a constant.

For unsigned integers, you can test like this:

overflow = (a+b<a);

This is possible because unsigned arithmetic is defined to wrap, unlike signed arithmetic which invokes undefined behavior on overflow.

When an overflow occurs, the sum exceeds some range (let's say this one):

-4,294,967,295 < sum < 4,294,967,295

So when the sum overflows, it wraps around and goes back to the beginning:

4,294,967,295 + 1 = -4,294,967,295

If the sum is negative and you know the the two numbers are positive, then the sum overflowed.

If a and b are known to be non negative integers, the sequence (int) ((unsigned) a + (unsigned) b) will return indeed a negative number on overflow.

Lets assume a 4 bit (max positive integer is 7 and max unsigned integer is 15) system with the following values:

a = 6

b = 4

a + b = 10 (overflow if performed with integers)

While if we do the addition using the unsigned conversion, we will have:

int((unsigned)a + (unsigned)b) = (int) ((unsigned)(10)) = -6

To understand why, we can quickly check the binary addition:

a = 0110 ; b = 0100 - first bit is the sign bit for signed int.

0110 +
0100
------
1010

For unsigned int, 1010 = 10. While the same representation in signed int means -6.

So the result of the operation is indeed < 0.

If the integers are unsigned and you're assuming IA32, you can do some inline assembly to check the value of the CF flag. The asm can be trimmed a bit, I know.

int of(unsigned int a, unsigned int b)
{
        unsigned int c;

        __asm__("addl %1,%2\n"
                "pushfl \n"
                "popl %%edx\n"
                "movl %%edx,%0\n"
                :"=r"(c)
                :"r"(a), "r"(b));

        return(c&1);
}

There are some good explanations on this page.

Here's the simple way from that page that I like:

Do the addition normally, then check the result (e.g. if (a+23<23) overflow).

As we know that Addition of 2 Numbers might be overflow. So for that we can use following way to add the two numbers.

Adder Concept

Suppose we have 2 numbers "a" AND "b"

(a^b)+(a&b); this equation will give the correct result.. And this is patented by the Samsung.

assuming twos compliment representation and 8 bit integers, the most significant bit has sign (1 for negative and 0 for positive), since we know the integers are non negative, it means most significant bit is 0 for both integers. Now if adding the unsigned representation of these numbers result in a 1 in most significant bit then that mean the addition has overflowed, and to check whether an unsigned integer has a 1 in most significant bit is to check if it is more than the range of signed integer, or you can convert it to signed integer which will be negative (because the most significant bit is 1)

example 8 bit signed integers (range -128 to 127):

twos compliment of 127 = 0111 1111
twos complement of 1   = 0000 0001

unsigned 127           = 0111 1111
unsigned 1             = 0000 0001
unsigned sum           = 1000 0000

sum is 128, which is not a overflow for unsigned integer but is a overflow for signed integer, the most significant bit gives it away.