CODEWITHSUNDEEP
c32-bitinteger-overflowinteger-arithmetic
ShadyBears
ShadyBears

Reputation: 4185

Need help understanding integer arithmetic function

Would someone please be kind enough to explain this function for me thank you!

int overflow(int x, int y)
{
   int result, non_overflow, overflow, result_sign, mask;

   result = x + y;
   result_sign = result >> 31;  //Need help starting from here... I know
                                //it is shifting 31 bits... but why??
   non_overflow = ((x ^ y) | ~(y ^ result)) >> 31;
   overflow = ~non_overflow;

   mask = overflow << 31;

   return (non_overflow & result) | (overflow & (result_sign ^ mask));  
}

Upvotes: 3

Views: 161

Answers (1)

Potatoswatter
Potatoswatter

Reputation: 137900

It's calculating an integral overflow "flag" for the addition operation, which represents whether the magnitude of the result was less than INT_MIN or greater than INT_MAX. It assumes that int is 32 bits, two's complement, and that a right shift of a signed number is an "arithmetic" shift which replicates the high-order bit — none safe assumptions.

If the sign of x and y is the same, but the sign of the result is the opposite, then the result overflowed. That's all it's computing. There's no need to be so complicated.

Assuming that addition doesn't generate integral exceptions and there is no wonky parity bit, this expression will work by manipulating the sign bit in the same spirit as the original code:

( x ^ y ) < 0 && ( x ^ result ) < 0 /* (A^B)<0 iff A and B have opposite sign */

If we want to be finicky about relying on well-defined behavior, performing x + y is illegal if the result may overflow. A machine conforming to the C standard is allowed to terminate the program at such an overflow (or self-destruct, etc), so we need to avoid doing it in the first place.

The tests we want to perform are

x + y > INT_MAX
x + y < INT_MIN

There's no safe operation between x and y directly. We have to move one to the other side of the equation, which means reversing its sign and doing subtraction. It's only safe to subtract a positive number from INT_MAX, or subtract a negative number from INT_MIN, so we can modify these:

y > INT_MAX - x
y < INT_MIN - x

The safest way to do it is then

x < 0? ( y < INT_MIN - x ) : ( y > INT_MAX - x );

Edit: Woops, I didn't guess what the function did with the overflow flag. It apparently returns the result if there's no overflow, returns INT_MAX if there is a positive overflow, and INT_MIN if there's a negative overflow. In other words, it's saturating addition. The way it does this is a bit convoluted, and it looks like the author took pains to eliminate branches. But overflow usually doesn't happen, and a predictable branch is cheaper than a lot of arithmetic, so it's probably worth trying a more straightforward implementation using if … else.

Upvotes: 5

Related Questions