一个奇怪的移位计算结果

标签: *nix and Win32 Kernel | 发表时间:2011-07-11 06:17 | 作者:Xin LI Shu. Wang
出处:https://blog.delphij.net/

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

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

相关 [移位 计算 结果] 推荐:

一个奇怪的移位计算结果

- Shu. Wang - delphij&#39;s Chaos
今天 强迫症 朱小瘦同学提到一个非常有意思的问题,一个32bit的无符号整数算术右移32个bit应该得多少. 我们知道算术右移一个bit相当于除2,所以一个32bit无符号整数除以 2^32,理论上,应该得0. 测试显示在 x86 系统上,一个32bit无符号整数算术右移32个bit之后得到的是原数.

Spark的速度快是以丧失计算结果正确性为代价的

- - Changming
但是它不保证它算出的值是对的,哪怕你要做的只是简单的整数累加. Spark最著名的一篇论文是:《Spark: Cluster Computing with Working Sets》. 当你读它的时候你需要明白:文中代码不保证计算结果是正确的. 具体来说,它的Logistic Regression的代码在map阶段用到了accumulator.

oracle license计算

- Fenng - eagle&#39;s home
Oracle license的计算是基于CPU core的. 用core的数目乘以一个系数core factor就可以得到所需的oracle license的数目. 对于不同的CPU,core factor是不一样的,可以从oracle提供的这张列表中查到 Oracle Processor Core Factor Table.

理解云计算

- 车东 - oneoo&#39;s 私家花园
  现在互联网最热门的关键字“云计算”,大大小小的公司纷纷加入到这块领域. 简单来说,目前的“云计算”主要分为:SaaS、PaaS和IaaS三大类.   其中SaaS云计算,为软件即服务的概念. 把传统客户端软件部署在互联网上,用户只需要一个浏览器就可以使用到软件的模式. 其实早在2000年就已经有B/S结构的软件服务,与现在所说的SaaS云计算相近,但此前的B/S结构软件服务,数据库等服务端是需要用户自行部署的,而非由软件提供商进行统一部署.

钢琴计算器

- 丑秋 - 专利之家-设计发明与创意商机
这款太阳能计算器别出心裁地设计了黑白相间的按键,看起来像钢琴的琴键一样,十分有趣. 或许这样的计算器可以给枯燥的计算工作增添一点乐趣,让它不再乏味.

10问云计算

- - 《商业价值》杂志
与数百位关注和实践云计算的CIO们共同解读云计算热点问题. 被视作IT界第三次革命的云计算,已经从炙手可热的概念逐渐走向了实际应用. 2011年8-11月, ITValue社区联合英特尔公司,与数百位关注和实践云计算的CIO们一起展开深入探讨,话题涉及云计算的商业价值、安全性、开放性、高效性、简单性等方面.

Jeff Patton谈结果导向

- - InfoQ - 促进软件开发领域知识与创新的传播
Jeff Patton在2019年敏捷希腊峰会的闭幕主题演讲中说,我们需要关注结果,调整我们的思维方式和流程,从而不断发布产品和服务的小更改. Patton表示,我们应该付费学习,而不是仅仅构建“潜在的可交付软件”. 他认为,我们必须承认我们经常会失败——我们必须让谦逊成为流程的一部分. 然后,我们可以把学习纳入流程:.

云计算的困局

- Star Ocean - It Talks--上海魏武挥的博客
有个媒体朋友打电话咨询我一个事. 说在江浙一带,有一位搞国际货运代理的民营企业家,想利用云计算来整合各种资源,比如运输车队、仓库、集装箱乃至货船. 这些资源的调配信息对任何一家从事外贸的企业都很重要,如果将这些信息放在所谓的“云”上,并加以运算,这些企业再以各种设备联入这个“云”,这位企业家觉得是一个很有前途的买卖.

开源云计算ERP ErpCore

- Le - 开源中国社区最新软件
  ErpCore是一套强大的云计算ERP开发框架,集数据库设计、软件建模、模型自动生成、界面可视化设计、业务流可自定义、全自动生成用户所需系统于一体. 在此框架上扩展出所有行业的业务系统,它让软件工程师从“建模——写代码——测试”所有繁琐重复的工作变为全自动化生成,大大简化了企业软件的开发时间和成本;同时,使用该框架扩展的所有业务子系统能够无缝连接进行数据共享,这也是云计算ERP的实现基础,杜绝了传统ERP的子.

异构计算的挑战

- Guancheng(冠诚) - 技术改变世界 创新驱动中国 - 《程序员》官网
进入新世纪之后,软件研发面临并行编程的技术变革、硬件架构面临异构计算的挑战,这些改变是否意味着新的机遇,取决于能否建立良好的生态链. 2004年12月,C++标准化委员会主席、著名程序员Herb Sutter在自己的个人网站发表了一篇影响深远的文章《免费午餐已经结束》(中文版发表于本刊2006年11月期).