Unsigned integer wrapping, different behaviour

Question

Here is a code in C:

#include <stdio.h>

int main()
{
    printf("Int width = %lu\n", sizeof(unsigned int)); // Gives 32 bits on my computer

    unsigned int n = 32;
    unsigned int y = ((unsigned int)1 << n) - 1;  // This is line 8
    printf("%u\n", y);
    
    unsigned int x = ((unsigned int)1 << 32) - 1; // This is line 11
    printf("%u", x);
    
    return 0;
}

It outputs:

main.c:11:39: warning: left shift count >= width of type [-Wshift-count-overflow]
Int width = 4
0
4 294 967 295 (= 2^32-1)

The warning for the line 11 is expected as explained in these links: wiki.sei.cmu.edu and https://stackoverflow.com/a/11270515

left-shift operations [...] 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.

There is no warning for the line 8, but I was expected the same warning as for line 11. Futhermore, the results are entirely different ! What do I miss ?

This behaviour is similar for C++:

#include <iostream>
using namespace std;
int main()
{
    cout << "Int width = " << sizeof(uint64_t) << "\n"; // Gives 64 bits on my computer

    int n = 64;
    uint64_t y = ((uint64_t)1 << n) - 1; // This is line 8
    cout << "y = " << y;
    
    uint64_t x = ((uint64_t)1 << 64) - 1; // This is line 11
    cout << "\nx = " << x;

    return 0;
}

Which outputs:

main.cpp:11:34: warning: left shift count >= width of type [-Wshift-count-overflow]                                                            
Int width = 8                                                                                                                                  
y = 0                                                                                                                                          
x = 18 446 744 073 709 551 615 (= 2^64-1)

I used the onlineGBD for C compiler for the C code and onlineGBD for C++ compiler. Here are the link to the code: C code and C++ code.

Answer 1

For line 8, the compiler has to prove that in ((unsigned int)1 << n), n is 32 or more. That can be difficult since n is not const so it's value could be changed. The compiler would have to do more static analysis to give you the warning.

On the other hand, with (unsigned int)1 << 32) the compiler knows that the value is 32 or more and can easily warn. This requies almost no time to detect, since the type and the value to shift by are both compile time "literals".

If you switch to using const int n = 64; in your C++ code, then you will get an error at OnlineGBD. You can see that here. I tried that with the C version but it still doesn't warn.

Answer 2

There is no warning for the line 8, but I was expected the same warning as for line 11.

The C standard does not require a compiler to diagnose an excessive shift amount. (Generally, it does not require C implementations to diagnose errors other than those explicitly listed in “Constraints” clauses.)

The compiler you using diagnoses the error with the integer constant expression (32), as this is easy. It does not diagnose the error with the variable n, as that involves more work and the compiler authors have not implemented it.

Futhermore, the results are entirely different !

With the integer constant expression, the compiler evaluates the shift during compilation, using whatever software is built into it. That apparently produces zero for (unsigned int) 1 << 32. With the variable, the compiler generates an instruction to perform the shift during program execution. That instruction likely uses only the low five bits of the right operand, so an operand of 32 (100000₂) yields of shift of zero bits, so shifting (unsigned int) 1 produces one.

Both behaviors are allowed by the C standard.

Answer 3

It's likely because n is a variable, the compiler doesn't seem to be verifying it, as it doesn't know its value it doesn't issue a warning, if you turn it into a constant i.e const int n = 64;, the warning is issued.

https://godbolt.org/z/4s5jz6

As for the results, undefined behavior is what it is, for the sake of curiosity you can analyze a particular case and try to figure out what the compiler did, but the results can't be reasoned with because there is no correct result.

Even the warnings are optional, gcc is nice enough to to warn you when a constant or constant literal is used but it didn't have to.

Answer 4

Undefined behaviour (UB) means undefined behaviour. Literally anything can happen. Compilers are not required to tell you of UB, but are permitted to.

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.

So max unsigned -1, or zero, or format your SSD while installing viruses on your cloud stored files and emailing your browser history to your contact list are all permitted things for your compiler to convert a shift of 32 bits of a 32 bit integer.

As a Quality of Implementation issue, the last is rare.

The compiler is optimizing (1<<x)-1 as x 1 bits, not even doing a shift operation, in one case. Within the bounds of defined shift operations, this is equivalent, so this is a valid optimization. So when you pass 32, it writes 0xffffffff.

In the other case, it is maybe setting the nth bit, reading the low 5 bits of the shift operation to see which to set. Also valid within the range of defined behaviour, utterly different.

Welcome to UB.

I would expect further changes based on optimization level.