tags:

views:

287

answers:

7

Hi,

I recently faced a strange behavior using the right-shift operator.

The following program:

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <stdint.h>

int foo(int a, int b)
{
   return a >> b;
}

int bar(uint64_t a, int b)
{
   return a >> b;
}

int main(int argc, char** argv)
{
    std::cout << "foo(1, 32): " << foo(1, 32) << std::endl;
    std::cout << "bar(1, 32): " << bar(1, 32) << std::endl;
    std::cout << "1 >> 32: " << (1 >> 32) << std::endl; //warning here
    std::cout << "(int)1 >> (int)32: " << ((int)1 >> (int)32) << std::endl; //warning here

    return EXIT_SUCCESS;
}

Outputs:

foo(1, 32): 1 // Should be 0 (but I guess I'm missing something)
bar(1, 32): 0
1 >> 32: 0
(int)1 >> (int)32: 0

What happens with the foo() function ? I understand that the only difference between what it does and the last 2 lines, is that the last two lines are evaluated at compile them. And why does it "work" if I use a 64 bits integer ?

Any lights regarding this will be greatly appreciated !


Surely related, here is what g++ gives:

> g++ -o test test.cpp
test.cpp: In function 'int main(int, char**)':
test.cpp:20:36: warning: right shift count >= width of type
test.cpp:21:56: warning: right shift count >= width of type
+27  A: 
KennyTM
Thanks. I always thought that shifting "too much" resulted in zero-ing the value, not UB. So I guess using a 64 bits value here (with `32` as the right shift operand) is both correct and defined behavior ?
ereOn
@ereOn: Correct.
KennyTM
`b % 32` seems correct; I tried a `foo(16, 33)` and got `8` as the result. Good sleuthing!
tzaman
Very good answer; clear and complete explanations. Thanks again.
ereOn
A: 

I suppose the reason is that int type holds 32-bits (for most systems), but one bit is used for sign as it is signed type. So only 31 bits are used for actual value.

DixonD
Signedness is a matter of interpretation on the language level. The CPU "sees" bits, not values or signs.
DevSolar
+4  A: 

OK. So it's in 5.8.1:

The operands shall be of integral or enumeration type and integral promotions are performed. The type of the result is that of the promoted left operand. 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.

So you have an Undefined Behaviour(tm).

Tadeusz Kopec
A: 

The warning says it all!

But in fairness I got bitten by the same error once.

int a = 1;
cout << ( a >> 32);

is completely undefined. In fact the compiler generally gives a different results than the runtime in my experience. What I mean by this is if the compiler can see to evaluate the shift expression at run time it may give you a different result to the expression evaluated at runtime.

bradgonesurfing
+1  A: 

I compiled it on 32 bit windows using VC9 compiler. It gave me the following warning. Since sizeof(int) is 4 bytes on my system compiler is indicating that right shifting by 32 bits results in undefined behavior. Since it is undefined, you can not predict the result. Just for checking I right shifted with 31 bits and all the warnings disappeared and the result was also as expected (i.e. 0).

Naveen
undefined != unpredictable. It *might* mean that, but it ain't necessarily so.
Nathan Fellman
@Nathan But for practical reasons undefined should generally be treated like unpredictable. Otherwise one would couple the code to a very specific build/run-time environment.
mxp
This is why both Intel and Microsoft have so much trouble with backward compatibility. Software often (or often enough) does something undefined, only to find that it breaks on a future CPU or OS. The users don't know that the software is wrong, and assume Intel or Microsoft broke it, resulting in bad press. Microsoft and Intel go to great lengths not to break legacy code even if it was poorly written.
Nathan Fellman
A: 

foo(1,32) performs a rotate-shit, so bits that should disappear on the right reappear on the left. If you do it 32 times, the single bit set to 1 is back to its original position.

bar(1,32) is the same, but the bit is in the 64-32+1=33th bit, which is above the representable numbers for a 32-bit int. Only the 32 lowest bit are taken, and they are all 0's.

1 >> 32 is performed by the compiler. No idea why gcc uses a non-rotating shift here and not in the generated code.

Same thing for ((int)1 >> (int)32)

Calvin1602
`>>` is _not_ a rotating shift, otherwise `1 >> 1` would yield `INT_MIN`, which it provably does not. The problem here is that shifting by as many or more bits as there are in a type is U.B. That in this case it manifested itself as a result equivalent to a rotating shift is coincidental.
Pavel Minaev
+2  A: 

What happens in foo is that the shift width is greater than or equal to the size of the data being shifted. In the C99 standard that results in undefined behaviour. It's probably the same in whatever C++ standard MS VC++ is built to.

The reason for this is to allow compiler designers to take advantage of any CPU hardware support for shifts. For example, the i386 architecture has an instruction to shift a 32 bit word by a number of bits, but the number of bits is defined in a field in the instruction that is 5 bits wide. Most likely, your compiler is generating the instruction by taking your bit shift amount and masking it with 0x1F to get the bit shift in the instruction. This means that shifting by 32 is the same as shifting by 0.

JeremyP