C++按位左移32

Question

目前我正在研究背包问题的蛮力算法。对于小问题实例，一切正常工作，例如15个项目。但是当我为31或32等更大的实例运行我的程序时，算法失败。我遇到了一个按位转换的问题，我正在使用它来计算可能的解决方案的数量。例如有10个项目计划应该2^10次迭代，所以我用这个语句：

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

的计算值1024是正确的。但是对于(1 << 31)，计算得出的值是18446744071562067968（最大unsigned long long int），但应该是2147483648. (1 << 32)返回0.它就好像从0位移到30位一切正常。

我正在使用Visual Studio 2015社区并在x64模式下编译我的解决方案。 是什么导致了这种行为？我怎样才能绕过这个？

Answer 1

的问题是，1是signed int常量文字 - 这样的转变是一个signed int转变完成（这显然是包括你的编译器的符号只有32位），所以它溢出，导致不确定的行为。

尝试使用1ULL << 32（或任何其他需要的移位量） - ULL后缀使得常数为unsigned long long，与您所需结果的类型相匹配。如果移位量对unsigned long long过大，这可能仍然会溢出，但在此之前它会起作用。