我想写一个函数,返回最接近的2的次幂数。例如,如果我的输入是789,输出应该是1024。有没有办法不使用任何循环,而只是使用一些位运算符?


当前回答

如果你需要OpenGL相关的东西:

/* Compute the nearest power of 2 number that is 
 * less than or equal to the value passed in. 
 */
static GLuint 
nearestPower( GLuint value )
{
    int i = 1;

    if (value == 0) return -1;      /* Error! */
    for (;;) {
         if (value == 1) return i;
         else if (value == 3) return i*4;
         value >>= 1; i *= 2;
    }
}

其他回答

C / c++中用于整数输入的高效微软(例如Visual Studio 2017)特定解决方案。在检查最有效的1位的位置之前,通过递减处理输入完全匹配2的幂值的情况。

inline unsigned int ExpandToPowerOf2(unsigned int Value)
{
    unsigned long Index;
    _BitScanReverse(&Index, Value - 1);
    return (1U << (Index + 1));
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

#if defined(WIN64) // The _BitScanReverse64 intrinsic is only available for 64 bit builds because it depends on x64

inline unsigned long long ExpandToPowerOf2(unsigned long long Value)
{
    unsigned long Index;
    _BitScanReverse64(&Index, Value - 1);
    return (1ULL << (Index + 1));
}

#endif

这将为英特尔处理器生成5个左右的内联指令,类似如下:

dec eax
bsr rcx, rax
inc ecx
mov eax, 1
shl rax, cl

显然Visual Studio c++编译器并没有针对编译时值进行优化,但这里并没有大量的指令。

编辑:

如果你想让输入值1产生1(2的0次方),对上面代码的一个小修改仍然会生成没有分支的直通指令。

inline unsigned int ExpandToPowerOf2(unsigned int Value)
{
    unsigned long Index;
    _BitScanReverse(&Index, --Value);
    if (Value == 0)
        Index = (unsigned long) -1;
    return (1U << (Index + 1));
}

生成更多的指令。诀窍在于Index可以被一个测试后跟一个cmove指令所取代。

c#中的可移植解决方案:

int GetNextPowerOfTwo(int input) {
    return 1 << (int)Math.Ceiling(Math.Log2(input));
}

Math.Ceiling(Math.Log2(value))计算2的下一个幂的指数,1 <<通过移位计算实值。

更快的解决方案,如果你有。net Core 3或更高版本:

uint GetNextPowerOfTwoFaster(uint input) {
    return (uint)1 << (sizeof(uint) * 8 - System.Numerics.BitOperations.LeadingZeroCount(input - 1));
}

这将使用system . numbers . bitoperations . leadingzerocount(),如果可用,则使用硬件指令:

https://github.com/dotnet/corert/blob/master/src/System.Private.CoreLib/shared/System/Numerics/BitOperations.cs

更新:

RoundUpToPowerOf2()即将在。net 6!内部实现与上面的. net Core 3解决方案基本相同。

这里是社区更新。

我认为这也是可行的:

int power = 1;
while(power < x)
    power*=2;

答案就是力量。

将其转换为浮点数,然后使用.hex()来显示标准化的IEEE表示。

> > >(789)浮动.hex () “0 x1.8a80000000000p + 9”

然后提取指数,再加1。

>>> int(float(789).hex().split('p+')[1]) + 1 10

取2的这个次方。

> > > 2 * * (int (float(789)。hex(),斯普利特(“p +”)[1])+ 1) 1024

这是我用c语言的解决方案,希望能有所帮助!

int next_power_of_two(int n) {
    int i = 0;
    for (--n; n > 0; n >>= 1) {
        i++;
    }
    return 1 << i;
}