LOG2的快速计算为64位整数(Fast computing of log2 for 64-bit

2019-06-14 17:26发布

站内文章 / 前端开发
248 0 0

一个伟大的编程资源，位操作黑客，提出了（ 这里 ）下面的方法来计算一个32位整数的log 2： 

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

内在功能都非常快，但仍然不足以LOG2的真正的跨平台，编译器无关的实现。 所以，如果如果有人有兴趣，这里是最快的，无分支，CPU抽象DeBruijn样的算法我来，同时研究我自己的话题。 

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的下一个较低功率的一部分取自电源的-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要求的输入值是大于零。



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

我试图转换与乘法和查找查找为O N位整数的日志基地2（LG（N））业务为64位通过暴力破解的幻数。 不用说，它正在采取一段时间。

后来我发现Desmond的答案，并决定尝试他的魔术数字作为起点。 因为我有一个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:

基-2-整数对数

以下是我对64位无符号整数做。 此计算基本-2对数，这相当于最显著位的索引的楼层。 这种方法是快速smokingly为大量，因为它使用的展开循环，在log₂64= 6个步骤总是执行。

本质上，它的作用是在序列中减去远逐渐变小的平方{0≤ķ≤5：2 ^（2 ^ k）的} = {2³²，2 16，2⁸，2⁴，2 2，2 1} = {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
}

请注意，这将返回-1，如果给定的0无效的输入（这是最初的-(n == 0)被检查）。 如果你从来没有期望与调用它n == 0 ，你可以代替int i = 0; 对于初始化，并添加assert(n != 0); 在进入该功能。

BASE-10的对数的整数

BASE-10整数对数可以用类似的计算 - 与最大的广场，以测试为10 16，因为log₁₀2⁶⁴≅19.2659 ...（注：这是不是为了实现一个基数为10整数对数最快的方法，因为它使用整数除法，这本质上是缓慢的。一个更快的实施将采用与指数增长值的蓄电池，并且比较对蓄压器，实际上做一种二进制搜索的。） 

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 5:

这里是一个非常紧凑和快速的延伸，不使用额外的临时： 

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

这是一个与链构建if S，再次使用无需额外的临时。 可能不是最快的，但。 

  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 6:

该算法基本上找出哪些字节包含最显著1位，然后查找该字节的查找，找到字节的日志，然后将其添加到字节的位置。

这里是32位算法的稍微简化的版本： 

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位的算法： 

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

我想出了任何规模大小类型，我认为是比原来更好的算法。 

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中的位的数目的一半我用移位来代替乘法这里（只是因为我觉得它）。

你可以查找表添加到该算法可能加速这一过程，但它更是一个验证的概念。



文章来源: Fast computing of log2 for 64-bit integers
标签： c 64bit bit-manipulation 32bit-64bit lookup
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~