一个奇怪的移位计算结果
今天 强迫症 朱小瘦同学提到一个非常有意思的问题,一个32bit的无符号整数算术右移32个bit应该得多少?
我们知道算术右移一个bit相当于除2,所以一个32bit无符号整数除以 2^32,理论上,应该得0。
然而事实不是这样。测试显示在 x86 系统上,一个32bit无符号整数算术右移32个bit之后得到的是原数。例如下面这个测试程序:
#include <stdio.h> int main(void /* int argc, char **argv */) { unsigned int a = 0x5a5a5a5a; a >>= 32; printf("%x\n", a); return 0; }
不启用任何优化的话,编译出来的程序得到的结果是:
5a5a5a5a
更进一步,我们将上面的测试改写为:
#include <stdio.h> int main(void /* int argc, char **argv */) { unsigned int a = 0x5a5a5a5a; int i; for (i=0; i<33; i++) printf("%x\n", a >> i); return 0; }
则无论优化级别为何,都可以看到在 i=32 时得到原数这一奇怪的结果。进一步观察发现,当i上限为65时,i=3332..6463 时的结果实际上与 i=0..3231 重复。或者说实际上对 >> 算符来说,它将 i 按 32 做了取模运算。【此处感谢 owen_water 指出】
继续测试,如果 i 从31开始到33结束,采用 -O3 优化,则得到的是正确的结果。
观察汇编代码发现,-O3得到正确结果的原因是它直接将两次循环展开,并直接填入了正确的结果。
而对比组(第一个循环 0 .. 32),则采用的是 shrl 指令计算。因此,这个取模的行为是 CPU 进行的。这样做有什么依据呢?翻阅 Intel(R) 64 and IA-32 Architectures Software Developer's Manual, Volume 2 (Intel 文献编号 325383),卷 2-B,4-357页找到了下面这段描述:
IA-32 Architecture Compatibility The 8086 does not mask the shift count. However, all other IA-32 processors (starting with the Intel 286 processor) do mask the shift count to 5 bits, resulting in a maximum count of 31. This masking is done in all operating modes (including the virtual-8086 mode) to reduce the maximum execution time of the instructions.
至此,我们可以看到这个行为是从早期 x86 CPU 上继承的。我认为最开始引入这个取模的原因是在 8086 上计算 SHR 时,内部的实现是一个循环,而到 80286 时希望将计算时间缩短,于是增加了一个 & 0x1f 的操作,但这么一来,在 CPU 看来移位 32 次和不移位就一样了。而后续有些程序依赖了这个行为,导致以后的CPU不得不忠实地继续实现这个行为,而不是将其改正。
这个后果相当严重,简单地说,想要绕过这个问题,使用 >> 或者 << 的时候,其后就必须使用常量而不是变量(如果必须用变量,则应用一个循环),然后把剩下的问题交给编译器。