c# - 大数上的 BigInteger 日志问题

下面的代码采用 BigInteger n 并找到一个小于 n 的数字，该数字也是 power of 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);
}

最佳答案

在 if 分支中，你可以从商中减去一些东西，

number = BigInteger.Log(n)/BigInteger.Log(2) - 0.9;

例如(我会小心在那里减去 1.0，因为 BigInteger.Log(x) 不准确，商可能有点太小，然后减去 1.0 会给你错误的 2 次幂)。这也适用于相当大的数字(但 double 只有 53 位精度，因此对于大于 2^(2^54) 的数字肯定会失败 - 但是，这比当前可用的内存要多得多)。

但当然更容易

if (n.IsPowerOfTwo) {
    return n/2;
}

然而，else 分支是有问题的。如果 n 非常接近 2 的幂，

BigInteger.Log(n) / BigInteger.Log(2)

可能有点太大或太小，将商跨最接近的整数移动到精确结果。您应该检查 big 确实小于 n，如果不是，则除以 2。

可能 BigInteger.Log(n, 2.0) 产生比除以两个自然对数更精确的结果。 (我不知道实现。)

关于c# - 大数上的 BigInteger 日志问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11677972/