有没有一种有效的方法可以找到一个数字的log2,假设它是2的幂。我知道一些显而易见的方法,比如有一张桌子或
for (log2=0;x!=1;x>>=1,log2++);
但我想知道是否有更高效/更优雅的方式。
您只需计算前导或尾随零位的数量,因为任何精确的二次方都表示为单个1位,而所有其他位都为0。许多CPU都有专门的指令来执行这一操作,而像gcc这样的编译器也有用于这些操作的内部函数,这些操作可以在适当的体系结构上编译成一条指令。
如果您有一个有效的clz
("计数前导零"),那么log2
的实现可能如下所示:
int32_t ilog2(uint32_t x)
{
return sizeof(uint32_t) * CHAR_BIT - clz(x) - 1;
}
(注意:对于ilog2(0)
,返回-1。)
当使用gcc或兼容gcc的编译器时,您可以这样定义clz
:
#define clz(x) __builtin_clz(x)
微软也有类似的东西:BitScanReverse。
请注意,计数尾随的零(使用ctz
指令)可能更方便,但clz
指令在不同的CPU架构上更广泛。
使用clz
而不是ctz
的另一个好处是,对于非2次幂的值,您可以获得floor(log2(x))
,这使得您的ilog2
函数比使用仅适用于2次幂精确值的ctz
更通用。
另请参阅:查找二进制数中的第一个设置位。
我还没有对此进行基准测试,但它应该运行得相当快,因为它不需要多次迭代:
int which_power_of_2(uint64_t x) {
uint64_t z = 0x0000000100000000ULL;
int p = 31, d = 16;
while (d) {
if (x & (z-1)) {
p -= d;
z >>= d;
}
else {
p += d;
z <<= d;
}
d >>= 1;
}
return x ? ((x & z) ? p+1 : p) : -1;
}