找到BigInteger的最重要部分

Question

我已经阅读了很多精确的算法来识别32位和64位整数的最高位(包括SO上的其他帖子).但我正在使用BigIntegers,并将处理长达4000位的数字.(BigInteger将希尔伯特指数保持为Hilbert空间填充曲线,该曲线在分形深度为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毫秒.

  对EverySignificantBitUsingBinarySearch(可转换为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;
}

Answer 1

您可以计算log2,它表示所需的位数:

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