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

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).

Answer 2

You can use:

static inline pack_t lshift_fix64(pack_t shiftee, short_idx_t shifter){
  return (shiftee << shifter) & (-(shifter < 64));
}

for such a trick,

(-(shifter < 64)) == 0xffff ffff ffff ffff

if shifter < 64 and

(-(shifter < 64)) == 0x0

otherwise.

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

Another trap for the unwary: I know this is an old thread, but I came here looking for help. I got caught out on a 64 bit machine using 1<<k when I meant 1L<<k; no help from the compiler in this case :(

Answer 5

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 6

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.