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?

Solution 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.

Solution 2

The problems is 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'

Solution 3

The other answers have already answered the question you're asking, but there are some other problems in your code.

To expand on the other answers, keep in mind that the type of a C expression is generally determined by the expression itself, not by the context in which it appears. You have:

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

The fact that the left side of the assignment is of type unsigned long long int doesn't affect the evaluation of the right side, which is of type int, and the << results in an int overflow.

There's no need to treat element 0 of the array as a special case.

Rather than 2 << (i-1), or more correctly 2ULL << (i-1), it's more straightforward to write 1ULL << i.

You're using the wrong printf format strings for your variables. i is of type unsigned long long; "%d" requires an argument of type int. But since i just counts from 0 to 65, it might as well be an int. The elements of a are of type unsigned long long int, but you're using the format for signed long long int.

Here's a modified version of your program code snippet, fleshed out to a complete program and with the above problems corrected:

#include <stdio.h>
int main(void) {
    unsigned long long int a[65];
    int i;
    for(i=0;i<65;i++) {
        a[i] = 1ULL << i;
        printf("i=%d a[i]=%llu\n", i, a[i]);
    }
}

Comments

[user1551574]

printf statement was just for testing purpose, before posting i was trying few things, so made i as long long int.

[Keith Thompson]

@user1551574: Sure, but even if it's just for testing purposes (perhaps especially if it's for testing purposes), it's worth the effort to use exactly the right format string.