Home > Mobile >  A C left shift anomaly in unsigned long long ints
A C left shift anomaly in unsigned long long ints

Time:05-08

When this code:

// Print out the powers of 2 from 1 to 63. 
#include <stdio.h>

int main() {
  unsigned long long n = 64;
  for (unsigned long long i = 1; i < n; i  ) {
    unsigned long long po2 = (1 << i);
    printf("%llu) %llu/%0llX\n", i, po2, po2);
  }
  printf("Size of unsigned long long int: %ld.\n", sizeof(unsigned long long int));
}

is run, left shift values up to 30 are correct:

1) 2/2
2) 4/4
3) 8/8
...
28) 268435456/10000000
29) 536870912/20000000
30) 1073741824/40000000

However, once i == 31 (a 32 bit left shift), the results are not correct:

31) 18446744071562067968/FFFFFFFF80000000
32) 1/1
33) 2/2
34) 4/4
35) 8/8
36) 16/10
37) 32/20
...  
61) 536870912/20000000
62) 1073741824/40000000
63) 18446744071562067968/FFFFFFFF80000000  
Size of unsigned long long int: 8.

This is run on a 64 bit machine, and the C Standard states:

The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. 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.

Note that the variables, i and n, in the above code are both 64 bit integers, yet they are treated as if they were 32 bit integers!

CodePudding user response:

Look at the << operation in the following line:

unsigned long long po2 = (1 << i);

What is its left operand? Well, that is the int literal, 1, and an int type will not undergo promotion, in that context1. So, the type of the result will be int, as specified in the extract from the Standard that you cited, and that int result will be converted to the required unsigned long long type … but after the overflow (undefined behaviour) has already happened.

To fix the issue, make that literal an unsigned long long, using the uLL suffix:

unsigned long long po2 = (1uLL << i);

1 Some clarity on the "context" from this cppreference page (bold emphasis mine):

Shift Operators


First, integer promotions are performed, individually, on each operand (Note: this is unlike other binary arithmetic operators, which all perform usual arithmetic conversions). The type of the result is the type of lhs after promotion.

CodePudding user response:

Adrian Mole is correct. The revised code:

// Print out the powers of 2 from 1 to 63. 
#include <stdio.h>

int main() {
  unsigned long long n = 64,
                     one = 1;
  for (unsigned long long i = 1; i < n; i  ) {
    unsigned long long po2 = (one << i);
    printf("%llu) %llu/%0llX\n", i, po2, po2);
  }
  printf("Size of unsigned long long int: %ld.\n", sizeof(unsigned long long int));
}

works.

  • Related