一个2的幂的整数的log2 [英] log2 of an integer that is a power of 2

问题描述

有没有一种有效的方法来查找数字的log2(假设它的幂为2).我知道很明显的方法，例如拥有表格或

Is there an efficient way to find the log2 of a number assuming it's a power of 2. I know the obvious ways like having a table or

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

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

But I am wondering if there is a more efficient/elegant way.

推荐答案

您可以只计算前零位或后零位的数量，因为任何精确的2的幂都表示为一个1位，而所有其他位0.许多CPU都有执行此操作的特殊指令，而gcc之类的编译器具有这些操作的内在函数，这些内在函数在适当的体系结构上被编译为一条指令.

You can just count the number of leading or trailing zero bits, because any exact power-of-two is represented as a single 1 bit, with all other bits 0. Many CPUs have special instructions for doing this, and compilers such as gcc have intrinsics for these operations, which get compiled to a single instruction on appropriate architectures.

如果您拥有高效的clz(计数前导零")，则log2实现可能如下所示:

If you have an efficient clz ("count leading zeroes") then a log2 implementation might look like this:

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

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

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

When using gcc or a gcc-compatible compiler you can just define clz like this:

#define clz(x) __builtin_clz(x)

Microsoft具有类似的内容: BitScanReverse .

Microsoft has something similar: BitScanReverse.

请注意，使用ctz指令来计数后缀零可能看起来更方便，但是

Note that it might appear more convenient to count trailing zeroes (using a ctz instruction), but a clz instruction is more widely available on different CPU architectures.

使用clz而不是ctz的另一个好处是，对于非2幂的值，您会得到floor(log2(x))，这使得ilog2函数比使用ctz时更有用. ，仅适用于2的幂.

A further bonus of using clz rather than ctz is that you get floor(log2(x)) for non-power-of-2 values, making your ilog2 function more generally useful than if you had used ctz, which only works for exact powers-of-2.

另请参见:找到二进制数的第一个置位.

这篇关于一个2的幂的整数的log2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！