51

我需要找到大于或等于给定值的两个的最小幂。到目前为止，我有这个：

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

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

它工作正常，但感觉有点幼稚。有没有更好的算法来解决这个问题？

编辑。有一些很好的汇编程序建议，所以我将这些标签添加到问题中。

4

16 回答 16

67

这是我最喜欢的。除了初始检查它是​​否无效（<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;
}
于 2008-12-13T10:08:55.313 回答
21 
ceil(log2(value))

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

于 2008-12-13T08:18:35.957 回答
12

在 Intel 硬件上，BSR 指令接近您想要的 - 它找到最高有效位。如果您需要更精确，您可以想知道剩余位是否精确为零。我倾向于假设其他 CPU 会有类似 BSR 的东西——这是一个你想要回答的问题以标准化一个数字。如果您的数字超过 32 位，那么您将从最重要的 DWORD 进行扫描，以找到第一个设置了ANY位的 DWORD。Edsger Dijkstra 可能会说，上述“算法”假设您的计算机使用二进制数字，而从他那种崇高的“算法”角度来看，您应该考虑图灵机或其他东西——显然我的风格更务实。

于 2008-12-13T08:39:43.607 回答
12

本着 Quake II 的 0x5f3759df 和 Bit Twiddling Hacks 的 IEEE 版本的精神 - 这个解决方案达到了双精度以提取指数作为计算 floor(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%（6 秒，我的笔记本电脑上的 n=1..2^31-2 为 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 
  }
}
于 2009-01-20T19:35:11.570 回答
7

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

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));
}
于 2013-03-18T14:26:52.407 回答
6

您的实现并不幼稚，它实际上是合乎逻辑的，除了它是错误的 - 它对于大于 1/2 最大整数大小的数字返回负数。

假设您可以将数字限制在 0 到 2^30 的范围内（对于 32 位整数），它会工作得很好，并且比任何涉及对数的数学函数都要快得多。

无符号整数会更好，但最终会出现无限循环（对于大于 2^31 的数字），因为使用 << 运算符永远无法达到 2^32。

于 2008-12-13T08:24:14.387 回答
6

pow（2，ceil（log2（值））；

log2(value) = log(value) / log(2);

于 2013-04-01T22:37:29.040 回答
4

Bit Twiddling Hacks页面上提供了对密切相关问题的可能解决方案（即向下舍入而不是向上舍入）的探索，其中许多解决方案比简单方法快得多，这是进行各种优化的绝佳资源你正在寻找。最快的解决方案是使用具有 256 个条目的查找表，这将总操作计数从天真的方法的平均 62（通过类似的操作计数方法）减少到大约 7。使这些解决方案适应您的问题是一个比较和增量的问题。

于 2008-12-17T01:42:35.877 回答
3

您并没有真正说出“更好的算法”是什么意思，但是由于您提出的那个非常清楚（如果有些缺陷），我假设您追求的是更有效的算法。

Larry Gritz 给出了可能是最有效的 c/c++ 算法，没有查找表的开销，并且在大多数情况下就足够了（有关类似算法，请参见http://www.hackersdelight.org）。

正如其他地方所提到的，如今大多数 CPU 都有机器指令来计算前导零的数量（或等效地返回 ms 设置位），但是它们的使用是不可移植的，并且 - 在大多数情况下 - 不值得付出努力。

然而，大多数编译器具有“内在”功能，允许使用机器指令，但以更可移植的方式。

Microsoft C++ 有 _BitScanReverse() 并且 gcc 提供 __builtin_clz() 来有效地完成大部分工作。

于 2008-12-13T13:10:18.333 回答
3

递归模板版本如何生成编译常量：

template<uint32_t A, uint8_t B = 16>
struct Pow2RoundDown { enum{ value = Pow2RoundDown<(A | (A >> B)), B/2>::value }; };
template<uint32_t A>
struct Pow2RoundDown<A, 1> { enum{ value = (A | (A >> 1)) - ((A | (A >> 1)) >> 1) }; };

template<uint32_t A, uint8_t B = 16>
struct Pow2RoundUp { enum{ value = Pow2RoundUp<((B == 16 ? (A-1) : A) | ((B == 16 ? (A-1) : A) >> B)), B/2>::value }; };
template<uint32_t A >
struct Pow2RoundUp<A, 1> { enum{ value = ((A | (A >> 1)) + 1) }; };

可以这样使用：

Pow2RoundDown<3221>::value, Pow2RoundUp<3221>::value
于 2014-02-18T01:33:01.350 回答
1

下面的代码反复去除最低位，直到数字是 2 的幂，然后将结果加倍，除非数字是 2 的幂。它的优点是运行时间与设置的位数成正比。不幸的是，它的缺点是在几乎所有情况下都需要比问题中的代码或汇编建议更多的指令。我只是为了完整性才包括它。

int nextPow(int x) {
  int y = x
  while (x &= (x^(~x+1))) 
    y = x << 1;
  return y
}
于 2008-12-13T09:34:22.653 回答
1

我知道这是投反对票，但如果数字足够小（如 8 位或 16 位），直接查找可能是最快的。

// fill in the table
unsigned short tab[65536];
unsigned short bit = tab[i];

通过先执行高位字然后执行低位字，可以将其扩展到 32 位。

//
unsigned long bitHigh = ((unsigned long)tab[(unsigned short)(i >> 16)]) << 16;
unsigned long bitLow = 0;
if (bitHigh == 0){
    bitLow = tab[(unsigned short)(i & 0xffff)];
}
unsigned long answer = bitHigh | bitLow;

shift-or 方法可能并不好，但也许可以扩展到更大的字数。

（实际上，这给出了最高的 1 位。您必须将其左移 1 才能获得下一个更高的 2 幂。）

于 2008-12-17T01:57:07.063 回答
1

我的版本相同：

int pwr2Test(size_t x) {
    return (x & (x - 1))? 0 : 1; 
}

size_t pwr2Floor(size_t x) {
    // A lookup table for rounding up 4 bit numbers to
    // the nearest power of 2.
    static const unsigned char pwr2lut[] = {
        0x00, 0x01, 0x02, 0x02,     //  0,  1,  2,  3
        0x04, 0x04, 0x04, 0x04,     //  4,  5,  6,  7
        0x08, 0x08, 0x08, 0x08,     //  8,  9, 10, 11
        0x08, 0x08, 0x08, 0x08      // 12, 13, 14, 15
    };

    size_t pwr2 = 0;                // The return value
    unsigned int i = 0;             // The nybble interator

    for( i = 0; x != 0; ++i ) {     // Iterate through nybbles
        pwr2 = pwr2lut[x & 0x0f];   // rounding up to powers of 2.
        x >>= 4;                    // (i - 1) will contain the
    }                               // highest non-zero nybble index.

    i = i? (i - 1) : i;
    pwr2 <<= (i * 4);
    return pwr2; 
}

size_t pwr2Size(size_t x) {
    if( pwr2Test(x) ) { return x; }
    return pwr2Floor(x) * 2; 
 }
于 2010-05-12T23:47:53.163 回答
0

我喜欢这种转变。

我会接受的

    int bufferPow = 1;
    while ( bufferPow<bufferSize && bufferPow>0) bufferPow <<= 1;

这样循环总是会终止，并且 && 之后的部分几乎不会被评估。而且我不认为两行值得一个函数调用。你也可以根据自己的判断做长或短，而且可读性很强。（如果 bufferPow 变为负数，希望您的主代码能够快速退出。）

通常你在算法开始时只计算一次 2 次方，所以无论如何优化都是愚蠢的。但是，如果有足够无聊的人会关心速度比赛......使用上面的例子和 255 256 257 .. 4195 4196 4197

于 2012-08-20T19:11:42.460 回答
0

通过除以 2 的对数，可以将任意对数函数转换为以 2 为底的对数：

$ /usr/local/pypy-1.9/bin/pypy
Python 2.7.2 (341e1e3821ff, Jun 07 2012, 15:38:48)
[PyPy 1.9.0 with GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
And now for something completely different: ``<arigato> yes but there is not
much sense if I explain all about today's greatest idea if tomorrow it's
completely outdated''
>>>> import math
>>>> print math.log(65535)/math.log(2)
15.9999779861
>>>> print math.log(65536)/math.log(2)
16.0
>>>>

它当然不会 100% 精确，因为涉及到浮点运算。

于 2012-08-21T17:30:39.893 回答
-2

这很有效，而且速度非常快（在我的 2.66 GHz Intel Core 2 Duo 64 位处理器上）。

#include <iostream>
int main(void) {
    int testinput,counter;
    std::cin >> testinput;
    while (testinput > 1) {
        testinput = testinput >> 1;
        counter++;
    }
    int finalnum = testinput << counter+1;
    printf("Is %i\n",finalnum);
    return 0;
}

我在 3、6 和 65496 上对其进行了测试，并给出了正确答案（4、8 和 65536）。

抱歉，如果这看起来有点神秘，我在写作之前受到了几个小时的Doom的影响。:)

于 2011-08-20T18:16:12.333 回答