一个奇怪的移位计算结果

今天强迫症朱小瘦同学提到一个非常有意思的问题，一个32bit的无符号整数算术右移32个bit应该得多少？

我们知道算术右移一个bit相当于除2，所以一个32bit无符号整数除以$2^{32}$，理论上，应该得0。

然而事实不是这样。测试显示在x86系统上，一个32bit无符号整数算术右移32个bit之后得到的是原数。例如下面这个测试程序：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <stdio.h>

int
main(void /* int argc, char **argv */)
{
	unsigned int a = 0x5a5a5a5a;

	a >>= 32;

	printf("%x\n", a);

	return 0;
}

不启用任何优化的话，编译出来的程序得到的结果是：

5a5a5a5a

更进一步，我们将上面的测试改写为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#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® 64 and IA-32 Architectures Software Developer’s Manual, Volume 2（Intel文献编号325383），卷2-B，4-357页找到了下面这段描述：

1
2
3
4
5
6

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不得不忠实地继续实现这个行为，而不是将其改正。

这个后果相当严重，简单地说，想要绕过这个问题，使用>>或者<<的时候，其后就必须使用常量而不是变量（如果必须用变量，则应用一个循环），然后把剩下的问题交给编译器。