求大于或等于给定值的2的最小幂的算法

这是我最喜欢的。除了最初检查它是否无效(<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;
}

答案在 Given an integer, how do I find the next largest power of two using bit-twiddling? 对这种常见算法的工作原理进行了一些解释,并给出了几个输入的位模式示例。(该版本使用 unsigned ,这允许避免 x<0 请检查,通常如评论中所讨论的那样更好。)

相同的dec/shift/OR/inc策略可在以下内容中找到:

• http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
• 小亨利·s·沃伦的《黑客的快乐》。

ceil(log2(value))

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

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

本着《雷神之锤II》的0x5f3759df和Bit Twidling Hacks的IEEE版本的精神,该解决方案采用双精度来提取指数作为计算下限(lg2(n))的手段。它比公认的解决方案快一点,也比bit Twidling 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 
  }
} 

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

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));
}

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

假设你可以将数字限制在0到2^30的范围内(对于32位整数),它会工作得很好,而且比任何涉及对数的数学函数都快得多。

无符号整数会更好,但你最终会得到一个无限循环(对于大于2^31的数字),因为<<操作员。

pow(2,ceil(log2(值));

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

关于密切相关问题的可能解决方案(即四舍五入而不是向上)的探索,其中许多解决方案比简单方法快得多,请访问 Bit Twiddling Hacks 页面,一个很好的资源来做你正在寻找的优化。最快的解决方案是使用具有256个条目的查找表,这将总操作计数从朴素方法的平均62个(通过类似的操作计数方法)减少到大约7个。使这些解决方案适应你的问题只是一个比较和增量的问题。

你并没有真正说出你所说的“更好的算法”是什么意思,但由于你提出的算法非常清楚(如果有点缺陷),我假设你正在寻找一种更有效的算法。

Larry Gritz给出了可能是最有效的c/c++算法,没有查找表的开销,在大多数情况下就足够了(参见 http://www.hackersdelight.org 对于类似的算法)。

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

然而,大多数编译器都有“内在”功能,允许使用机器指令,但以更便携的方式。

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

使用递归模板版本生成编译常量怎么样:

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

在标准C++20中 <bit> 这样做: cppreference .

#include <bit>
unsigned long upper_power_of_two(unsigned long v)
{
    return std::bit_ceil(v);
}

仅 unsigned 如果不使用整数类型,则整数类型将参与重载解析 bit_ceil<T> 模板参数显式。

Beware that bit_ceil has undefined behaviour 如果结果在输入类型中不可表示,而不仅仅是垃圾结果。
这甚至适用于无符号整数类型,在这种类型中,算术被定义为换行。

例如, std::bit_ceil(-123) 将隐式转换已签名的 int 输入到 未签约的 ,因此它将在 -123u 例如。 0xffffff85u 在32位系统上 国际性组织 正确的结果需要33位,大于 未签约的 ,因此行为未定义。

对于2的补码系统上的负输入,这是正确的,除了 INT_MIN / LONG_MIN 其具有与…相同的比特模式 1u<<(n-1) ,即。 2**(n-1)

下面的代码反复剥离最低位,直到数字是2的幂,然后将结果加倍,除非数字一开始是2的乘幂。它的优点是在与设置的比特数成比例的时间内运行。不幸的是,它的缺点是在几乎所有情况下都需要比问题中的代码或程序集建议更多的指令。我把它包括在内只是为了完整。

int nextPow(int x) {
  int y = x
  while (x &= (x^(~x+1))) 
    y = x << 1;
  return y
}

我知道这是下投票诱饵,但如果数字足够小(比如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;

这种转变或方法可能并不好,但也许可以扩展到更大的单词大小。

(实际上,这给出了最高的1位。你必须将其向左移动1才能得到下一个更高的2次幂。)

我的版本是一样的:

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; 
 }

我喜欢这种转变。

我会接受的

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

这样循环总是终止的,&&几乎从不进行评估。 我认为两行代码不值得调用函数。你也可以根据自己的判断做一个长的或短的,而且它非常易读。 (如果bufferPow变为负数,希望你的主代码能快速退出。)

通常你在算法开始时只计算一次2-power,所以优化无论如何都是愚蠢的。然而,如果有人足够无聊,会对速度竞赛感兴趣。..使用上述示例和255 256 257。. 4195 4196 4197

通过除以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%精确的,因为其中涉及浮点运算。