visual-studio-2015 - 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 Community 并在 x64 模式下编译我的解决方案。是什么导致了这种行为？我怎样才能避免这个？

Answer 1

问题是 1是 signed int常量字面量——所以转换是作为 signed int 完成的shift(这显然只有 32 位，包括编译器上的符号)，所以它会溢出，导致未定义的行为。

尝试使用 1ULL << 32 (或您想要的任何其他移动量)- ULL后缀使常量成为 unsigned long long , 匹配您想要的结果的类型。如果移位量对于 unsigned long long 来说太大，这可能仍然会溢出。 ，但在那之前它会起作用。