哪个更快:x << 1或x << 10？

Question

我不想优化任何东西,我发誓,我只想出于好奇而问这个问题.我知道,在大多数硬件有位移(例如的组件的命令shl,shr),它是一个命令.但是,你转移了多少比特(纳秒级,或CPU技巧)是否重要？换句话说,在任何CPU上是否更快？

x << 1;

和

x << 10;

请不要因为这个问题而恨我.:)

Answer 1

可能取决于CPU.

但是,所有现代CPU(x86,ARM)都使用"桶形移位器" - 一种专门设计用于在恒定时间内执行任意移位的硬件模块.

所以底线是......不.没有不同.

Answer 2

一些嵌入式处理器仅具有"逐个移位"指令.在这样的处理器上,编译器将x << 3变为((x << 1) << 1) << 1.

我认为摩托罗拉MC68HCxx是受此限制的更受欢迎的家族之一.幸运的是,这种架构现在非常罕见,现在大多数都包括一个具有可变移位尺寸的桶形移位器.

具有许多现代衍生产品的英特尔8051也无法移位任意数量的位.

Answer 3

有很多案例.

1. 许多高速MPU具有桶形移位器,类似多路复用器的电子电路,可在恒定时间内进行任何移位.

2. 如果MPU只有1位移位x << 10通常会更慢,因为它主要通过10次移位或2次移位的字节复制完成.

3. 但已知的常见情况下x << 10甚至会更快比x << 1.如果x是16位,则只需要低6位(所有其他都将被移出),因此MPU只需要加载低位字节,因此只x << 10需要对8位存储器进行单个访问周期,同时需要两个访问周期.如果访问周期比移位慢(并清除低位字节),x << 10则会更快.这可能适用于具有快速板载程序ROM的微控制器,同时访问慢速外部数据RAM.

4. 作为案例3的补充,编译器可能关心有效位的数量x << 10并优化对较低宽度的操作的进一步操作,例如将16x16乘法替换为16x8乘法(因为低位字节始终为零).

注意,一些微控制器根本没有左移指令,add x,x而是使用它们.

Answer 4

在ARM上,这可以作为另一条指令的副作用来完成.所以潜在地,它们中的任何一个都没有延迟.

Answer 5

这是我最喜欢的CPU,其中x<<2需要的时间是x<<1:)的两倍

Answer 6

这取决于CPU和编译器.即使底层CPU具有桶形移位器的任意位移,这只有在编译器利用该资源时才会发生.

请记住,在数据位中移动宽度以外的任何内容都是C和C++中的"未定义行为".签名数据的右移也是"实现定义的".而不是过分关注速度,关注你在不同的实现上得到相同的答案.

引用ANSI C第3.3.7节:

3.3.7按位移位运算符

句法

      shift-expression:
              additive-expression
              shift-expression <<  additive-expression
              shift-expression >>  additive-expression

约束

每个操作数应具有整数类型.

语义

对每个操作数执行整体促销.结果的类型是提升的左操作数的类型.如果右操作数的值为负或大于或等于提升的左操作数的位宽,则行为未定义.

E1 << E2的结果是E1左移E2位位置; 腾出的位用零填充.如果E1具有无符号类型,则结果的值为E1乘以数量,2增加到功率E2,如果E1的类型为无符号长,则减少模ULONG_MAX + 1,否则为UINT_MAX + 1.(常量ULONG_MAX和UINT_MAX在标题中定义.)

E1 >> E2的结果是E1右移E2位位置.如果E1具有无符号类型或者E1具有有符号类型和非负值,则结果的值是E1除以数量的商的整数部分,2增加到幂E2.如果E1具有带符号类型和负值,则结果值是实现定义的.

所以:

x = y << z;

"<<":y×2 ^z(如果发生溢出则不确定);

x = y >> z;

">>":为signed定义的实现(通常是算术移位的结果:y/2 ^z).

Answer 7

可以想象,在8位处理器上,x<<1实际上可能比16位值慢得多x<<10.

例如,合理的翻译x<<1可能是:

byte1 = (byte1 << 1) | (byte2 >> 7)
byte2 = (byte2 << 1)

而x<<10更简单:

byte1 = (byte2 << 2)
byte2 = 0

注意如何x<<1更频繁地转移,甚至更远x<<10.此外,结果x<<10不依赖于byte1的内容.这可以另外加速操作.

Answer 8

在几代英特尔CPU上(P2或P3？不是AMD,如果我没记错的话),比特移位操作非常慢.Bitshift by 1 bit应该总是很快,因为它只能使用加法.要考虑的另一个问题是,通过恒定位数的位移是否比可变长度位移更快.即使操作码的速度相同,在x86上,位移的非常量右手操作数也必须占用CL寄存器,这会对寄存器分配施加额外的约束,并且可能会使程序慢下来.