小编典典

一个2的幂的整数的log2

algorithm

假设有2的幂,有没有找到数字的log2的有效方法?我知道很明显的方法,例如拥有表格或

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

但是我想知道是否有一种更有效/更优雅的方法。


阅读 65

收藏
2020-07-28

共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的幂。

2020-07-28