LOG2的64位整数运算速度快 [英] Fast computing of log2 for 64-bit integers

问题描述

有一个伟大的编程资源，位操作劈，提出（这里）下面的方法来计算一个32位的整数的LOG2：

A great programming resource, Bit Twiddling Hacks, proposes (here) the following method to compute log2 of a 32-bit integer:

#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的操作。

The lookup table method takes only about 7 operations to find the log of a 32-bit value. If extended for 64-bit quantities, it would take roughly 9 operations.

但是，唉，不给哪些途径之一应该真正去算法扩展到64位整数的任何其他信息。

but, alas, doesn't give any additional info about which way one should actually go to extend the algorithm to 64-bit integers.

有关如何这样的一个64位算法会是什么样任何提示？

Any hints about how a 64-bit algorithm of this kind would look like?

推荐答案

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

Intrinsic functions are really fast but still are insufficient for a truly cross-platform, compiler-independent implementation of log2. So in case if anyone is interested, here is the fastest, branch-free, CPU-abstract DeBruijn-like algorithm I've come to while researching the topic on my own.

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 ） code有挑出最右边的位被设置为1，这是不需要我们已经四舍五入为2下次上电后的值）。

The part of rounding down to the next lower power of 2 was taken from Power-of-2 Boundaries and the part of getting the number of trailing zeros was taken from BitScan (the (bb & -bb) code there is to single out the rightmost bit that is set to 1, which is not need after we've rounded the value down to the next power of 2).

和32位实现，顺便说一句，就是

And the 32-bit implementation, by the way, is

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需要将输入值大于零。

As with any other computational method, log2 requires the input value to be greater than zero.

这篇关于LOG2的64位整数运算速度快的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！