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

または怠け者のバージョン：

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 に答える
1

ブランチではif、商から何かを引くことができます。

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

たとえば（BigInteger.Log(x)正確ではないため、1.0を引くことに注意してください。商が少し小さすぎる可能性があり、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)2 つの自然対数を割るよりも正確な結果が得られる可能性があります。（実装はわかりません。）

于 2012-07-26T21:18:18.627 に答える