快速计算64位整数的log2

Question

很棒的编程资源，Bit Twiddling Hacks，在这里提出了以下方法来计算32位整数的log2：#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, nstatic const char LogTable256[256] = {    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)};unsigned int v; // 32-bit word to find the log ofunsigned r;     // r will be lg(v)register unsigned int t, tt; // temporariesif (tt = v >> 16){    r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];}else {    r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];}并提到查找表方法仅需执行大约7个操作即可查找32位值的日志。如果扩展为64位，则大约需要9次操作。但是，可惜的是，它没有提供任何其他有关将算法扩展到64位整数的实际方法的信息。关于这种64位算法的外观有何暗示？

Answer 1

如果您使用的是GCC，则在这种情况下不需要查找表。

GCC提供了一个内置函数来确定前导零的数量：

内置函数： 从最高有效位位置开始，返回x中前导0位的数量。如果x为0，则结果不确定。int __builtin_clz (unsigned int x)

因此，您可以定义：

#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))

它适用于任何unsigned long long int。结果四舍五入。

对于x86和AMD64，GCC会将其编译为bsr指令，因此解决方案非常快（比查找表快得多）。

工作示例：

#include <stdio.h>

#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))

int main(void) {

    unsigned long long input;

    while (scanf("%llu", &input) == 1) {

        printf("log(%llu) = %u\n", input, LOG2(input));

    }

    return 0;

}

Answer 2

我正在尝试通过蛮力强制使用幻数将O（lg（N））操作中的N位整数的对数基数2与乘法和查找转换为64位。不用说这需要一段时间。

然后，我找到了戴斯蒙德的答案，并决定尝试以他的幻数作为起点。由于我有一个6核处理器，因此我从0x07EDD5E59A4E28C2 / 6倍数开始并行运行它。我很惊讶它立即发现了一些东西。原来0x07EDD5E59A4E28C2 / 2工作。

因此，这是0x07EDD5E59A4E28C2的代码，可节省您的移位并减去：

int LogBase2(uint64_t n)

{

    static const int table[64] = {

        0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61,

        51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62,

        57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56,

        45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63 };

    n |= n >> 1;

    n |= n >> 2;

    n |= n >> 4;

    n |= n >> 8;

    n |= n >> 16;

    n |= n >> 32;

    return table[(n * 0x03f6eaf2cd271461) >> 58];

}