我想写一个函数，返回最接近的2的次幂数。例如，如果我的输入是789，输出应该是1024。有没有办法不使用任何循环，而只是使用一些位运算符?
当前回答
import sys
def is_power2(x):
return x > 0 and ((x & (x - 1)) == 0)
def find_nearest_power2(x):
if x <= 0:
raise ValueError("invalid input")
if is_power2(x):
return x
else:
bits = get_bits(x)
upper = 1 << (bits)
lower = 1 << (bits - 1)
mid = (upper + lower) // 2
if (x - mid) > 0:
return upper
else:
return lower
def get_bits(x):
"""return number of bits in binary representation"""
if x < 0:
raise ValueError("invalid input: input should be positive integer")
count = 0
while (x != 0):
try:
x = x >> 1
except TypeError as error:
print(error, "input should be of type integer")
sys.exit(1)
count += 1
return count
其他回答
g++编译器提供了一个内置函数__builtin_clz，用于计算前导零:
所以我们可以这样做:
int nextPowerOfTwo(unsigned int x) {
return 1 << sizeof(x)*8 - __builtin_clz(x);
}
int main () {
std::cout << nextPowerOfTwo(7) << std::endl;
std::cout << nextPowerOfTwo(31) << std::endl;
std::cout << nextPowerOfTwo(33) << std::endl;
std::cout << nextPowerOfTwo(8) << std::endl;
std::cout << nextPowerOfTwo(91) << std::endl;
return 0;
}
结果:
8
32
64
16
128
但请注意，对于x == 0， __builtin_clz return是未定义的。
我试着找到最接近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;
}
在x86中，你可以使用sse4位操作指令来提高速度。
//assume input is in eax
mov ecx,31
popcnt edx,eax //cycle 1
lzcnt eax,eax //cycle 2
sub ecx,eax
mov eax,1
cmp edx,1 //cycle 3
jle @done //cycle 4 - popcnt says its a power of 2, return input unchanged
shl eax,cl //cycle 5
@done: rep ret //cycle 5
在c中，您可以使用匹配的intrinsic。
或者无跳转，通过避免跳转导致的错误预测来加快速度，但通过延长依赖链来减慢速度。计时，看看哪种代码最适合您。
//assume input is in eax
mov ecx,31
popcnt edx,eax //cycle 1
lzcnt eax,eax
sub ecx,eax
mov eax,1 //cycle 2
cmp edx,1
mov edx,0 //cycle 3
cmovle ecx,edx //cycle 4 - ensure eax does not change
shl eax,cl
@done: rep ret //cycle 5
我认为这也是可行的:
int power = 1;
while(power < x)
power*=2;
答案就是力量。
next = pow(2, ceil(log(x)/log(2)));
这是通过找到你想要2乘以x的数字来实现的(取这个数字的对数，然后除以想要的底数的对数，详见维基百科)。然后把它四舍五入，得到最接近的整数幂。
这是一个比其他地方链接的按位方法更通用的方法(即更慢!)，但很好地了解数学，不是吗?
