我想写一个函数，返回最接近的2的次幂数。例如，如果我的输入是789，输出应该是1024。有没有办法不使用任何循环，而只是使用一些位运算符?
当前回答
尽管问题标注为c，我的5分钱。幸运的是，c++ 20将包含std::ceil2和std::floor2(参见这里)。它是consexpr模板函数，目前的GCC实现使用位移位和工作于任何整型无符号类型。
其他回答
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指令所取代。
next = pow(2, ceil(log(x)/log(2)));
这是通过找到你想要2乘以x的数字来实现的(取这个数字的对数，然后除以想要的底数的对数，详见维基百科)。然后把它四舍五入，得到最接近的整数幂。
这是一个比其他地方链接的按位方法更通用的方法(即更慢!)，但很好地了解数学，不是吗?
g++编译器提供了一个内置函数__builtin_clz，用于计算前导零:
所以我们可以这样做:
int nextPowerOfTwo(unsigned int x) {
return 1 << sizeof(x)*8 - __builtin_clz(x);
}
int main () {
std::cout << nextPowerOfTwo(7) << std::endl;
std::cout << nextPowerOfTwo(31) << std::endl;
std::cout << nextPowerOfTwo(33) << std::endl;
std::cout << nextPowerOfTwo(8) << std::endl;
std::cout << nextPowerOfTwo(91) << std::endl;
return 0;
}
结果:
8
32
64
16
128
但请注意，对于x == 0， __builtin_clz return是未定义的。
检查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 + +;
延伸到其他宽度应该是明显的。
许多处理器架构都支持log以2为底或非常类似的操作——计数前导零。许多编译器都有针对它的内在特性。参见https://en.wikipedia.org/wiki/Find_first_set
