2 的幂的整数的 log2

Question

假设它是 2 的幂，是否有一种有效的方法来查找数字的 log2。我知道一些显而易见的方法，例如 table 或

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

不过我想知道有没有更efficient/elegant的方法

Answer 1

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

如果您有高效的 clz ("count leading zeroes")，那么 log2 实现可能如下所示：

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

（注：returns -1 表示 ilog2(0)。）

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

#define clz(x) __builtin_clz(x)

Microsoft 有类似的东西：BitScanReverse.

请注意，计算尾随个零（使用 ctz 指令）可能更方便，但 a clz instruction is more widely available on different CPU architectures.

使用 clz 而不是 ctz 的另一个好处是，对于非 2 的幂值，您会得到 floor(log2(x))，从而使您的 ilog2 功能更多通常比使用 ctz 更有用，后者仅适用于精确的 2 次幂。

另请参阅：Finding the first set bit in a binary number。

Answer 2

我没有对此进行基准测试，但它应该运行相当快，因为它不需要很多迭代：

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;
}

2 的幂的整数的 log2

log2 of an integer that is a power of 2

c++

algorithm

math

logarithm