I was mucking around with some numerical analysis code the other day and came across this function:

```
bool sum_will_overflow (int x, int y)
{
// RETURNS: true if the sum overflows, false otherwise
int sum = x + y;
if (sum - x == y) && (sum - y == x)
return false;
else
return true;
}
```

This function is essentially trying to check for the condition when the addition of integers leads to an overflow. For e.g. if you represent an integer using 4 bits, then the two's complement representation of 6 and 7 will be equal to 0110 and 0111 respectively. But if you add them together, the resulting sum will be 1101 which in two's complement is equal to 1 * -8 + 1 * 4 + 0 * 2 + 1 * 1 = -3. Thus the addition of two positive numbers has led to a negative number!

So does the above function correctly figure out when a number will overflow? At first glance, everything looks good. If the sum overflows, it will never be equal to x + y. Similarly, if the sum does not overflow, it will be equal to x + y. For a 4 bit integer representation, one can show that the sum will be represented as

` sum = x + y if (-8 <= x + y <= 7)`

= x + y + 16 if -8 > x + y

= x + y - 16 if x + y > 7

For e.g. 6 + 7 = 13 - 16 = -3 which matches our result above. Now armed with this equation, let us check the logic of the function. Remember that 16 is 10000 in binary. While adding and subtracting 16 from a 4 bit number, only the first 4 bits of 16 will be considered i.e. 0000. So for all practical purposes, 16 behaves as 0 in a 4 bit world. Now let us see what happens when we subtract x from the sum

` sum - x = x + y - x if -8 <= x + y < 7`

Thus the function "sum_will_overflow" is essentially a contradiction and will return false always. Let us verify with our earlier example:

= x + y + 16 - x if -8 > x + y

= x + y - 16 - x if x + y > 7

= y if -8 <= x, y <= 7 ` sum(6, 7) - 6 = -3 - 6 + 16 = 7`

sum(6, 7) - 7 = -3 - 7 + 16 = 6

Here is a nice example of a simple function that works quite counter-intuitively. The correct way to check for overflow is to check whether the sign of the sum differs from the sign of the individual addends.

```
bool sum_will_overflow_correct (int x, int y)
{
bool retval = false;
int sum = x + y;
if (x > 0 && y > 0)
{
if sum < 0
retval = true;
}
else if (x < 0 && y < 0)
{
if sum > 0
retval = true;
}
return retval;
}
```

No wonder, life is tough for us programmers!

For the ubergeek, the function can be succinctly expressed as:

return (x < 0 == y < 0)&&(sum > 0 == x < 0);

Posted by: Phaedurs | 07/02/2012 at 10:09 AM