计算1到2之间的数字的对数基数2的有效方法

Question

我正在开发一个定点平台(不支持浮点运算).

我将任何有理数表示q为q * (1 << precision).

我需要用于计算对数底2的有效方法x,其中1 < x < 2.

这是我到目前为止所做的:

uint64_t Log2(uint64_t x, uint8_t precision)
{
    uint64 res = 0;

    uint64 one = (uint64_t)1 << precision;
    uint64 two = (uint64_t)2 << precision;

    for (uint8_t i = precision; i > 0 ; i--)
    {
        x = (x * x) / one; // now 1 < x < 4
        if (x >= two)
        {
            x >>= 1; // now 1 < x < 2
            res += (uint64_t)1 << (i - 1);
        }
    }

    return res;
}

这很好用,但它会影响我的程序的整体性能,这需要为大量的输入值执行此操作.

尽管如此,precision使用的是31,但这可能会改变,所以我需要将它保留为变量.

我可以在这里应用任何优化吗？

我想的是"先乘,最后总结"的形式.

但这意味着计算x ^ (2 ^ precision),这将很快溢出.

谢谢.

更新:

我之前试图摆脱分支,但它只是让事情变得更糟:

for (uint8_t i = precision; i > 0 ; i--)
{
    x = (x * x) / one; // now 1 < x < 4
    uint64_t n = x / two;
    x >>= n; // now 1 < x < 2
    res += n << (i - 1);
}

return res;

Answer 1

我唯一能想到的就是用右移而不是递减来执行循环，并将一些操作更改为其等效的二进制操作。这可能与您的平台相关，也可能无关，但在我的 x64 PC 中，它们产生了约 2% 的改进：

uint64_t Log2(uint64_t x, uint8_t precision)
{
    uint64_t res = 0;
    uint64_t two = (uint64_t)2 << precision;

    for (uint64_t b = (uint64_t)1 << (precision - 1); b; b >>= 1)
    {
        x = (x * x) >> precision; // now 1 < x < 4
        if (x & two)
        {
            x >>= 1; // now 1 < x < 2
            res |= b;
        }
    }
    return res;
}