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


当前回答

检查Bit Twiddling Hacks。你需要得到以2为底的对数,然后加上1。32位值的示例:

四舍五入到下一个2的最高次幂 Unsigned int v;//计算32位v的下一个最高次幂2 v -; V |= V >> 1; V |= V >> 2; V |= V >> 4; V |= V >> 8; V |= V >> 16; v + +;

延伸到其他宽度应该是明显的。

其他回答

为了完整起见,这里是用标准C语言实现的浮点数。

double next_power_of_two(double value) {
    int exp;
    if(frexp(value, &exp) == 0.5) {
        // Omit this case to round precise powers of two up to the *next* power
        return value;
    }
    return ldexp(1.0, exp);
}

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 next_power_of_two(int n) {
    int i = 0;
    for (--n; n > 0; n >>= 1) {
        i++;
    }
    return 1 << i;
}

如果你需要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;
    }
}

我试着找到最接近2的次幂,然后写出这个函数。希望它能帮助你。只要用最近的小数乘以2,就能得到2的最近上次方

int nearest_upper_power(int number){
    int temp=number;
    while((number&(number-1))!=0){
        temp<<=1;
        number&=temp;
    }
    //Here number is closest lower power 
    number*=2;
    return number;
}