Pac*_*ier 30 language-agnostic hardware cpu big-o bit-shift
轮班操作O(1)还是O(n)？
计算机通常需要更多操作来转移31个位置而不是移动1个位置是否有意义？
或者有意义的是,无论我们需要移动多少个位置,移位所需的操作数量都是恒定的？
PS:想知道硬件是否是合适的标签..
old*_*mer 13
一些指令集限于每条指令一位移位.并且一些指令集允许您指定在一条指令中移位的任意位数,这通常在现代处理器上需要一个时钟周期(现代是有意模糊的字).请参阅dan04关于桶形移位器的答案,这是一种在一次操作中移位多于一位的电路.
这一切都归结为逻辑算法.结果中的每个位都是基于输入的逻辑功能.对于单个右移,算法将类似于:
但逻辑方程可以很容易:
逻辑门是异步的,可以在一个时钟周期内完成所有这些工作.然而,如果您要比较的是这两种指令,那么单一移位确实可以实现更快的时钟周期和更少的门限.或者替代方案是需要更长时间才能解决,因此指令需要2或3个时钟或其他任何时间,逻辑计数到3然后锁存结果.
例如,MSP430只有单位向右旋转指令(因为你可以执行单个位移或向左旋转另一个指令,我将留给读者去弄清楚).
ARM指令集允许基于立即和寄存器的多位旋转,算术移位和逻辑移位.我认为只有一个实际的旋转指令而另一个是别名,因为左旋转1与右旋转32相同,你只需要一个方向的桶形移位器来实现多位旋转.
x86中的SHL允许每条指令多于一位,但它过去需要多个时钟.
等等,您可以轻松地检查那里的任何指令集.
你的问题的答案是它没有修复.有时它是一个操作,一个循环,一个指令.有时它是一个指令多个时钟周期.有时它是多个指令,多个时钟周期.
编译器经常针对这些事情进行优化.假设您有一个带有交换字节指令的16位寄存器指令集和带有立即数的AND指令,但只有一个位移位.您可能认为移位8位需要8个移位指令周期,但您可以只交换字节(一条指令)然后将下半部分与零交叉(可能需要两条指令,或者可能是两个字的可变字长指令,或者它可能编码为单个指令)所以它只需要2或3个指令/时钟周期而不是8个.对于9位的移位,你可以做同样的事情并添加一个移位,使其成为9个时钟对3或4个此外,在某些体系结构中,乘以256比移动8等更快等等.每个指令集都有其自身的局限性和技巧.
甚至不是大多数指令集对单个位提供多位或大多数限制的情况.属于"计算机"类别的处理器,如X86,ARM,PowerPC和MIPS,将倾向于一个转换操作.扩展到所有处理器但不一定是今天常用的"计算机",并且它转向另一种方式,我会说它们更多是单比特而不是多比特,因此需要多个操作来执行多比特移位.
如前所述,桶形移位器可以在恒定时间内将操作数移位任意距离.但是,桶形移位器在CPU芯片上占用相当大的空间,因此它们不包含在所有CPU设计中.
只是一个相当著名的例子,英特尔奔腾III包括了桶式移位器-但奔腾IV确实没有.为奔腾III编写的代码假设有一个桶形移位器,有时在Pentium IV上放慢了相当多的速度.我有一些加密代码(包括许多移位和旋转),在1.2 GHz奔腾III上运行速度比在2.8 GHz奔腾IV上快4倍.
实际上每个当前处理器上的位移是O(1).
例如,看看x86"shrw"指令.第一个操作数(在AT&T语法中)是要移位的位数.编译器如何实现移位取决于编译器,但是当处理器一次性移位N位时,将移位置于循环中将是愚蠢的.
附录:回复:"他们需要更多的操作才能向左移31？" 有不同类型的移位(如果您想知道为什么,请考虑如何处理从寄存器移出的位),但大多数处理器可以执行与GPR可以存储的位数相同的单指令移位.要在32位寄存器上执行40位移位,需要在多个寄存器之间进行移位(假设在2个32位寄存器中存储了64位数),这在我知道的每个处理器上都需要更多指令.它仍然是O(1),可能不是1个时钟.作为一个有趣的侧面说明,Pentium IV处理器的位移速度非常慢.这具有讽刺意味,因为英特尔历来建议通过位移优化^ 2除法和乘法.如果感兴趣,请参阅:此PDF和Google了解更多信息.
| 归档时间： |
|
| 查看次数： |
10770 次 |
| 最近记录： |