CODEWITHSUNDEEP
c++bit-manipulation
Aks
Aks

Reputation: 5236

What is happening when I left shift beyond INT_MAX ?

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?

Upvotes: 6

Views: 1550

Answers (4)

Vlad from Moscow
Vlad from Moscow

Reputation: 311048

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.

Upvotes: 2

fede1024
fede1024

Reputation: 3098

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.

Upvotes: 12

wesley.mesquita
wesley.mesquita

Reputation: 785

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.

Upvotes: 2

αλεχολυτ
αλεχολυτ

Reputation: 5039

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 × 2E2, 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×2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined

Upvotes: 7

Related Questions