Need help understanding integer arithmetic function
Someone please be so kind to explain this feature for me, thanks!
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));
}
source to share
It computes an integral "overflow" flag for the addition operation, which indicates whether the value of the result was less than INT_MIN
or greater than INT_MAX
. It is assumed to be int
32 bits, two's complement and the signed number right shift is an "arithmetic" shift that replicates a high order bit - no safe assumptions.
If the sign x
and are the y
same, but the sign of the result is opposite, the result overflows. That's all it calculates. There is no need to be so complicated.
Assuming the addition does not throw cumulative exceptions and there is no winning parity bit, this expression will work by manipulating the sign bit in the same vein 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 careful to rely on well-defined behavior, execution x + y
is illegal if the result might overflow. A machine conforming to the C standard allows the program to terminate on such an overflow (or self-destruct, etc.), so we need to avoid this in the first place.
The tests we want to run
x + y > INT_MAX
x + y < INT_MIN
There is no safe operation between x
and y
. We have to transfer one side of the equation to the other, which means changing its sign and performing a subtraction. It's safe to subtract a positive number from, INT_MAX
or subtract a negative number from INT_MIN
, so we can change them:
y > INT_MAX - x
y < INT_MIN - x
The safest way to do this is
x < 0? ( y < INT_MIN - x ) : ( y > INT_MAX - x );
Edit: Woops, I had no idea what the overflow flag function did. Apparently it returns a result if there is no overflow, returns INT_MAX
if there is a positive overflow, and INT_MIN
if there is a negative overflow. In other words, it is a satiating supplement. The way he does it is a bit confusing and it seems the author went out of his way to eliminate branches. But overflow doesn't usually happen, and the predicted branch is cheaper than a lot of arithmetic, so it's probably worth trying a simpler implementation using if … else
.
source to share