在AVR中，逻辑右移2的幂次方是否更快速？

Question

我想知道进行逻辑右移是否更快，当将位移数设置为2的幂时。

例如，是否

myUnsigned >> 4

比任何更快

myUnsigned >> 3

我知道大家第一反应会告诉我不要担心这些微小的事情，使用正确的算法和集合来减少数量级才是最重要的。我完全同意你们的看法，但我真的在尝试挤出嵌入式芯片（ATMega328）的所有性能 - 我刚刚通过用位移替换除法获得了一个值得欢呼的性能提升，所以我向你保证这确实很重要。

- Will

---

你为什么不测量一下自己呢？ - Tadeusz A. Kadłubowski

谁在意 x >> 4 比 x >> 3 更快？它们有不同的语义，因此哪个更快并不重要。无论如何，我从未遇到过任何一个体系结构，其中位移操作符的右操作数会对性能产生影响。 - fredoverflow

在ATMega上，位移指令没有“要移位的位数”操作数。关于x >> 4和x >> 3的区别 - 也许原帖作者在这方面有一些自由（例如进行定点算术并具有在小数部分有多大的余地） - Martin B

除法因其极高的成本而闻名（在现代桌面处理器上大约需要40个周期，可以在一个周期内执行多个移位操作，更糟糕的是，在嵌入式芯片上实现时，它是以软件形式实现的，雪上加霜）。 - Pascal Cuoq

@FredOverflow：我猜他正在尝试实现某种固定点整数。在这种情况下，只要精度/范围对应应用程序仍然足够好，他可以通过更改小数位数来在x >> 4和x >> 3之间切换。 - Niki

Answer 1

我们来看看数据手册：

http://atmel.com/dyn/resources/prod_documents/8271S.pdf

就我所见，ASR（算术右移）总是向右移动一位，不能确定要移动的位数；它需要一个周期来执行。因此，向右移动 n 位将需要 n 个周期。二的幂与任何其他数字的行为都是相同的。

- Martin B

---

谢谢！我必须用整数替换浮点数，但是为了保持精度，这个整数必须被乘以更大的数。我正在尝试找到一个理想的系数，以便我花费最少的时间将整数压缩回未乘以的大小。 - Will

Answer 2

在AVR指令集中，算术右移和左移一次只发生在一个位上。因此，对于这个特定的微控制器，向右移动>> n意味着编译器实际上会进行n个单独的asr操作，我猜>>3比>>4快一点。

顺便说一下，这使得AVR变得相当不寻常。

- Crashworks

---

这并不罕见。大多数（如果不是全部）8位微控制器都没有桶移位器，必须逐位移动。 - phuclv

8086和80286也没有移位器，因此移位距离越远，速度就越慢。 - phuclv

Answer 3

事实上，ATMega没有移位寄存器，就像大多数（如果不是全部）其他8位MCU一样。因此，它每次只能向右移1位，而不是像更强大的CPU那样可以任意移位。因此，理论上移4位比移3位慢多了

然而，ATMega 确实有一个交换半字指令，所以实际上x >> 4比x >> 3更快

假设x是一个uint8_t，那么x >>= 3由3次右移操作实现

x >>= 1;
x >>= 1;
x >>= 1;

而 x >>= 4 只需要进行一次交换和一次位清除操作。

swap(x);    // swap the top and bottom nibbles AB <-> BA
x &= 0x0f;

或者

x &= 0xf0;
swap(x);

---

对于更大的交叉寄存器移位，也有各种优化方法。

使用一个由低部分y0和高部分y1组成的uint16_t变量y，那么y >> 8就是简单的。

y0 = y1;
y1 = 0;

同样地，y >> 9 可以被优化为

y0 = y1 >> 1;
y1 = 0;

因此，它比在char上进行3次移位更快。

---

总之，移位时间取决于移位距离，但对于更长或非2的幂值来说不一定更慢。通常，在8位字符内进行移位最多需要3条指令。

这里是编译器浏览器的一些演示

• A right shift by 4 is achieved by a swap and an and like above

    swap r24
    andi r24,lo8(15)
  

• A right shift by 3 has to be done with 3 instructions

    lsr r24
    lsr r24
    lsr r24
  

左移操作也以相同方式进行了优化

另请参阅 哪个更快：x<<1还是x<<10？

- phuclv

---

哦，我不知道AVR中的x << 3是通过3次移位来实现的。你确定AVR有一个专门用于单比特移位的操作符吗？在ARM上，swap和<<3需要相同的时间（1个周期）。 - Mixaz

我所知道的8位微控制器都没有移位寄存器，因此每个周期只能移动1位。只需查找AVR、PIC或8051指令集即可。 - phuclv

即使一些16位微控制器仍然需要每次移动1位。ARV的指令集已经在其他答案中发布，请先阅读它。 - phuclv

Answer 4

对于这方面的信息，您需要查阅处理器文档。即使针对同一指令集，根据型号不同可能会有不同的成本。例如，在真正小的处理器上，向左或向右移动一个单位可能比其他值更快（例如，在某些IA32处理器上的旋转指令中情况就是如此，但这仅因为编译器极少生成此类指令）。

根据http://atmel.com/dyn/resources/prod_documents/8271S.pdf，ATMega328中所有逻辑移位都在一个周期内完成。但是，正如评论中指出的那样，所有逻辑移位都是每次移动一个位。因此，通过n位移的成本是n个周期和n个指令。

- Pascal Cuoq

---

谨慎使用：移位指令总是只移动一位...因此，移动的位数越多，所需时间就越长。 - Martin B

@Martin B 感谢您指出，我应该注意到这一点，信息在同一份PDF中是可用的。 - Pascal Cuoq

ATMega具有半字节交换指令，因此Rd << 4可以实现为SWAP Rd; ORI Rd, 0xF0，并且比Rd << 3更快。 - phuclv

Answer 5

这取决于处理器的构建方式。如果处理器有一个桶旋转功能，它可以在一次操作中移动任意数量的位，但这需要芯片空间和功率预算。最经济实惠的硬件只能向右旋转一次，并具有关于环绕位的选项。下一个是可以左右旋转一次的处理器。我可以想象一个结构，其中包含1位移器、2位移器、4位移器等，这种情况下4可能比3更快。

- Mike Dunlavey

Answer 6

先反汇编，再计时代码。不要被告知你在浪费时间的人打击。你所获得的知识将使你成为处理大公司问题的人选。这个行业中真正幕后知识的人数正在以惊人的速度下降。

听起来像是其他人已经解释了真正的答案，而反汇编会显示单位移指令。因此，4次移位将需要比3次移位多133%的时间，或者3次移位相当于4次移位时间的75%，具体取决于您如何比较这些数字。如果您的测量结果没有反映出这种差异，我建议您继续进行这个实验，直到完全理解执行时间为止。

- old_timer

Answer 7

如果您的目标处理器具有位移指令（这很可能），那么它取决于该指令的硬件实现是否存在在移动2的幂次方位或其他数字位之间存在差异。但是，这种差异不太可能产生影响。

- Bart van Ingen Schenau

Answer 8

恕我直言，在开始谈论性能之前，您应该先开始测量。使用除法编译程序。运行。测量时间。然后使用移位操作重复此过程。

- danatel

---

考虑到他已经通过将div替换为shift来测量性能改进，我认为很明显他一直在运行计时。 - Crashworks

据我所知，关于计算机运算，移位操作比乘法操作快得多是一个广为人知的事实，除法比乘法慢（即使在纸上也是如此）。加法/减法几乎和移位一样快 - 只是在理论上它们使用了更多的晶体管，但这并不重要，因为 CPU 无论如何都可以在单个时钟周期内执行它们。乘法和除法需要更多的时钟周期。 - Mixaz

乘法和除法需要更多的周期，因为它们在后续迭代中内部使用加法/减法。我记得 ARM 规格（至少对于旧版本）指出，除法（我不记得乘法）可能需要不同的时间，因为这个原因。 - Mixaz

Answer 9

用位移替换除法。 这对于负数不是一样的。

char div2 (void)
{
    return (-1) / 2;
    // ldi r24,0
}

char asr1 (void)
{
    return (-1) >> 1;
    //  ldi r24,-1
}

- emacs drives me nuts