Test whether sum of two integers might overflow

Question

From C traps and pitfalls

If a and b are two integer variables, 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?

possible duplicate of [Best way to detect integer overflow in C/C++](http://stackoverflow.com/questions/199333/best-way-to-detect-integer-overflow-in-c-c) — pmr, May 12 '13 at 16:08

score 19 · Accepted Answer · answered Aug 07 '11 at 06:00

19

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.

answered Aug 07 '11 at 06:00

R.. GitHub STOP HELPING ICE

208,859
35
376
711

Don't you have to special case when `a` is `INT_MIN` and `-INT_MIN` is an overflow? – Jens Gustedt Aug 07 '11 at 07:02
@Jens: Why? `a` is never negated. You're testing to see if `a+b` will overflow. If `a` is positive, `INT_MAX-a` cannot overflow. If `a` is negative or zero, `INT_MIN-a` cannot overflow. – R.. GitHub STOP HELPING ICE Aug 07 '11 at 07:09
right, somehow I always thought of `a-b` as `a + (-b)` but which in this case, isn't. – Jens Gustedt Aug 07 '11 at 07:36
`*Nod*`, if that were the case though then you could never subtract `INT_MAX` from anything. :-) – R.. GitHub STOP HELPING ICE Aug 07 '11 at 07:45

sorin · Answer 2 · 2013-07-25T07:59:04.637

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.

score 2 · Answer 3 · answered Aug 07 '11 at 04:56

2

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.

answered Aug 07 '11 at 04:56

Blender

289,723
53
439
496

1

BTW, that's assuming your integers are unsigned. Read the Wikipedia article (yes, one exists...) on them: http://en.wikipedia.org/wiki/Integer_overflow – Blender Aug 07 '11 at 05:00
1

If your integers are unsigned, the sum is never "negative"... This is not a valid test. – R.. GitHub STOP HELPING ICE Aug 07 '11 at 05:55

dan · Answer 4 · 2013-02-02T07:23:23.630

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);
}

score 0 · Answer 5 · answered May 28 '14 at 08:50

0

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.

answered May 28 '14 at 08:50

Dasharath Singh Shekhwat

1

1

Are you sure this is correct? It gives 1 for sum of 1 and 1: `(1^1) + (1&1) == 1` – sukhmel Aug 27 '14 at 18:26

score 0 · Answer 6 · answered Jun 12 '15 at 11:57

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.

score 0 · Answer 7 · answered Aug 07 '11 at 06:08

0

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).

answered Aug 07 '11 at 06:08

mpontillo

13,559
7
62
90

That may sometimes work in practice, but the behavior of signed overflow is undefined. Even if the hardware has the typical 2's-complement behavior, an optimizing compiler is likely to *assume* that no overflow occurs (because if it does, any possible behavior is valid anyway). For example, the expression `(a+23<23)` could easily be optimized to just `1`. – Keith Thompson Aug 07 '11 at 06:15

Test whether sum of two integers might overflow

7 Answers7