64bit shift problem.

Question

Why this code does not write 0 as a last element but 18446744073709551615? (compiled with g++)

#include <iostream>

using namespace std;
int main(){
    unsigned long long x = (unsigned long long) (-1);
    for(int i=0; i <= 64; i++)
     cout << i << " " << (x >> i) << endl;
    cout << (x >> 64) << endl;
    return 0;
}

Answer 1

well, you are shifting one too many times. you are shifting from 0 to 64 inclusive which is a total of 65 times. You generally want:

for(int i=0; i < 64; i++)
    ....

Answer 2

Shifting a number a number of bits that is equal to or larger than its width is undefined behavior. You can only safely shift a 64-bit integer between 0 and 63 positions.

Answer 3

When you shift a value by more bits than word size, it usually gets shifted by mod word-size. Basically, shifting it by 64 means shifting by 0 bits which is equal to no shifting at all. You shouldn't rely on this though as it's not defined by the standard and it can be different on different architectures.

Answer 4

This warning from the compiler should be a hint:

"warning: right shift count >= width of type"

This results in undefined behavior:

http://sourcefrog.net/weblog/software/languages/C/bitshift.html

Answer 5

I get:

test.c:8: warning: right shift count >= width of type

so perhaps it's undefined behavior?

Answer 6

You overflow the shift. If you've noticed, GCC even warns you:

warning: right shift count >= width of type

How come? You include 64 as a valid shift, which is an undefined behavior. counting from 0 to 64 there are 65 numbers (0 included). 0 being the first bit (much like arrays).

#include <iostream>

using namespace std;
int main(){
    unsigned long long x = (unsigned long long) (-1);
    for(int i=0; i < 64; i++)
        cout << i << " " << (x >> i) << endl;
    cout << (x >> 63) << endl;
    return 0;
}

Will produce the output you'd expect.

Answer 7

The bit pattern of -1 looks like 0xFFFFFFFFFFFFFFFF in hex, for 64 bit types. Thus if you print it as an unsigned variable you will see the largest value an unsigned 64 bit variable can hold, i.e. 18446744073709551615.

When bit shifting we don't care what a value means in this case, i.e. it doesn't matter if the variable is signed or unsigned it is treated the same way (shifting all bits one step to the right in this case).