Bitshift Operations?

[christinetom]

Hello there everybody..

I am just trying to understand something in relation to bitshift operations. With reference to the small program below. I have tried to keep this as simple as possible.

I understand that by doing this (integer << x), a temporary variable is formed to contain the result of the new value of the integar where all bits have been moved to the left (from least significant to the most significant bit) by x places.

I'm just not sure I understand why when after the 32 bits have been exceeded (I'm using a 32 bit system, int = 32 bits), that the operation seems to start from scratch again. I thought all the bits would just be pushed off the edge of the 32 bits and the remaining output would be zero.

If you see the output below the procedure below, after 32 cycles, it starts again. Is it true that the bitshift operations will continually loop through the 32 bits and return to the start after the 32 bits have been exceeded? Is there another explanation?

int t = 1;

for (int p = 0; p < 40; p++)
{

   cout << "Count: " << p << " - "<< (t << p) << endl;
}

Output:

    Count: 0 - 1
    Count: 1 - 2
    Count: 2 - 4
    Count: 3 - 8
    Count: 4 - 16
    Count: 5 - 32
    Count: 6 - 64
    Count: 7 - 128
    Count: 8 - 256
    Count: 9 - 512
    Count: 10 - 1024
    Count: 11 - 2048
    Count: 12 - 4096
    Count: 13 - 8192
    Count: 14 - 16384
    Count: 15 - 32768
    Count: 16 - 65536
    Count: 17 - 131072
    Count: 18 - 262144
    Count: 19 - 524288
    Count: 20 - 1048576
    Count: 21 - 2097152
    Count: 22 - 4194304
    Count: 23 - 8388608
    Count: 24 - 16777216
    Count: 25 - 33554432
    Count: 26 - 67108864
    Count: 27 - 134217728
    Count: 28 - 268435456
    Count: 29 - 536870912
    Count: 30 - 1073741824
    Count: 31 - -2147483648
    Count: 32 - 1
    Count: 33 - 2
    Count: 34 - 4
    Count: 35 - 8
    Count: 36 - 16
    Count: 37 - 32
    Count: 38 - 64
    Count: 39 - 128

[sepp2k]

Shifting an n-bit integer by m bits when m > n invokes undefined behavior in C and C++.

If you change your code like this, it will give you 0 from count 32 onwards as you'd expect:

unsigned int t = 1;
for (unsigned int p = 0; p < 40; p++)
{
    cout << "Count: " << p << " - "<< t << endl;
    t = t << 1;
}

Here I made two changes to your code:

1. Instead of shifting t by p, I shift t by one and store the result in t. This will still lead to t having been shifted p times, but since I only ever shift by 1 bit at a time, I don't invoke undefined behavior.

2. I made t into an unsigned integer. The reason for that is that signed integer overflow invokes undefined behavior as well.

[christinetom]

When m > n, it might invoke undefined behaviour, but what I am trying to understand is that the cycle seems to go back to the beginning again when presented my way. That's the only reason I have done this as I noticed this every time m > n.

When I say the cycle goes back to the beginning I mean that after I have shifted by 32 bits it seems to go back to the first bitshift result again.

[sepp2k]

I assume it only looks at the last 5 bits of the right operand to << and ignores anything else (presumably that's how it's implemented in the CPU). So 32 is the same as 0, 33 as 1 etc. The reason it's allowed to do that is that, as I said, it's undefined behavior and thus any behavior is allowed.

[christinetom]

Thanks. If it's undefined behaviour then that's the answer to this. I just thought there must be some kind of rule with bitshift operations which confines the shift within 32 bits.

[rubberman]

There is no rule. This issue is processor-dependent. Some will drop data when the shift results in an integer wrap-around event, and others will push the left-most bit to the right-most (or vice-versa depending if the operator is << or >>). IE, what happens on an x86 processor may be different to what happens on an ARM chip. Sometimes, you can set the chip to use either means, but not for all processors. This is DEFINITELY a case of caveat programmer!