问题描述
目前，我正在研究背包问题的蛮力算法.一切对于小问题实例(例如15个项目)都运行良好.但是，当我针对较大的实例(例如31或32)运行程序时，该算法将失败.我遇到了按位移位的问题，该问题用于计算可能的解决方案的数量.例如，对于10个项目，程序应进行2 ^ 10次迭代，因此我使用了以下语句:
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);
计算值1024是正确的.但是对于(1<<<<<<<<<<<<<<<>)(计算值是18446744071562067968(最大 unsigned long long int )，但应为2147483648.(1<<; 32)返回0.就像从0到30位转换一样，一切正常.
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.
我正在使用Visual Studio 2015社区，并以x64模式编译我的解决方案.是什么原因导致这种行为?我该如何规避?
I'm using Visual Studio 2015 Community and compile my solution in x64 mode.What causes this behaviour? How can I circumvent this?
推荐答案
问题是 1 是一个 signed int 常量常量，因此转换操作如下 signed int 移位(显然只有32位，包括编译器上的符号)，因此它会溢出，从而导致未定义的行为.
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.
尝试使用 1ULL<<32 (或您想要的任何其他移位量)-后缀 ULL 使常数成为 unsigned long long ，与所需结果的类型匹配.如果移位量对于 unsigned long long 而言太大，这可能仍然会溢出，但是在那之前它将起作用.
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.
这篇关于C ++按位左移32的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！