c# - 查找 BigInteger 的最高有效位

Question

我已经阅读了许多用于识别 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 的一百万次调用过去了 96 毫秒 (可转换为长)。

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

  一万次调用 MostSignificantBitUsingLog 已过去 74 毫秒 (太大而无法转换)。

  一万次调用过去了 267 毫秒 MostSignificantBitUsingBinarySearch(太大而无法转换)。

这是使用日志的代码:

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 位 block 中递归调用自身。好多了。现在运行我的测试需要 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;
}

Answer 1

您可以计算代表所需位数的 log2:

var numBits = (int)Math.Ceil(bigInt.Log(2));