我想写一个函数,返回最接近的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指令所取代。
其他回答
许多处理器架构都支持log以2为底或非常类似的操作——计数前导零。许多编译器都有针对它的内在特性。参见https://en.wikipedia.org/wiki/Find_first_set
在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
这是我用来让它成为一个常数表达式的,如果输入是一个常数表达式的话。
#define uptopow2_0(v) ((v) - 1)
#define uptopow2_1(v) (uptopow2_0(v) | uptopow2_0(v) >> 1)
#define uptopow2_2(v) (uptopow2_1(v) | uptopow2_1(v) >> 2)
#define uptopow2_3(v) (uptopow2_2(v) | uptopow2_2(v) >> 4)
#define uptopow2_4(v) (uptopow2_3(v) | uptopow2_3(v) >> 8)
#define uptopow2_5(v) (uptopow2_4(v) | uptopow2_4(v) >> 16)
#define uptopow2(v) (uptopow2_5(v) + 1) /* this is the one programmer uses */
例如,这样的表达式:
uptopow2(sizeof (struct foo))
会很好地化简为常数。
检查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语言的解决方案,希望能有所帮助!
int next_power_of_two(int n) {
int i = 0;
for (--n; n > 0; n >>= 1) {
i++;
}
return 1 << i;
}