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

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

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

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

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

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

1> Larry Gritz..：

---

这是我的最爱.除了初始检查它是​​否无效(<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;
}

---

除了较小的语法差异和初始检查的附加内容之外,您的内容也与Henry S. Warren,Jr.的"Ha​​cker's Delight"中给出的版本几乎完全相同.

---

@Boyan:这个解决方案不可移植,例如,它如何在x64上运行？(它没有)

---

除了@Boojum提到的Hacker's Delight外，在Bit Twiddling Hacks（2001; http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2）中也几乎逐字找到了该解决方案，该解决方案被归功于Sean安德森，甚至更早于1997年由皮特·哈特（Pete Hart）和威廉·刘易斯（William Lewis）撰写的Usenet主题（https://groups.google.com/forum/#!topic/comp.lang.python/xNOq4N-RffU）。

2> jfs..：

---

ceil(log2(value))

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

---

Log-base-2通常将float作为参数.你是说你有一个查找表,每个可能的浮点数都有一个条目？我希望不是......当然,最快的方法是一个包含2 ^ 32个条目的查找表,但这有点内存昂贵.

3> Tony Lee..：

---

本着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 
  }
} 

4> 小智..：

---

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

5> paxdiablo..：

---

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

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

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

6> 小智..：

---

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

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