我想写一个函数,返回最接近的2的次幂数。例如,如果我的输入是789,输出应该是1024。有没有办法不使用任何循环,而只是使用一些位运算符?
当前回答
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;
}
其他回答
我试着找到最接近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;
}
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++20中,这包含在<bit>中。 答案很简单
#include <bit>
unsigned long upper_power_of_two(unsigned long v)
{
return std::bit_ceil(v);
}
注意: 我给出的解决方案是针对c++,而不是c,我会给出这个问题的答案,但它是这个问题的副本!
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
@YannDroneaud答案的变体,适用于x==1,仅适用于x86平台,编译器,gcc或clang:
__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
assert(x > 0);
assert(x <= ((UINT32_MAX/2) + 1));
#endif
int clz;
uint32_t xm1 = x-1;
asm(
"lzcnt %1,%0"
:"=r" (clz)
:"rm" (xm1)
:"cc"
);
return 1 << (32 - clz);
}