C++ 按位左移 32 [英] C++ bitwise left shift by 32

问题描述

目前我正在研究背包问题的蛮力算法.对于小问题实例，例如 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 <<31)，计算出的值是 18446744071562067968 (max 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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！