Why does bit-shifting an int upwards produce a negative number?

Question

I am new to bit manipulations tricks and I wrote a simple code to see the output of doing single bit shifts on a single number viz. 2

#include <iostream>
int main(int argc, char *argv[])
{

  int num=2;

 do
   {
     std::cout<<num<<std::endl;
     num=num<<1;//Left shift by 1 bit.

   } while (num!=0);


  return 0;
}

The output of this is the following.

2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
-2147483648

Obviously, continuously bit shifting to the left by 1 bit, will result in zero as it has done above, but why does the computer output a negative number at the very end before terminating the loop (since num turned zero)??

However when I replace int num=2 by unsigned int num=2 then I get the same output except that the last number is this time displayed as positive i.e. 2147483648 instead of -2147483648

I am using the gcc compiler on Ubuntu Linux

Answer 1

That's because int is a signed integer. In the two's-complement representation, the sign of the integer is determined by the upper-most bit.

Once you have shifted the 1 into the highest (sign) bit, it flips negative.

When you use unsigned, there's no sign bit.

0x80000000 = -2147483648 for a signed 32-bit integer.
0x80000000 =  2147483648 for an unsigned 32-bit integer.

EDIT :

Note that strictly speaking, signed integer overflow is undefined behavior in C/C++. The behavior of GCC in this aspect is not completely consistent:

• num = num << 1; or num <<= 1; usually behaves as described above.
• num += num; or num *= 2; may actually go into an infinite loop on GCC.

Answer 2

Good question! The answer is rather simple though.

The maximum integer value is 2^31-1. The 31 (not 32) is there for a reason - the last bit on the integer is used for determining whether it's a positive or negative number.

If you keep shifting the bit to the left, you'll eventually hit this bit and it turns negative.

More information about this: http://en.wikipedia.org/wiki/Signed_number_representations

Answer 3

As soon as the bit reaches the sign bit of signed (most significant bit) it turns negative.