我如何使用一位移位有效地向左移位N位? [英] How do I efficiently left-shift by N bits using single-bit shifts?

问题描述

某些MSP430等CPU没有多位移位，而只有一位移位或旋转指令.这使我对昔日"的程序员如何生活感到好奇.实施多位移位，而他们所能做的就是一次移位一位.

Some CPUs like the MSP430 don't have multi-bit shifts, but only single-bit shifts or rotate instructions. This makes me curious about how programmers in the "olden days" implemented multi-bit shifts, when all they could do is shift one bit at a time.

我知道哑巴"的方式，就是这样:

I am aware of a "dumb" way of doing it, which is this:

#include <cstdint>

uint64_t lshift(uint64_t x, uint64_t shift) {
    for (uint64_t i = 0; i < shift; ++i) {
        x <<= 1;
    }
}

有什么方法可以做到这不具有O(n)的复杂性吗?还是至少有一种实现方式，如果我知道编译时的移位(通常是位移位的情况)，该实现是可能的?

Is there any way of doing it which does not have O(n) complexity? Or is there at least an implementation that makes it possible if I know the shift at compile time, which is often the case with bit-shifts?

我的直觉是 x<<(1<<(1<< 1))与 x<<4 ，所以也许可以通过组合这样的移位将其降低到O(log n).

My intuition is that x << (1 << (1 << 1)) is the same as x << 4, so maybe one could reduce it down to O(log n) by combining shifts like that.

我的直觉是错误的，但是其他操作也会产生类似的效果. x<<1 等效于 x + = x ，因此 x + = x，x + = x，x + = x 等效于 x<<4 .乘以2的幂也可以.

My intuition was wrong, but other operations could produce a similar effect. x << 1 is equivalent to x += x so x += x, x += x, x += x is equivalent to x << 4. Multiplication with powers of two would also work.

注意:这里使用C ++只是为了方便起见，我知道总是会有一个左移运算符.我只是不想在MP430装配中考虑这一点.

推荐答案

有关以下代码的背景信息，请在互联网上搜索达夫设备".

For background information about the following code, search the internet for "Duff's Device".

您可以在以下情况下使用 switch 语句:

You could use a switch statement with fall through:

uint32_t Shift_Value(uint32_t value, unsigned int shift_quantity)
{
  switch (shift_quantity)
  {
     case 31:
         value <<= 1;
     case 30:
         value <<= 1;
     case 29:
         value <<= 1;
// ...
     case  1:
         value <<= 1;
   }
   return value;
}

上面的代码很有趣，因为它是进入移位操作数组的跳转表.可以将其与展开 for 循环进行比较，但是它具有执行跳入展开"的适当位置的优点.

The above code is interesting because it is a jump table into an array of shift operations. It can be compared to unrolling a for loop, but it has an advantage that the execution jumps into the appropriate location for the "unrolling".

我以前在嵌入式系统中使用过这种模式来提高性能.

I've used this pattern before in embedded systems to increase performance.

我建议打印出编译器生成的汇编语言并研究汇编语言.:-)

I recommend printing out the compiler generated assembly language and studying the assembly language. :-)

此外，由于没有循环，只有计算和跳转，因此优化可能是O(1).

Also, the optimization could be O(1) since there are no loops, only a calculation and jump.

这篇关于我如何使用一位移位有效地向左移位N位?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！