Checking overflow in C

Contrary to popular belief, an int overflow results in undefined behavior. This means that once a + b overflows, it doesn't make sense to use this value (or do anything else, for that matter). The wrap-around is just what most machines happen to do in case of overflow, but they might as well explode.

To check whether an int overflow will occur when adding two non-negative integers a and b, you can do the following:

if (INT_MAX - b < a) {
        /* int overflow when evaluating a+b */
}

This is due to the fact that if a + b > INT_MAX, then INT_MAX - b < a, but INT_MAX - b can not overflow.

You will have to pay special attention to the case where b is negative, which is left as an exercise for the reader ;)

Regarding your actual goal: 1024-bit numbers suffer from exactly the same overall issues as 32-bit numbers. It might be more promising to choose a completely different approach, e.g. representing numbers as, say, linked lists of digits, using a very large base B. Usually, B is chosen such that B = sqrt(INT_MAX), so multiplication of digits doesn't overflow the machine's int type.

This way, you can represent arbitrarily large numbers, where "arbitrary" means "only limited by the amount of main memory available".

If you're adding unsigned numbers then you can do this

c = a+b;
if (c<a) {
  // you'll get here if and only if overflow has occurred
}

and you may even find that your compiler is clever enough to implement it by checking the overflow or carry flag instead of doing an extra comparison. For instance, I just fed this to gcc -O3 -S:

unsigned int foo() {
  unsigned int x=g(), y=h();
  unsigned int z = x+y;
  return z<0 ? 0 : z;
}

and got this for the key bit of the code:

movl  $0,   %edx
addl  %ebx, %eax
cmovb %edx, %eax

where you'll notice there's no extra comparison instruction.

If you are working with unisigned numbers, then if a <= UINT_MAX, b <= UINT_MAX, and a + b >= UINT_MAX, then c = (a + b) % UINT_MAX will always be smaller than a and b. And this is the only case where this can happen.

So you can detect overflow this way.

int add_return_overflow(unsigned int a, unsigned int b, unsigned int* c) {
    *c = a + b;
    return *c < a && *c < b;
}

Information which maybe useful in this subject :

1. Secure Coding in C and C++
2. IntSafe library

You can base a solution on a particular feature of the C language. According to the specification, when you add two unsigned ints, "the result value is congruent to the modulo 2^n of the true result" ("C - A reference manual" by Harbison and Steele). This means you can use some simple arithmetic checks to detect overflow:

#include <stdio.h>

int main() {
    unsigned int a, b, c;
    char *overflow;

    a = (unsigned int)-1;
    for (b = 0; b < 3; b++) {
        c = a + b;
        overflow = (a < b) ? "yes" : "no";
        printf("%u + %u = %u, %s overflow\n", a, b, c, overflow);
    }

    return 0;
}

Just xor MSB of both operands and result. Result of this operation is overflow flag.

But that will not show you if result is correct or not. (it might be correct result even whit overflow) for instance 3 + (-1) is 2 whit overflow.

In order to figure that using signed arithmetic you need to check if both operdas were same sign (xor of MSB).

Once you add 1 to INT_MAX, you end up getting INT_MIN (i.e. overflow).
In C, there's no reliable way to test for overflow, because all 32 bytes are used to represent the integer (and not a state flag). You can only test to see if the number you get will be within a valid range, as in your link.

You'll get answers suggesting that you can test if (c < a), however note that you could overflow the value of a and/or b to the point where their addition forms a number greater than a (but still overflown)