快速计算64位整数的log2

一个伟大的编程资源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次操作。

但是，唉，没有给出任何额外的信息应该实际去哪种方式将algorithm扩展到64位整数。

有关这种64位algorithm如何看起来的提示？

Answer 1

内在函数非常快，但仍然不足以实现真正的跨平台，独立于编译器的log2实现。 所以如果有人感兴趣的话，下面是我自己研究这个主题时所用到的最快，无分支，CPU抽象的DeBruijn-likealgorithm。

 const int tab64[64] = { 63, 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}; int log2_64 (uint64_t value) { value |= value >> 1; value |= value >> 2; value |= value >> 4; value |= value >> 8; value |= value >> 16; value |= value >> 32; return tab64[((uint64_t)((value - (value >> 1))*0x07EDD5E59A4E28C2)) >> 58]; } 

下舍入到下一个较低次幂的部分取自2的幂次边界 ，从BitScan中获取尾随零数的部分（ (bb & -bb)代码是单独出来的最右边的位被设置为1，在将值舍入到2的下一个幂后，这是不需要的）。

顺便说一句，32位的实现是

 const int tab32[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31}; int log2_32 (uint32_t value) { value |= value >> 1; value |= value >> 2; value |= value >> 4; value |= value >> 8; value |= value >> 16; return tab32[(uint32_t)(value*0x07C4ACDD) >> 27]; } 

与其他任何计算方法一样，log2要求input值大于零。

Answer 2

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

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

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

所以你可以定义：

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

它将适用于任何无符号long long int。 结果向下舍入。

对于x86和AMD64，GCC将把它编译成bsr指令，所以解决scheme非常快（比查找表快得多）。

工作示例 ：

 #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 3

我试图转换查找O（lg（N））操作中的N位整数的日志库2乘以强制幻数的蛮力和查find64位。 不用说这是需要一段时间的。

然后，我发现德斯蒙德的答案，并决定尝试他的魔术数字作为一个起点。 由于我有一个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]; } 

Answer 4

这是一个非常紧凑和快速的扩展，不使用额外的临时对象：

 r = 0; /* If its wider than 32 bits, then we already know that log >= 32. So store it in R. */ if (v >> 32) { r = 32; v >>= 32; } /* Now do the exact same thing as the 32 bit algorithm, except we ADD to R this time. */ if (tt = v >> 16) { r += (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt]; } else { r += (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v]; } 

这里是一个build立了一系列的if ，再次使用没有额外的临时工。 可能不是最快的。

  if (tt = v >> 48) { r = (t = tt >> 8) ? 56 + LogTable256[t] : 48 + LogTable256[tt]; } else if (tt = v >> 32) { r = (t = tt >> 8) ? 40 + LogTable256[t] : 32 + LogTable256[tt]; } else if (tt = v >> 16) { r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt]; } else { r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v]; } 

Answer 5

基2整数对数

这是我为64位无符号整数做的。 这将计算基数为2的对数的底数，它等于最高有效位的指数。 这种方法对于大数量来说是非常快速的 ，因为它使用了一个以log264 = 6步执行的展开循环。

实质上，它所做的是逐渐减去序列中的较小的平方{0≤k≤5：2 ^（2 ^ k）} = {2,2,2,2，2,2,4,2,2,2} = {4294967296,65536,256 ，16,4,2,1}并且将相减值的指数k相加。

 int uint64_log2(uint64_t n) { #define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; } int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i; #undef S } 

请注意，如果给定无效input0（这是初始-(n == 0)正在检查的内容），则返回-1。 如果你不希望用n == 0调用它，你可以用int i = 0;来代替int i = 0; 为初始值设定项添加assert(n != 0); 在进入function。

基数10整数对数

基10的整数对数可以用类似的方法计算 – 最大的平方testing是10 10，因为log 10 2 4 4 19.2659 …（注意：这不是完成10进制整数对数的最快方法，因为它使用整数除法，这本质上是缓慢的，一个更快的实现是使用一个累加器，它的值按指数规律增长，然后和累加器进行比较，实际上是进行二分search）。

 int uint64_log10(uint64_t n) { #define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); } int i = -(n == 0); S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10); return i; #undef S } 

Answer 6

该algorithm基本上找出哪个字节包含最重要的1位，然后在查找中查找该字节以查找字节的日志，然后将其添加到该字节的位置。

这是一个32位algorithm的简化版本：

 if (tt = v >> 16) { if (t = tt >> 8) { r = 24 + LogTable256[t]; } else { r = 16 + LogTable256[tt]; } } else { if (t = v >> 8) { r = 8 + LogTable256[t]; } else { r = LogTable256[v]; } } 

这是等效的64位algorithm：

 if (ttt = v >> 32) { if (tt = ttt >> 16) { if (t = tt >> 8) { r = 56 + LogTable256[t]; } else { r = 48 + LogTable256[tt]; } } else { if (t = ttt >> 8) { r = 40 + LogTable256[t]; } else { r = 32 + LogTable256[ttt]; } } } else { if (tt = v >> 16) { if (t = tt >> 8) { r = 24 + LogTable256[t]; } else { r = 16 + LogTable256[tt]; } } else { if (t = v >> 8) { r = 8 + LogTable256[t]; } else { r = LogTable256[v]; } } } 

我想出了一种我认为比原来更好的尺寸types的algorithm。

 unsigned int v = 42; unsigned int r = 0; unsigned int b; for (b = sizeof(v) << 2; b; b = b >> 1) { if (v >> b) { v = v >> b; r += b; } } 

注意： b = sizeof(v) << 2将b设置为v中的位数的一半。我在这里使用移位而不是乘法（因为我觉得这样）。

你可以添加一个查找表来加速这个algorithm，但这更像是一个概念validation。