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

You may also wonder why shifting -1 right gives you the same -1 and not 0. — Alexey Frunze, Dec 03 '11 at 23:15

score 16 · Accepted Answer · edited May 23 '17 at 12:16

16

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.

edited May 23 '17 at 12:16

Community

1
1

answered Dec 03 '11 at 22:19

Mysticial

464,885
45
335
332

Rather, once you shifted too far, you have undefined behaviour! – Kerrek SB Dec 03 '11 at 23:05
Correct, though only for the signed case. Actually, the only question I've asked so far on SO has to do with almost this exact situation. But with `num += num` instead of `num <<= 1`. Apparently GCC allows you to do overflowing shifts on signed integers. – Mysticial Dec 03 '11 at 23:09
Hehe, luckily, "undefined behaviour" includes the situation where your compiler does something that you might enjoy :-) – Kerrek SB Dec 03 '11 at 23:20
Yeah XD... In the case I had in my question. That came up when porting about 30,000 lines of code from Windows to Linux. It wasn't fun to trace that one down... You'd think GCC would at least emit a warning... – Mysticial Dec 03 '11 at 23:25
I'm not sure if such a warning could exist. You can certainly warn if you shift too much in one go (e.g. `n << 99`), but otherwise the validity of your code depends on the *value* of `n`, not just its type and the shift amount, so I don't suppose such a warning can be implemented. (Oh, about your last sentence, I have a feeling that this may also depend on optimization levels...) – Kerrek SB Dec 03 '11 at 23:28
We should move this to chat, since it's no longer about this question. – Mysticial Dec 03 '11 at 23:29
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/5565/discussion-between-mysticial-and-kerrek-sb) – Mysticial Dec 03 '11 at 23:30
Note that it is also undefined behavior to shift a one into the sign bit. – tommyo Feb 03 '14 at 19:42

Tom van der Woerdt · Answer 2 · 2011-12-03T23:13:03.033

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

edited Dec 03 '11 at 23:13

answered Dec 03 '11 at 22:20

Tom van der Woerdt

29,532
7
72
105

Errr, the -1 doesn't account for a whole bit, the ^31 (rather than ^32) does! – John Carter Dec 03 '11 at 23:12
It would be better to refer to `int` rather than "integer" (the latter covers all integer types), and to note that the range of type `int` is implementation-defined. – Keith Thompson Dec 03 '11 at 23:23
Though not wrong, this is a bit misleading; it might cause people to think that someone actually uses sign-magnitude representation. – harold Dec 04 '11 at 19:42

score 0 · Answer 3 · answered Dec 03 '11 at 22:19

0

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

answered Dec 03 '11 at 22:19

Michael Krelin - hacker

138,757
24
193
173

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

3 Answers3

Linked