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


当前回答

next = pow(2, ceil(log(x)/log(2)));

这是通过找到你想要2乘以x的数字来实现的(取这个数字的对数,然后除以想要的底数的对数,详见维基百科)。然后把它四舍五入,得到最接近的整数幂。

这是一个比其他地方链接的按位方法更通用的方法(即更慢!),但很好地了解数学,不是吗?

其他回答

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

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

对于IEEE浮点,你可以这样做。

int next_power_of_two(float a_F){
    int f = *(int*)&a_F;
    int b = f << 9 != 0; // If we're a power of two this is 0, otherwise this is 1

    f >>= 23; // remove factional part of floating point number
    f -= 127; // subtract 127 (the bias) from the exponent

    // adds one to the exponent if were not a power of two, 
    // then raises our new exponent to the power of two again.
    return (1 << (f + b)); 
}

如果你需要一个整数的解决方案,并且你能够使用内联汇编,BSR会在x86上给你一个整数的log2。它计算有多少位是正确的,这正好等于这个数字的log2。其他处理器(通常)有类似的指令,比如CLZ,根据你的编译器,可能有一个内在的可用指令来为你做这项工作。

这是我用来让它成为一个常数表达式的,如果输入是一个常数表达式的话。

#define uptopow2_0(v) ((v) - 1)
#define uptopow2_1(v) (uptopow2_0(v) | uptopow2_0(v) >> 1)
#define uptopow2_2(v) (uptopow2_1(v) | uptopow2_1(v) >> 2)
#define uptopow2_3(v) (uptopow2_2(v) | uptopow2_2(v) >> 4)
#define uptopow2_4(v) (uptopow2_3(v) | uptopow2_3(v) >> 8)
#define uptopow2_5(v) (uptopow2_4(v) | uptopow2_4(v) >> 16)

#define uptopow2(v) (uptopow2_5(v) + 1)  /* this is the one programmer uses */

例如,这样的表达式:

uptopow2(sizeof (struct foo))

会很好地化简为常数。

next = pow(2, ceil(log(x)/log(2)));

这是通过找到你想要2乘以x的数字来实现的(取这个数字的对数,然后除以想要的底数的对数,详见维基百科)。然后把它四舍五入,得到最接近的整数幂。

这是一个比其他地方链接的按位方法更通用的方法(即更慢!),但很好地了解数学,不是吗?

许多处理器架构都支持log以2为底或非常类似的操作——计数前导零。许多编译器都有针对它的内在特性。参见https://en.wikipedia.org/wiki/Find_first_set