您可以只计算前零位或后零位的数量,因为任何精确的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的幂。