6

我想知道按 2 的幂移动时执行逻辑右移是否更快

例如，是

myUnsigned >> 4

任何快于

myUnsigned >> 3

我很感激每个人的第一反应是告诉我，人们不应该担心这样的小事情，它使用正确的算法和集合来减少数量级的重要性。我完全同意你的观点，但我真的想尽我所能从嵌入式芯片（ATMega328）中挤出来——我刚刚获得了值得“哇哦！”的性能转变。通过用位移来代替除法，所以我向你保证，这确实很重要。

4

9 回答 9

21

让我们看一下数据表：

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

据我所知，ASR（算术右移）总是移位一位，不能取移位的位数；执行需要一个周期。因此，右移 n 位需要 n 个周期。2 的幂的行为与任何其他数字相同。

于 2010-09-16T11:55:47.110 回答
5

在AVR 指令集中，算术右移和左移一次发生一位。所以，对于这个特定的微控制器，shifting>> n意味着编译器实际上做了 n 个单独的asr操作，我猜>>3是一个比>>4.

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

于 2010-09-16T11:59:34.473 回答
4

您必须查阅处理器的文档以获取此信息。即使对于给定的指令集，也可能存在不同的成本，具体取决于模型。例如，在一个非常小的处理器上，可以想象移位一个比其他值更快（在某些 IA32 处理器上旋转指令就是这种情况，但这只是因为编译器很少生成该指令）。

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

于 2010-09-16T11:54:04.483 回答
4

事实上，ATMega 没有像大多数（如果不是全部）其他 8 位 MCU 那样的桶式移位器。因此，它每次只能移动 1，而不是像更强大的 CPU 那样的任意值。因此，从理论上讲，移位 4比移位 3 慢

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

假设x一个uint8_tthenx >>= 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);

对于更大的跨寄存器移位，还有各种优化方法

使用由低部分和高部分组成的uint16_t变量，则很简单yy0y1y >> 8

y0 = y1;
y1 = 0;

同样y >> 9可以优化为

y0 = y1 >> 1;
y1 = 0;

因此甚至比在 char 上移动 3 还要快

总之，移位时间根据移位距离而变化，但对于较长或非 2 次幂值，它不一定会变慢。通常，在 8 位字符内移动最多需要 3 条指令

以下是编译器资源管理器的一些演示

  • 右移 4 是通过上面的 aswap和and类似实现的

      swap r24
  andi r24,lo8(15)

  • 右移 3 必须用 3 条指令完成

      lsr r24
  lsr r24
  lsr r24

左移也以相同的方式优化

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

于 2013-07-28T13:06:12.493 回答
2

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

于 2010-09-16T12:08:51.213 回答
2

先反汇编，然后对代码计时。不要因为别人告诉你而气馁，你在浪费时间。您获得的知识将使您成为扑灭大公司火灾的首选人。在这个行业中，真正了解幕后知识的人数正在以惊人的速度下降。

听起来像其他人在这里解释了真正的答案，反汇编会显示单个位移指令。因此，4 个班次将花费 3 个班次所花费时间的 133%，或者 3 个班次是 4 个班次所花费时间的 75%，具体取决于您如何比较数字。你的测量应该反映这种差异，如果他们不这样做，我会继续这个实验，直到你完全理解执行时间。

于 2010-09-16T21:01:21.703 回答
1

如果您的目标处理器有移位指令（这很可能），那么它取决于该指令的硬件实现是否在移位 2 位的幂或移位其他数字之间存在任何差异。但是，这不太可能有所作为。

于 2010-09-16T11:52:46.577 回答
0

恕我直言，在开始测量之前，您甚至不应该开始谈论性能。用除法编译你的程序。跑。测量时间。换档重复。

于 2010-09-16T11:59:06.330 回答
0

用位移替换除法

这与负数不同：

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

char asr1 (void)
{
    return (-1) >> 1;
    //  ldi r24,-1
}
于 2020-01-29T14:39:56.710 回答