1

我已经阅读了许多用于识别 32 位和 64 位整数的最高有效位的精细算法（包括 SO 上的其他帖子）。但我使用的是 BigIntegers，并且将处理长达 4000 位的数字。（BigInteger 将把希尔伯特索引保存到希尔伯特空间填充曲线中，该曲线蜿蜒穿过分形深度为 4 的 1000 维超立方体。）但是大部分案例将涉及可以放入 64 位整数内的数字，所以我想要一个最适合常见情况但可以处理极端情况的解决方案。

天真的方法是：

BigInteger n = 234762348763498247634; 
int count = 0; 
while (n > 0) {
    n >>= 1;
    count++;
}

我正在考虑将常见案例转换为 Longs 并在这些案例上使用 64 位算法，否则对非常大的数字使用不同的算法。但我不确定转换为 Long 的成本有多高，以及这是否会淹没在 64 位数量上进行剩余计算的效率。有什么想法吗？

此函数的一个预期用途是帮助优化逆格雷码计算。

更新。我编写了两种方法并运行了一个基准测试。

  • 如果数字低于 Ulong.MaxValue，则转换为 Ulong 并执行二进制搜索方法的速度是使用 BigInteger.Log 的两倍。

  • 如果这个数字非常大（我高达 10000 位），那么 Log 的速度会快 3.5 倍。

    对 MostSignificantBitUsingLog（可转换为 Long）的一百万次调用经过了 96 毫秒。

    100 万次调用 MostSignificantBitUsingBinarySearch（可转换为 Long）耗时 42 毫秒。

    对 MostSignificantBitUsingLog 的一万次调用经过了 74 毫秒（太大而无法转换）。

    对 MostSignificantBitUsingBinarySearch 的一万次调用经过了 267 毫秒（太大而无法转换）。

下面是使用 Log 的代码：

public static int MostSignificantBitUsingLog(BigInteger i)
{
    int bit;
    if (i == 0)
        bit = -1;
    else
        bit = (int)BigInteger.Log(i, 2.0);

    return bit;
}

这是我的二进制搜索方法。可以改进将二进制除法扩展到 BigInteger 范围。接下来我会尝试的。

public static int MostSignificantBitUsingBinarySearch(BigInteger i)
{
    int bit;
    if (i.IsZero)
        bit = -1;
    else if (i < ulong.MaxValue)
    {
        ulong y = (ulong)i;
        ulong s;
        bit = 0;
        s = y >> 32;
        if (s != 0)
        {
            bit = 32;
            y = s;
        }
        s = y >> 16;
        if (s != 0)
        {
            bit += 16;
            y = s;
        }
        s = y >> 8;
        if (s != 0)
        {
            bit += 8;
            y = s;
        }
        s = y >> 4;
        if (s != 0)
        {
            bit += 4;
            y = s;
        }
        s = y >> 2;
        if (s != 0)
        {
            bit += 2;
            y = s;
        }
        s = y >> 1;
        if (s != 0)
            bit++;
    }
    else
        return 64 + MostSignificantBitUsingBinarySearch(i >> 64);

    return bit;
}

更新 2：我更改了我的二进制搜索算法以针对 BigIntegers 最多一百万个二进制数字，而不是在 64 位块中递归地调用自身。好多了。现在运行我的测试需要 18 毫秒，比调用 Log 快四倍！（在下面的代码中，MSB 是我的 ulong 函数，它做同样的事情，循环展开。）

public static int MostSignificantBitUsingBinarySearch(BigInteger i)
{
    int bit;
    if (i.IsZero)
        bit = -1;
    else if (i < ulong.MaxValue)
        bit = MSB((ulong)i);
    else
    {
        bit = 0;
        int shift = 1 << 20; // Accommodate up to One million bits.
        BigInteger remainder;     
        while (shift > 0)
        {
            remainder = i >> shift;
            if (remainder != 0)
            {
                bit += shift;
                i = remainder;
            }
            shift >>= 1;
        }
    }
    return bit;
}
4

5 回答 5

5

您可以计算表示所需位数的 log2：

var numBits = (int)Math.Ceil(bigInt.Log(2));
于 2012-04-04T13:24:20.223 回答
2

您可以将其视为二进制搜索问题。

您的上限为 4000（可能会增加一些空间）

int m = (lo + hi) / 2;
BigInteger x = BigInteger(1) << m;

if (x > n) ...
else  ...
于 2012-04-04T13:26:38.257 回答
1

在 .Net 5 中，这现在是内置的......

int log2 = myBigInt.GetBitLength()
于 2021-01-06T01:44:40.493 回答
0

如果您可以使用 Java 而不是 C#，那么您可以在http://uzaygezen.googlecode.com找到一个用于任意精度希尔伯特曲线索引的库。对于格雷码逆的实现，您可能需要仔细查看上述项目中的 LongArrayBitVector.grayCodeInverse 或 BitSetBackedVector.grayCodeInverse。

于 2012-05-18T20:48:22.803 回答
0

8 年后，为了找到 MSB 最高位（又名 Log2），我想出了这个快速方法......

static int GetTopBit(BigInteger value)
{
    if (value < 0)
        BigInteger.Negate(value);
    int lowerBytes = value.GetByteCount(true) - 1;
    int t = value.ToByteArray(true)[lowerBytes];
    int top = t > 127 ? 8 : t > 63 ? 7 : t > 31 ? 6 : t > 15 ? 5 : t > 7 ? 4 : t > 3 ? 3 : t > 1 ? 2 : 1;
    int topbit = (top + lowerBytes * 8);
    return topbit;
}
于 2020-09-30T05:52:19.287 回答