3

下面的代码采用 BigIntegern并找到小于该数字的数字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);
}
4

3 回答 3

2

您可以使用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);
}
于 2012-07-26T21:39:14.910 回答
1

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

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

例如（我会小心减去 1.0，因为BigInteger.Log(x)不准确，商可能有点太小，然后减去 1.0 会给你 2 的错误幂）。这也适用于相当大的数字（但 adouble只有 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)比除以两个自然对数产生更精确的结果。（我不知道实现。）

于 2012-07-26T21:18:18.627 回答
1

或者懒人的版本：

public static BigInteger FindNearestPowerOfTwo(BigInteger number) {
    bool isPower = number.IsPowerOfTwo;
    int count = 0;
    while(!number.IsZero) {
        Console.WriteLine(number);
        number = number >> 1;
        count ++ ;
    }
    return BigInteger.Pow(2, count - (isPower ? 2: 1));
}
于 2012-07-26T22:33:48.250 回答