快速计算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, n

static 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 of

unsigned r;     // r will be lg(v)

register unsigned int t, tt; // temporaries

if (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) {&nbsp; &nbsp; unsigned long long input;&nbsp; &nbsp; while (scanf("%llu", &input) == 1) {&nbsp; &nbsp; &nbsp; &nbsp; printf("log(%llu) = %u\n", input, LOG2(input));&nbsp; &nbsp; }&nbsp; &nbsp; return 0;}

Answer 2

我正在尝试通过蛮力强制使用幻数将O（lg（N））操作中的N位整数的对数基数2与乘法和查找转换为64位。不用说这需要一段时间。然后，我找到了戴斯蒙德的答案，并决定尝试以他的幻数作为起点。由于我有一个6核处理器，因此我从0x07EDD5E59A4E28C2 / 6倍数开始并行运行它。我很惊讶它立即发现了一些东西。原来0x07EDD5E59A4E28C2 / 2工作。因此，这是0x07EDD5E59A4E28C2的代码，可节省您的移位并减去：int LogBase2(uint64_t n){&nbsp; &nbsp; static const int table[64] = {&nbsp; &nbsp; &nbsp; &nbsp; 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61,&nbsp; &nbsp; &nbsp; &nbsp; 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62,&nbsp; &nbsp; &nbsp; &nbsp; 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56,&nbsp; &nbsp; &nbsp; &nbsp; 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63 };&nbsp; &nbsp; n |= n >> 1;&nbsp; &nbsp; n |= n >> 2;&nbsp; &nbsp; n |= n >> 4;&nbsp; &nbsp; n |= n >> 8;&nbsp; &nbsp; n |= n >> 16;&nbsp; &nbsp; n |= n >> 32;&nbsp; &nbsp; return table[(n * 0x03f6eaf2cd271461) >> 58];}