C++ left shift overflow for negative numbers

Question

As shown below, the code has a bug. When input a = -1, b = 1, one of the line has runtime error. Could you please help me understand how (a & b) becomes INT_MIN?

In my understanding, -1 is represented as 32-bit binary format 0xFFFFFFFF, and 1 is represented as 32-bit format 0x00000001, thus (-1 & 1) will become 0x00000001. And my python command also shows '0b1' as result. Why does it report the error of INT_MIN?

int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;//BUG! left shift of negative value -2147483648
        a = a ^ b;
        b = carry;
    }

    return a;
}

Update: Is right shift for negative numbers well-defined? It seems ok to right shift negative numbers as long as it satisfies the requirements as quoted below.

From cppreference.com,

For unsigned a and for signed a with nonnegative values, the value of a >> b is the integer part of a/2b . For negative a, the value of a >> b is implementation-defined (in most implementations, this performs arithmetic right shift, so that the result remains negative).

In any case, if the value of the right operand is negative or is greater or equal to the number of bits in the promoted left operand, the behavior is undefined.

We aware that exists more than one way to represent a negative number in binary, not only 0xFFFFFFFF en.wikipedia.org/wiki/Signed_number_representations — Miguel
note that XOR doesn't produce more bits than the operands, so it can never overflow (except probably on systems with trap representation) Can XOR of two integers go out of bounds?. INT_MIT is well within int's range, therefore it's not an overflow — phuclv
The first a & b is 1 as you say, but you are in a while loop that updates the values of a and b, the bug comes on a later iteration — M.M

AShelly AShelly · Accepted Answer · 2019-04-10T22:10:26

Assuming this is C or C++, your error is because a Left Shifting a negative value is Undefined Behavior, and left shifting a signed value such that it becomes bigger than MAX_INT is also Undefined Behavior.

If you inspect the values of a and b as you run through this sequence, you will get:

-1 1
-2 2
-4 4
...
-1073741824 1073741824

At this point a&b == 1073741824. But shifting it left by 1 is the same as multiplying by 2, which would give 2147483648, which is larger than INT_MAX.

That's Undefined Behavior. The system can choose to do anything. It appears that in your case, it did the bitshift giving 0x80000000. In a signed int, this represents INT_MIN. So the next time through the loop, you are trying to left shift a negative number, which again is Undefined Behavior. Your system chose to treat this as an exception.

In general, if you are doing bit-manipulations, you are best using unsigned types.

C++ left shift overflow for negative numbers

1 Answers