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


当前回答

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

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

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

其他回答

from math import ceil, log2
pot_ceil = lambda N: 0x1 << ceil(log2(N))

测试:

for i in range(10):
    print(i, pot_ceil(i))

输出:

1 1
2 2
3 4
4 4
5 8
6 8
7 8
8 8
9 16
10 16

对于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,根据你的编译器,可能有一个内在的可用指令来为你做这项工作。

我试着找到最接近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;
}
unsigned long upper_power_of_two(unsigned long v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;

}

在标准c++20中,这包含在<bit>中。 答案很简单

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

注意: 我给出的解决方案是针对c++,而不是c,我会给出这个问题的答案,但它是这个问题的副本!