Undefined behavior of right-shift in C++

15
votes

From cppreference.com:

For unsigned a and for signed a with nonnegative values, the value of a >> b is the integer part of a/2b . For negative a, the value of a >> b is implementation-defined (in most implementations, this performs arithmetic right shift, so that the result remains negative).

In any case, if the value of the right operand is negative or is greater or equal to the number of bits in the promoted left operand, the behavior is undefined.

Why do we have an undefined behavior in case the right operand is greater or equal to the number of bits in the promoted left operand?
It seems to me that the result should be 0 (at least for unsigned/positive integers)...

In particular, with g++ (version 4.8.4, Ubuntu):

unsigned int x = 1;
cout << (x >> 16 >> 16) << " " << (x >> 32) << endl;

gives: 0 1

2
c++bit-shift
See: stackoverflow.com/questions/19636539/… - not actually a duplicate question of this one, but certainly explains that it is undefined behaviour, and why. Short version: shift instructions in modern processors often won't shift by more than the register bit width. - davmac
Some assembler instructions for rightshift have only 5 bit for the second operand. The first 5 bit of 32 are 0, so you have 1 >> 0 in some assembler languages. - mch
You can make your own: unsigned int right_shift(unsigned int x, int shift_amount) { if (shift_amount >= std::numeric_limits<unsigned int>::digits) return 0; return x >> shift_amount; } Notice the extra work to check the size? That's why >> by itself doesn't do that. - Eljay
At least on x86 shift instruction considers/masks only lower 5 bits of the value, i.e. it's basically x >> (num % 32) (same for <<). Implementing it as you want would require an expensive (relatively) branch to check if 0 < num < 32. - Dan M.
Long read, but super interesting if you're curious about undefined behaviour, especially the motivation behind it blog.regehr.org/archives/213 - krsteeve

2 Answers

32
votes

One of the goals of C++ is to allow for fast, efficient code, "close to the hardware". And on most hardware, an integer right shift or left shift can be implemented by a single opcode. The trouble is, different CPUs have different behavior in this case where the shift magnitude is more than the number of bits.

So if C++ mandated a particular behavior for shift operations, when producing code for a CPU whose opcode behavior doesn't match all the Standard requirements, compilers would need to insert checks and logic to make sure the result is as defined by the Standard in all cases. This would need to happen to almost all uses of the built-in shift operators, unless an optimizer can prove the corner case won't actually happen. The added checks and logic would potentially slow down the program.

1
votes

To give a specific example, x86 trims the shift count to 5 bits (6 bits for 64-bit shifts), while ARM trims the shift count to 8 bits. With current C++ standard, compilers for both CPUs can implement shifts with a single opcode.

If the C++ standard were to define the outcome of shifts by more than the operand length in a particular way, compilers targeting at least one of the CPU families (and possibly both, if the outcome required by C++ wouldn't match either hardware implementation, like the behaviour you suggest) would have to implement each shift operation using branches which would produce the required result where the CPU opcode wouldn't.