用于找到大于或等于给定值的2的最小幂的算法

Question

我需要找到大于或等于给定值的2的最小幂.到目前为止,我有这个:

int value = 3221; // 3221 is just an example, could be any number
int result = 1;

while (result < value) result <<= 1;

它工作正常,但感觉有点幼稚.这个问题有更好的算法吗？

编辑.有一些很好的Assembler建议,所以我将这些标签添加到问题中.

Answer 1

这是我的最爱.除了初始检查它是​​否无效(<0,如果你知道你只传入> = 0个数字就可以跳过),它没有循环或条件,因此将胜过大多数其他方法.这类似于埃里克森的回答,但我认为我在开始时递减x并在结尾加1并不像他的回答那么尴尬(并且也避免了最后的条件).

/// Round up to next higher power of 2 (return x if it's already a power
/// of 2).
inline int
pow2roundup (int x)
{
    if (x < 0)
        return 0;
    --x;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x+1;
}

Answer 2

ceil(log2(value))

ilog2()可以在3个asm指令中计算,例如,http://www.asterisk.org/doxygen/1.4/log2comp_8h-source.html

Answer 3

本着Quake II的0x5f3759df和Bit Twiddling Hacks的IEEE版本的精神 - 这个解决方案达到了一个双重提取指数作为计算楼层的方法(lg2(n)).它比公认的解决方案快一点,比Bit Twiddling IEEE版本快得多,因为它避免了浮点数学.在编码时,它假设double是一个小型端机上的真正的*8 IEEE浮点数.

int nextPow2(int n) 
{ 
    if ( n <= 1 ) return n;
    double d = n-1; 
    return 1 << ((((int*)&d)[1]>>20)-1022); 
} 

编辑:在同事的帮助下添加优化的x86程序集版本.速度增加4%,但仍然比bsr版本慢约50%(对于n = 1..2 ^ 31-2,我的笔记本电脑上的6秒与4相比).

int nextPow2(int n) 
{ 
    if ( n <= 1 ) return n;
    double d;
    n--;
    __asm {
      fild    n 
      mov     eax,4
      fstp    d 
      mov     ecx, dword ptr d[eax]
      sar     ecx,14h 
      rol     eax,cl 
  }
} 

Answer 4

在英特尔硬件上,BSR指令接近您想要的 - 它找到最重要的设置位.如果你需要更精确,那么你可以想知道其余的位是否正好为零.我倾向于认为其他CPU会有像BSR这样的东西 - 这是一个你想要回答的问题,以规范数字.如果您的数字超过32位,那么您将从最重要的DWORD进行扫描,以找到设置了任意位的第一个DWORD .Edsger Dijkstra可能会说上面的"算法"假设你的计算机使用二进制数字,而从他那种崇高的"算法"角度来看,你应该考虑一下图灵机或其他东西 - 显然我是更务实的风格.

Answer 5

你的实现并不天真,它实际上是逻辑的,除了它是错误的 - 它返回一个负数,大于最大整数大小的1/2.

假设您可以将数字限制在0到2 ^ 30(对于32位整数)的范围内,它可以正常工作,并且比任何涉及对数的数学函数快得多.

无符号整数可以更好地工作,但你最终会得到一个无限循环(对于大于2 ^ 31的数字),因为你永远不会使用<<运算符达到2 ^ 32.

Answer 6

这是位移位技术的模板版本。

template<typename T> T next_power2(T value)
{
    --value;
    for(size_t i = 1; i < sizeof(T) * CHAR_BIT; i*=2)
        value |= value >> i;
    return value+1;
}

由于循环只使用常量，它会被编译器扁平化。（我检查过）该功能也是面向未来的。

这是使用 __builtin_clz 的一个。（也是未来证明）

template<typename T> T next_power2(T value)
{
    return 1 << ((sizeof(T) * CHAR_BIT) - __builtin_clz(value-1));
}

Answer 7

pow（2，ceil（log2（value））;

log2（值）= log（值）/ log（2）;