Defining array of long long int

Question

I am trying to generate an array that will hold powers of 2 from 2^0 to 2^63. I am using unsigned long long int for this. But when i print all the values it is printing till 2^30 and then it is overflowing. Compiler is GNU GCC version 4.8.1. Here is the code.

unsigned long long int a[65],i;
a[0]=1;
for(i=1;i<65;i++) {

   a[i]=2<<(i-1);
   printf("i=%d a[i]=%lld\n",i, a[i]);
}

Here is the output

i=1 a[i]=2
i=2 a[i]=4
i=3 a[i]=8
i=4 a[i]=16
i=5 a[i]=32
i=6 a[i]=64
i=7 a[i]=128
i=8 a[i]=256
i=9 a[i]=512
i=10 a[i]=1024
i=11 a[i]=2048
i=12 a[i]=4096
i=13 a[i]=8192
i=14 a[i]=16384
i=15 a[i]=32768
i=16 a[i]=65536
i=17 a[i]=131072
i=18 a[i]=262144
i=19 a[i]=524288
i=20 a[i]=1048576
i=21 a[i]=2097152
i=22 a[i]=4194304
i=23 a[i]=8388608
i=24 a[i]=16777216
i=25 a[i]=33554432
i=26 a[i]=67108864
i=27 a[i]=134217728
i=28 a[i]=268435456
i=29 a[i]=536870912
i=30 a[i]=1073741824
i=31 a[i]=-2147483648
i=32 a[i]=0
i=33 a[i]=2
i=34 a[i]=4
i=35 a[i]=8
i=36 a[i]=16
i=37 a[i]=32
i=38 a[i]=64
i=39 a[i]=128
i=40 a[i]=256
i=41 a[i]=512
i=42 a[i]=1024
i=43 a[i]=2048
i=44 a[i]=4096
i=45 a[i]=8192
i=46 a[i]=16384
i=47 a[i]=32768
i=48 a[i]=65536
i=49 a[i]=131072
i=50 a[i]=262144
i=51 a[i]=524288
i=52 a[i]=1048576
i=53 a[i]=2097152
i=54 a[i]=4194304
i=55 a[i]=8388608
i=56 a[i]=16777216
i=57 a[i]=33554432
i=58 a[i]=67108864
i=59 a[i]=134217728
i=60 a[i]=268435456
i=61 a[i]=536870912
i=62 a[i]=1073741824
i=63 a[i]=-2147483648
i=64 a[i]=0

I have also tried using int64_t, but the results were same. Also if I normally do someting like

unsigned long long int lli = 9223372036854775807;

and printing its value, it is working. Where am i going wrong?

Answer 1

Your problem is in this code: a[i] = 2 << (i-1);

2 is assumed of type int because of that it's 32bits in most compilers of C++.

You need to override this with.

a[i] = 2ULL << (i-1);

You need to take special care with types used with shifting operator, shifting more bits that the size of the operand is Undefined Behavior and anything could happen here (sample), with literals more precaution are need because of the forgot suffix.

Answer 2

The main problem lies in this line:

2<<(i-1)
^

The 2 is an integer literal and thus the result is an int, not an unsigned long long. You can use the ULL suffix to fix this.

This is also undefined behavior to use a shift equal to a greater than the bit length of the promoted left operand. You also have undefined behavior in your use of printf. You are using the incorrect format specifier, in both cases you should be using %llu.

Using the right warning flags probably would have helped you catch all these bugs for example using the following flags -fsanitize=undefined -Wall -Wextra -Wconversion -pedantic with clang gives the following warnings:

 warning: implicit conversion changes signedness: 'int' to 'unsigned long long' [-Wsign-conversion]
a[i]=2<<(i-1);
   ~~^~~~~~~

warning: format specifies type 'int' but the argument has type 'unsigned long long' [-Wformat] 
printf("i=%d a[i]=%lld\n",i, a[i]);
         ~~              ^
         %llu

and the following run-time error:

runtime error: left shift of 2 by 31 places cannot be represented in type 'int'