快速计算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如何看起来的提示?

    内在函数非常快,但仍然不足以实现真正的跨平台,独立于编译器的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值大于零。

    如果您使用的是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; } 

    我试图转换查找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]; } 

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

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

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

    该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。