3

Currently I'm working on a brute force algorithm for the knapsack problem. Everything is working perfectly for small problem instances, for example 15 items. But when I run my program for bigger instances like 31 or 32, the algorithm is failing. I've run into a problem with bit-wise shift which I'm using to compute the number of possible solutions. For example with 10 items the program should make 2^10 iterations, so I'm using this statement:

unsigned long long int setCnt = (1 << 10);

The computed value 1024 is correct. But for (1 << 31) the computed value is 18446744071562067968 (max unsigned long long int), but should be 2147483648. (1 << 32) returns 0. It's like everything works just fine for shifting from 0 to 30 bits.

I'm using Visual Studio 2015 Community and compile my solution in x64 mode. What causes this behaviour? How can I circumvent this?

Hermann Döppes
  • 1,373
  • 1
  • 18
  • 26
radeko
  • 33
  • 1
  • 4

1 Answers1

3

The problem is that 1 is a signed int constant literal -- so the shift is done as a signed int shift (which is apparently just 32 bits including the sign on your compiler), so it overflows, leading to undefined behavior.

Try using 1ULL << 32 (or whatever other shift amount you want) -- the ULL suffix makes the constant an unsigned long long, matching the type of your desired result. This might still overflow if the shift amount becomes too large for an unsigned long long, but until then it will work.

Chris Dodd
  • 119,907
  • 13
  • 134
  • 226
  • Worked like a charm! I did not realize that 1 is taken as signed int in this case. Thanks a lot. – radeko Dec 03 '16 at 19:42
  • 1
    Integer literals with no suffix that can fit in a signed int are taken as a signed int in **ALL** cases in C and C++ – Chris Dodd Dec 03 '16 at 19:51