是移位O(1)还是O(n)? [英] Is bit shifting O(1) or O(n)?

问题描述

是移位操作O(1)或O(n)吗?

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

或者，无论我们需要转移多少个位置，转移所需的操作次数是恒定都有意义吗?

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

解决方案

某些指令集限制为每条指令移位一位.而且某些指令集允许您指定要移入一条指令的任意数量的位，这在现代处理器上通常需要一个时钟周期(现代是故意含糊的字).请参阅 dan04的答案有关桶形移位器的信息，桶形移位器是一种在一次操作中移位多于一位的电路.

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

• 如果指令为[向右移]并且输入的位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个移位指令周期，但是您可以先交换字节(一条指令)，然后将下半部分AND交换为零(这可能需要两条指令，或者可能是两个字的可变字长指令，否则它可能会编码为一条指令)，因此只需要2或3个指令/时钟周期，而不是8个周期.对于9位的移位，您可以执行相同的操作并添加一个移位，使其成为9个时钟，而3或4个时钟此外，在某些体系结构上，乘以256的速度要比移8的速度快，以此类推.等等.每个指令集都有其自身的局限性和技巧.

大多数指令集都不能提供多位或最多只能限制一位的情况.属于计算机"类别的处理器，例如X86，ARM，PowerPC和MIPS，将倾向于一种操作.扩展到所有处理器，但不一定要扩展到今天常用的计算机"，它会转移另一种方式，我想说其中更多的是单比特而不是多比特，因此执行多比特移位需要多次操作.

Are shift operations O(1) or O(n) ?

Does it make sense that computers generally require more operations to shift 31 places instead of shifting 1 place?

Or does it make sense the number of operations required for shifting is constant regardless of how many places we need to shift?

PS: wondering if hardware is an appropriate tag..

解决方案

Some instruction sets are limited to one bit shift per instruction. And some instruction sets allow you to specify any number of bits to shift in one instruction, which usually takes one clock cycle on modern processors (modern being an intentionally vague word). See dan04's answer about a barrel shifter, a circuit that shifts more than one bit in one operation.

It all boils down to the logic algorithm. Each bit in the result is a logic function based on the input. For a single right shift, the algorithm would be something like:

• If the instruction is [shift right] and bit 1 of the input is 1, then bit 0 of the result is 1, else bit 0 is 0.
• If the instruction is [shift right], then bit 1 = bit 2.
• etc.

But the logic equation could just as easily be:

• If the instruction is [shift right] and the amount operand is 1, then result bit 0 = shifted input bit 1.
• if the amount is 2 then bit 0 = bit 2.
• and so on.

The logic gates, being asynchronous, can do all of this in one clock cycle. Yet it is true the single shift allows for a faster clock cycle and less gates to settle, if all you are comparing is these two flavors of an instruction. Or the alternative is making it take longer to settle, so the instruction takes 2 or 3 clocks or whatever, and the logic counts to 3 then latches the result.

The MSP430, for example, only has single bit rotate right instructions (because you can perform a single bit shift or a rotate left with another instruction, which I will leave to the reader to figure out).

The ARM instruction set allows both immediate and register based multi-bit rotates, arithmetic shifts and logical shifts. I think there is only one actual rotate instruction and the other is an alias, because rotate left 1 is the same as a rotate right 32, you only need an one direction barrel shifter to implement a multi bit rotate.

SHL in the x86 allows more than one bit per instruction, but it used to take more than one clock.

and so on, you can easily examine any of the instruction sets out there.

The answer to your question is that it is not fixed. Sometimes it is one operation, one cycle, one instruction. Sometimes it is one instruction multiple clock cycles. Sometimes it is multiple instructions, multiple clock cycles.

The compilers often optimize for these sorts of things. Say you have a 16 bit register instruction set with a swap byte instruction and an AND instruction with immediate, but only a single bit shift. You may think shifting 8 bits would require 8 shift instruction cycles, but you could just swap bytes (one instruction) and then AND the lower half to zeros (which might take two instructions, or might be a variable word length instruction of two words, or it might encode into a single instruction) so it only takes 2 or 3 instruction/clock cycles instead of 8. For a shift of 9 bits, you can do the same thing and add a shift, making it 9 clocks vs 3 or 4. Also, on some architectures, it is faster to multiply by 256 than to shift by 8, etc, etc. Each instruction set has its own limitations and tricks.

It is not even the case that either most instruction sets provide multi bit or most limit to single bit. The processors that fall into the "computer" category, like X86, ARM, PowerPC, and MIPS, would lean toward one operation to shift. Expand to all processors but not necessarily "computers" commonly used today, and it shifts the other way, I would say more of them are single bit than multi bit, so multiple operations are needed to perform a multi-bit shift.

这篇关于是移位O(1)还是O(n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！