language-agnostic - 位移是 O(1) 还是 O(n)？

Question

是否轮类操作O(1)或 O(n) ?

计算机通常需要更多的操作来移动 31 个位置而不是移动 1 个位置是否有意义？

或者移位所需的操作次数是有意义吗？常数 不管我们需要转移多少地方？

PS:想知道硬件是否是合适的标签..

Answer 1

某些指令集限制为每条指令移位一位。并且某些指令集允许您指定在一条指令中移动的任意数量的位，这在现代处理器上通常需要一个时钟周期(现代是一个故意模糊的词)。见 dan04's answer关于桶形移位器，一种在一次操作中移位多于一位的电路。

这一切都归结为逻辑算法。结果中的每一位都是基于输入的逻辑函数。对于单个右移，算法将类似于:

如果指令是[右移]且输入的第1位为1，则结果的第0位为1，否则第0位为0。

如果指令是 [右移]，则位 1 = 位 2。

等

但逻辑方程也可以很容易地变成:

如果指令为 [右移] 且操作数为 1，则结果位 0 = 移位输入位 1。

如果数量为 2，则位 0 = 位 2。

等等。

异步逻辑门可以在一个时钟周期内完成所有这些工作。然而，如果您所比较的只是指令的这两种风格，那么单移位确实允许更快的时钟周期和更少的门来解决。或者另一种方法是让它需要更长的时间来稳定，所以指令需要 2 或 3 个时钟或其他什么，逻辑计数到 3 然后锁存结果。

例如，MSP430 只有一位右旋转指令(因为您可以使用另一条指令执行一位移位或左旋转，我将留给读者弄清楚)。

ARM 指令集允许立即数和基于寄存器的多位循环、算术移位和逻辑移位。我认为只有一个实际的旋转指令，另一个是别名，因为向左旋转 1 与向右旋转 32 相同，您只需要一个单向桶形移位器来实现多位旋转。

x86 中的 SHL 允许每条指令多于一位，但它过去需要多于一个时钟。

等等，您可以轻松检查那里的任何说明。

你的问题的答案是它不是固定的。有时是一个操作，一个周期，一条指令。有时是一条指令多个时钟周期。有时是多条指令，多个时钟周期。

编译器经常针对这类事情进行优化。假设您有一个带有交换字节指令的 16 位寄存器指令集和带有立即数的 AND 指令，但只有一个位移位。您可能认为移位 8 位需要 8 个移位指令周期，但您可以只交换字节(一条指令)，然后将下半部分与零(这可能需要两条指令，或者可能是两个字的可变字长指令，或者它可能编码成一条指令)所以它只需要 2 或 3 个指令/时钟周期而不是 8 个。对于 9 位的移位，您可以做同样的事情并添加一个移位，使其成为 9 个时钟 vs 3 个或 4 个此外，在某些体系结构上，乘以 256 比移位以 8 等更快，每个指令集都有其自身的局限性和技巧。

甚至大多数指令集都提供多位或最大限制为单位的情况也不是这样。属于“计算机”类别的处理器，如 X86、ARM、PowerPC 和 MIPS，将倾向于一种操作来转换。扩展到所有处理器，但不一定是今天常用的“计算机”，它以另一种方式移动，我会说其中更多的是单位而不是多位，因此需要多个操作来执行多位移动。