我想写一个函数,返回最接近的2的次幂数。例如,如果我的输入是789,输出应该是1024。有没有办法不使用任何循环,而只是使用一些位运算符?
当前回答
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#中的可移植解决方案:
int GetNextPowerOfTwo(int input) {
return 1 << (int)Math.Ceiling(Math.Log2(input));
}
Math.Ceiling(Math.Log2(value))计算2的下一个幂的指数,1 <<通过移位计算实值。
更快的解决方案,如果你有。net Core 3或更高版本:
uint GetNextPowerOfTwoFaster(uint input) {
return (uint)1 << (sizeof(uint) * 8 - System.Numerics.BitOperations.LeadingZeroCount(input - 1));
}
这将使用system . numbers . bitoperations . leadingzerocount(),如果可用,则使用硬件指令:
https://github.com/dotnet/corert/blob/master/src/System.Private.CoreLib/shared/System/Numerics/BitOperations.cs
更新:
RoundUpToPowerOf2()即将在。net 6!内部实现与上面的. net Core 3解决方案基本相同。
这里是社区更新。
你可能会发现以下的澄清有助于达到你的目的:
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;
}
如果您正在使用GCC,您可能想要看看Lockless Inc.优化next_pow2()函数。本页描述了一种使用内置函数builtin_clz()(计数前导零)的方法,然后直接使用x86 (ia32)汇编指令bsr(位扫描反向),就像它在另一个答案的游戏开发站点链接中所描述的那样。此代码可能比前面的回答中描述的更快。
顺便说一下,如果你不打算使用汇编指令和64位数据类型,你可以使用这个
/**
* return the smallest power of two value
* greater than x
*
* Input range: [2..2147483648]
* Output range: [2..2147483648]
*
*/
__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
assert(x > 1);
assert(x <= ((UINT32_MAX/2) + 1));
#endif
return 1 << (32 - __builtin_clz (x - 1));
}
将保罗·迪克森的答案应用到Excel中,效果非常好。
=POWER(2,CEILING.MATH(LOG(A1)/LOG(2)))