What is happening when I left shift beyond INT_MAX ?

Question

I have this piece of code

int a = 1;
while(1) {
    a<<=1;
    cout<<a<<endl;
}

In the output, I get

.
.
536870912
1073741824
-2147483648
0
0

Why am I not reaching INT_MAX? and what is really happening beyond that point?

Right, and is that a value you would expect to get by repeatedly left-shifting `1`? — Oliver Charlesworth, Feb 02 '14 at 15:37

fede1024 · Accepted Answer · 2014-02-02T15:54:21.907

12

You have a signed int, so numbers are in two's complement. This is what happens

00..01 = 1
00..10 = 2
[...]
01..00 = 1073741824
10..00 = -2147483648 // Highest bit to one means -01..11 - 1 = -(2^31)
00..00 = 0

You cannot reach INT_MAX, at most you will have 2^30.

As pointed out in the comments, c++ standard does not enforce 2's complement, so this code could behave differently in other machines.

edited Feb 02 '14 at 15:54

answered Feb 02 '14 at 15:39

fede1024

3,099
18
23

2

+1 Finally an answer that shows whats going on on bitlevel. Now you should only add the bit representation for `INT_MAX` to show why it is never reached. – Nobody moving away from SE Feb 02 '14 at 15:40
I don't think the C++ standard actually mandates two's complement. The actual behavior is undefined, i.e. you will not get the same effect on obscure machines that may or may not still be running (and of course there are no guarantees about *future* machines). – Frédéric Hamidi Feb 02 '14 at 15:44
1

Yes, the C++ standard does not enforce 2's complement, and there are more than one way to implement it (some architectures for example don't have a sign preserving right shift). So this may not be always true, but i think it's the correct explanation for what is happening in this particular case. – fede1024 Feb 02 '14 at 15:48

score 7 · Answer 2 · edited Feb 02 '14 at 15:43

From ISO/IEC 14882:2011 Clause 5.8/2

The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 × 2^E2, reduced modulo one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1×2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined

score 2 · Answer 3 · edited Feb 02 '14 at 17:04

2

According to the C++ Standard:

The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand

In you example when you shift the number left, vacated bits are zero-filled. As you can see, all your numbers are even. It is because the lowest bits are filled with zero. You should write:

a =  ( a << 1 ) | 1;

if you want to get INT_MAX. Also the loop should check whether the number is positive.

edited Feb 02 '14 at 17:04

Lightness Races in Orbit

378,754
76
643
1,055

answered Feb 02 '14 at 15:43

Vlad from Moscow

301,070
26
186
335

1

The standard quote is useless in this case as the right hand side of the operator is not negative and also not greater than the bitlength of the int (it is always 1). It would become relevant if he would write something like `a << 32`. – Nobody moving away from SE Feb 02 '14 at 15:45
@Nobody I agree. I t would be better to cite other quote from this section. – Vlad from Moscow Feb 02 '14 at 15:48

score 2 · Answer 4 · answered Feb 02 '14 at 15:49

Take a look at this (reference)[http://www.cplusplus.com/reference/climits/]: Assuming INT_MAX == 2^15-1, doing the loop as you are doing you will get 2^14, 2^15 and 2^16, but 2^15-1, never. But INT_MAX differ (look at the ref, or greater), try this in your machine:

#include<climits>
#include<iostream>
int main(){

int a = 1;
int iter = 0; 
std::cout << "INT_MAX == " << INT_MAX << " in my env" << std::endl;

while(1) {

    a <<=1;
    std::cout << "2^" << ++iter << "==" << a << std::endl;
    if((a-1) == INT_MAX){
        std::cout << "Reach INT_MAX!" << std::endl;
        break;
    }   
}
return 0;
}

See how INT_MAX is formed, 2^exp - 1.

What is happening when I left shift beyond INT_MAX ?

4 Answers4