我想写一个函数，返回最接近的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;
}
其他回答
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指令所取代。
将其转换为浮点数，然后使用.hex()来显示标准化的IEEE表示。
> > >(789)浮动.hex () “0 x1.8a80000000000p + 9”
然后提取指数，再加1。
>>> int（float（789）.hex（）.split（'p+'）[1]） + 1 10
取2的这个次方。
> > > 2 * * (int (float(789)。hex(),斯普利特(“p +”)[1])+ 1) 1024
next = pow(2, ceil(log(x)/log(2)));
这是通过找到你想要2乘以x的数字来实现的(取这个数字的对数，然后除以想要的底数的对数，详见维基百科)。然后把它四舍五入，得到最接近的整数幂。
这是一个比其他地方链接的按位方法更通用的方法(即更慢!)，但很好地了解数学，不是吗?
如果您想要单行模板。在这里
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)); }
你可能会发现以下的澄清有助于达到你的目的:
