c# - 大量的 BigInteger 日志问题

Question

下面的代码采用 BigInteger n 并找到一个小于 n 的数，该数也是 2 的幂。它适用于小数字，但 if 语句的第一个分支不适用于 int.MaxValue 及更高版本。显然减去 1 (BigInteger.Log(n - 1)) 对于更大的数字是不够的。

我怎样才能计算出一个大到足以产生差异的数字来减去，同时还能处理较小的数字？

public BigInteger FindNearestPowerOfTwo (BigInteger n)
{
    double number = 0;
    BigInteger big = 0;

    if (n.IsPowerOfTwo)
    {
        number = BigInteger.Log(n - 1) / BigInteger.Log(2);
    }
    else
    {
        number = BigInteger.Log(n) / BigInteger.Log(2);
    }

    number = Math.Floor(number);

    big = BigInteger.Pow(2, (int) number);

    return (big);
}

Answer 1

您可以使用 ToByteArray 获得显式表示，然后清除除最高位以外的所有位。

public BigInteger FindNearestPowerOfTwo (BigInteger n) {
    Byte[] a = n.ToByteArray();
    int len = a.Length;
    if (a[len - 1] == 0) len--; // leading zero to maintain sign
    for (int i = 0; i < len - 1; i++) a[i] = 0;
    int x = a[len - 1] & 255;
    int y = 1;
    while (x > 1) {
      x >>= 1;
      y <<= 1;
    }
    a[len - 1] = y;
    return new BigInteger(a);
}