log2的幂为2的整数

Question

是否有一种有效的方法来查找数字的log2,假设它是2的幂.我知道明显的方法,如有一张桌子或

for (log2=0;x!=1;x>>=1,log2++);

但我想知道是否有更有效/更优雅的方式.

Answer 1

您可以只计算前导或尾随零位的数量,因为任何精确的2次幂都表示为单个1位,其他所有位为0.许多CPU都有执行此操作的特殊指令,并且编译器(如gcc)具有这些操作的内在函数,它们被编译为适当体系结构上的单个指令.

如果你有一个有效的clz("计数前导零"),那么log2实现可能如下所示:

int32_t ilog2(uint32_t x)
{
    return sizeof(uint32_t) * CHAR_BIT - clz(x) - 1;
}

(注意:返回-1表示ilog2(0).)

使用gcc或兼容gcc的编译器时,您可以clz像这样定义:

#define clz(x) __builtin_clz(x)

微软有类似的东西:BitScanReverse.

请注意,它可能会出现更方便计数尾随零(使用ctz指令),但一个clz指令是更广泛的应用在不同的CPU架构.

通过进一步的奖金clz,而不是ctz在于你得到floor(log2(x))了非幂的2个值,让您的ilog2功能更普遍有用比,如果你使用过ctz,它仅适用于精确的功率为2的.