我想写一个函数,返回最接近的2的次幂数。例如,如果我的输入是789,输出应该是1024。有没有办法不使用任何循环,而只是使用一些位运算符?
当前回答
在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
其他回答
这是我用c语言的解决方案,希望能有所帮助!
int next_power_of_two(int n) {
int i = 0;
for (--n; n > 0; n >>= 1) {
i++;
}
return 1 << i;
}
你可能会发现以下的澄清有助于达到你的目的:
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指令所取代。
检查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 + +;
延伸到其他宽度应该是明显的。
为了完整起见,这里是用标准C语言实现的浮点数。
double next_power_of_two(double value) {
int exp;
if(frexp(value, &exp) == 0.5) {
// Omit this case to round precise powers of two up to the *next* power
return value;
}
return ldexp(1.0, exp);
}