Unsigned Bitwise Shift Operators [C11]

Question

Edit: As pointed out below I missed the first part of the ANSI C standard: "If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined." The errors (or rather lack of errors / difference in errors) are due to the particular compiler I was using.

I've come across something a bit strange, and I hope that someone can shed some light on my ignorance here. The necessary sample code is as follows:

#include <stdio.h>
int main(void)
{
    unsigned a, b;
    int w, x, y;

    a = 0x00000001;
    b = 0x00000020;
    w = 31;
    x = 32;
    y = 33;

    a << w; /*No error*/
    a << x; /*No error*/
    a << y; /*No error*/

    a << 31; /*No error*/
    a << 32; /*Error*/
    a << 33; /*Error*/

    a << 31U; /*No error*/
    a << 32U; /*Error*/
    a << 33U; /*Error*/

    a << w + 1; /*No error*/
    a << b; /*No error*/

    return 0;
}

My question is this: why is it that an error is returned for a raw number, but not for any of the variables? They, I think, should be treated the same. According to the C11 standard

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 × 2^E2 , reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 × 2 E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

The right side, since the left is unsigned type, should be 2^E2 reduced modulo one more than the maximum value representable in the result type.... That sentence isn't entirely clear to me, but in practice it seems that it is E1 << (E2%32) - despite that 32 is not the maximum representable in the result type. Regardless, it is not undefined for the C11 standard, yet the error

left shift count >= width of type [enabled by default]

shows up when trying to compile. I cannot deduce why it is that some values of >31 work (e.g. x = 33; a <

I am using the GCC compiler on 64-Bit Fedora. Thanks in advance. -Will

Answer 1

My question is this: why is it that an error is returned for a raw number, but not for any of the variables?

Because absence of compiler warnings is not a guarantee of good program behavior. The compiler would be right to emit a warning for a << x, but it does not have to.

They, I think, should be treated the same

The compiler is doing you a favor when it warns for a << 33. It is not doing you any favor when it doesn't warn for a << y, but the compiler does not have to do you any favor.

If you want to be certain that your program does not contain undefined behavior, you cannot rely on the absence of compiler warnings, but you can use a sound static analyzer. If a sound static analyzer for undefined behavior does not detect any in your program, then you can conclude that it does not produce any (modulo the conditions of use that would be documented for the analyzer in question). For instance:

$ frama-c -val t.c ... t.c:13:[kernel] warning: invalid RHS operand for shift. assert 0 ≤ x < 32;

in practice it seems that it is E1 << (E2%32)

The reason you are seeing this is that this is the behavior implemented by the shift instructions in x86_64's instruction set. However, shifting by a negative number or by a number larger than the width of the type is undefined behavior. It works differently on other architectures, and even some compiler for your architecture may compute it at compile-time (as part of the constant propagation phase) with rules that differ from the one you have noticed. Do not rely on the result being E1 << (E2%32) any more than you would rely on memory still containing the correct results after being free()d.

Answer 2

The right side, since the left is unsigned type, should be 2^E2 reduced modulo one more than the maximum value representable in the result type.... That sentence isn't entirely clear to me, but in practice it seems that it is E1 << (E2%32) - despite that 32 is not the maximum representable in the result type.

That's not the correct interpretation. It's the result that is modulo 2^32, not E2. That sentence is describing how bits shifted off the left side are discarded. As a result, any E2 greater than or equal to the number of bits in an int would be zero, if it were allowed. Since shifts greater than or equal to that number of bits are undefined behavior, the compiler is doing you the favor of producing an error at compile-time, rather than leaving it until runtime for strange and incorrect things to happen.

Answer 3

For n bit of data shifting is only possible for values x>0 and x<=n-1 where x is no of bit to shift.

here in your case unsigned has memory size equals to 32 bit so only possible shifting ranges from 1 to 31. you are trying to shift data beyond the storage size of that variable that's why it is giving error to you.

Answer 4

modulo one more than the maximum value representable in the result type....

means that the value E1 * 2^E2 is reduced mod (UINT_MAX+1) for unsigned int. This has nothing at all to do with your hypothesis about E2.

Regardless, it is not undefined for the C11 standard,

You forgot to read the paragraph before the one you quoted:

If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

All the shifts of 32 or more cause undefined behaviour. The compiler is not required to issue a warning about this, but it's being nice to you in some of the cases.