2的幂次方整数的log2值

Question

如果一个数字是2的幂次方，那么有没有高效的方法来找到它的log2值？我知道一些明显的方法，比如用表格或者

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

但我在想是否有更加高效/优美的方式。

- Tohiko

---

你有查过数学库吗？我打赌里面肯定有一些高效的函数。 - user7636697

但是你可能只需要来自<cmath>的std::log2()。如果你能使用分析器证明瓶颈存在，那么再考虑寻找更高效的方法。 - underscore_d

使用表格；给定64位整数，它们只有64个。 - Richard Critten

@RichardCritten - 但是你如何为那个查找表创建索引？ - Brett Hale

另一个重复问题：计算“2的幂”数的幂次的最快方法是什么？ - phuclv

Answer 1

你只需数一下前导零位或尾随零位的数量，因为任何精确的二的幂都可以表示为单个1位，其他所有位都是0。许多CPU都有专门的指令来执行此操作，并且像gcc这样的编译器具有用于这些操作的内置函数，这些函数在适当的体系结构上被编译为单个指令。

如果你有一个高效的clz（"计算前导零位"）函数，那么一个log2的实现可能如下所示：

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

(Note: 对于 ilog2(0), 返回 -1。) 当您使用gcc或兼容gcc的编译器时，只需像这样定义clz:

#define clz(x) __builtin_clz(x)

微软也有类似的功能：BitScanReverse。

请注意，使用ctz指令计算 尾随 零可能会更方便，但是clz指令在不同的CPU架构上更为普遍可用。

使用clz而不是ctz的另一个好处是，在非2的幂值时，您可以获得floor(log2(x))，使您的ilog2函数比使用ctz更具普适性，后者仅适用于精确的2次幂。

另请参见：在二进制数中查找第一个设置的位。

- Paul R

---

只用 ctz(num) 不就足以获取 num 中的尾随零了吗？ - Bhawan

__builtin_ctz 显然是一个更为直接的选项... - davmac

对于ctz，我没有检查arm，但在aarch64上，gcc生成rbit+clz，这应该不会比31-clz差太多。 - Marc Glisse

@MarcGlisse：好的 - 尽管您可能仍然希望添加处理0情况的代码（如果需要），当使用clz时，您可以免费获得它。 - Paul R

（0不是2的幂，但人们经常需要处理2的幂或0）gcc的文档说，__builtin_c [lt] z在参数为0时都未定义。 - Marc Glisse

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

- r3mainer