我想写一个函数,返回最接近的2的次幂数。例如,如果我的输入是789,输出应该是1024。有没有办法不使用任何循环,而只是使用一些位运算符?
当前回答
对于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,根据你的编译器,可能有一个内在的可用指令来为你做这项工作。
其他回答
如果您想要单行模板。在这里
int nxt_po2(int n) { return 1 + (n|=(n|=(n|=(n|=(n|=(n-=1)>>1)>>2)>>4)>>8)>>16); }
or
int nxt_po2(int n) { return 1 + (n|=(n|=(n|=(n|=(n|=(n-=1)>>(1<<0))>>(1<<1))>>(1<<2))>>(1<<3))>>(1<<4)); }
这是我用c语言的解决方案,希望能有所帮助!
int next_power_of_two(int n) {
int i = 0;
for (--n; n > 0; n >>= 1) {
i++;
}
return 1 << i;
}
将保罗·迪克森的答案应用到Excel中,效果非常好。
=POWER(2,CEILING.MATH(LOG(A1)/LOG(2)))
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
检查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 + +;
延伸到其他宽度应该是明显的。