delphij's Chaos

选择chaos这个词是因为~~实在很难找到一个更合适的词来形容这儿了……

13 Jun 2011

一个奇怪的移位计算结果

今天 强迫症 朱小瘦同学提到一个非常有意思的问题,一个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不得不忠实地继续实现这个行为,而不是将其改正。

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


Archived: 17 Comments

blog.wuxinan.net | June 13, 2011 12:05 AM

太伟大了。

mischachen | June 13, 2011 2:08 AM

ARM中的shift又要先& 0xff一把。

owen_water | June 13, 2011 12:14 PM

“进一步观察发现,当i上限为65时,i=33..64时的结果实际上与 i=0..32 重复。或者说实际上对 » 算符来说,它将 i 按 32 做了取模运算。”
应该是i=32..63的结果与i=0..31重复

Xin LI replied to comment from owen_water | June 13, 2011 12:53 PM

已修正,感谢指正。

nero | June 13, 2011 10:33 PM

C标准里面只允许 0-31bit shift 你去研究这么一个未定义行为干吗?

nero | June 13, 2011 10:44 PM

c标准只允许 0-31bit的shift,你研究这个没意义

Xin LI replied to comment from nero | June 13, 2011 11:20 PM

C假定开发人员理解系统到底在做什么,为什么会那样;不研究实现为什么会是这样子的人,窃以为还是别写C了吧。

nero | June 13, 2011 11:55 PM

我表达的意思是,C语言对shift有显式的描述,不同的体系架构对shift有不同的理解,但有一点C可以保证,0-31 bit shift是正确的,这也可以应付几乎所有程序的需求,为什么不多考虑一下C/C++这什么要做这样的限制,而去纠结于某一体系结构的席位呢?说实话,*Developer’s Manual,全套我都有,纸张的,intel免费送,翻一翻也是有意义的.但问题是,你没说到点子上,在C 中 x» 32 是错误的代码。应该避免的,你的代码在x86上工作,在 mips, arm,IA64上呢,你都去研究实现吗?
窃以为,我会继续写C的。

nero | June 14, 2011 12:19 AM

不是很理解,为什么这里留言也有审核系统吗?看来美帝也不自由啊。
我只是路过,说说自己的意见。
附:
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf
第84页
The integer promotions are performed on each of the operands. The type of the result is
that of the promoted left operand. If the value of the right operand is negative oris
greater than or equal to the width of the promoted left operand, the behavior is undefined.

Xin LI replied to comment from nero | June 14, 2011 12:22 AM

C标准是有明确的规定,但是我不知道有什么理由不去研究一下为什么会发生这样的情况,以及标准为什么要说“the behavior is undefined”,因为这个坑今天有人跳了,以后仍然会有人跳,不求甚解是不对的。

Xin LI replied to comment from nero | June 14, 2011 12:27 AM

因为垃圾评论太多了,我没精力去做一个语义识别系统来判断是否广告。如果您用 OpenID 登录发表评论,只要第一次不是广告,我就会做 trust 处理,如果匿名评论就只好先审后发了,抱歉。

Yang | June 14, 2011 1:05 AM

感谢分享这个知识。平时很少注意到这点。但是针对评论,忍不住想写两句自己的想法。no offense。只是觉得有时候或许更平和的态度有助降低风险。

1,C规范并没有假定开发人员具备怎样的知识。
2,不研究具体实现的人一样可以写出至少无错的C程序。任何时候,无错是底线。尤其对于C。
3,不去了解一个运算符使用上的限制,不去了解undefined behavior,多数情况下比不去了解具体实现更危险。另外个人觉得,了解规范比了解具体实现,在做开发的时候更efficient.

Xin LI replied to comment from Yang | June 14, 2011 6:29 PM

我的观点是,很多时候从开发效率来说 C 并不是一个最“快”的语言,因为很多东西用 C 去写要麻烦得多,因此没必要凡事都拿 C 去做,而只用 C 去做那些用它来做最经济的模块,或者不得不用 C 去做的事情。写一个 C 程序很容易,但在现实的应用场景中 C 总是用来做一些“重要”的事情,比如希望用它来改进现有程序的性能、减少开销,等等,这些无一例外地要求开发人员对计算机 *如何* 去完成计算有深入的理解。

我完全同意了解规范要比了解具体实现更为高效,特别是在学习任何东西的时候。我只是非常不认可遇到问题之后简单地把它绕过去这样浅尝辄止的人生态度。

一个人走出学校,离开了做学问的环境,总要保持那么一点点好奇心,而不是看到书本上怎么写的就毫无保留地照做(这里还不说 C 标准很多地方并不解释为什么要那样做)。遇到一个现象没有好奇心、不问几个为什么的人生是很可怕的。

以上。

summertown | June 15, 2011 4:44 AM

这个同时也解释了为什么在左移或者右移次数为负数的情况下,结果会那么奇特。

在MIPS平台上(AR7240)的测试显示,位移运算和x86系统类似。
在AMD64平台上也有类似的结果~

zhywang | June 16, 2011 1:04 AM

这个行为也被Java忠实地继承下来了。
对32位的数据进行超过31的移位操作确实没有意义。

tianwei | June 17, 2011 7:32 AM

感谢delphij!真受教了!胡乱写了很长时间的C没有想到一直是编译器在帮着防止此类怪异的结果:)
看到此文后我在x86平台上试验确实是这样的..让我大叹不止…
我这两天断续在一台StrongARM的cpu上面尝试写了一下(立即数我改为0xa5a5a5a5),
发现:
1.GCC如果发现a»=32;会有一个Warning:right shift count >= width of type
编译是成功的,结果直接是0,用反编译看,也是直接放入了#0. 这个无论在gcc上加不加-O? 优化开关都是这样,都是直接放0.我的gcc是3.3.5
2.于是我尝试用二进制直接把一个编译好的a»=31的a.out修改为a»=32的.尝试了很多次,
发现了立即数的排列(真是"精简指令"啊,才4bit.汗一个),终于让它从汇编层lsr 了#32,结果是正确的0. 这个和x86平台不同.
3.查了一下这个老ARM的指令,发现说它允许1-32的移位,从我所做的估计来看,指令中4bits:0001-1111,代表1-31,而0000代表的正是32(也就是说是貌似0的移位反而是32的移位,不知我这个说法是否准确). 虽然gcc编译不会编译成移位32,但是汇编确实是支持#32位移位的.
以上只是在本机试验的结果,本人才疏学浅,错漏难免,仅供参考.
ps:能从您的博客学到东西,真是快乐之事!

Haohui | July 10, 2011 3:17 PM

This is defined as “undefined” in C standard