[解決済み] ある数字が2の累乗かどうかを確認する方法

質問

今日、ある数字が2の累乗であるかどうかをチェックするための簡単なアルゴリズムが必要でした。

アルゴリズムに必要なのは

1. シンプル
2. あらゆる ulong の値を指定します。

こんなシンプルなアルゴリズムを思いつきました。

private bool IsPowerOfTwo(ulong number)
{
    if (number == 0)
        return false;

    for (ulong power = 1; power > 0; power = power << 1)
    {
        // This for loop used shifting for powers of 2, meaning
        // that the value will become 0 after the last shift
        // (from binary 1000...0000 to 0000...0000) then, the 'for'
        // loop will break out.

        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}

しかし、そこで私は考えました。ログをチェックするのはどうだろう？ <サブ 2 がちょうど丸い数なのか？2^63+1について調べると Math.Log() は四捨五入のため、ちょうど63を返しました。そこで、2の63乗が元の数値と等しいかどうか調べてみると、等しいことがわかりました。 double のように、正確な数字ではありません。

private bool IsPowerOfTwo_2(ulong number)
{
    double log = Math.Log(number, 2);
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}

これは true は、与えられた間違った値に対して 9223372036854775809 .

もっと良いアルゴリズムはないのでしょうか？

どのように解決するのですか？

この問題には、簡単なコツがあります。

bool IsPowerOfTwo(ulong x)
{
    return (x & (x - 1)) == 0;
}

注意：この関数は true に対して 0 のべき乗ではない 2 . それを除外したい場合は、以下のようになります。

bool IsPowerOfTwo(ulong x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

説明

まず第一に、MSDN の定義にあるビット単位の二項演算子 & を使用することです。

二項演算子は、積分型とbool型に対してあらかじめ定義されています。この演算子は はオペランドのビット単位の論理積を計算します。 boolオペランドの場合、&はオペランドの論理ANDを計算します。 オペランドがともに真のときのみ、結果は真となる。

さて、このような流れで見ていきましょう。

この関数はブール値（true / false）を返し、unsigned long型（この場合はx）のパラメータを1つ受け取ります。 簡単のために、誰かが値4を渡し、このように関数を呼び出したと仮定してみましょう。

bool b = IsPowerOfTwo(4)

ここで、xの出現箇所を4で置き換えてみます。

return (4 != 0) && ((4 & (4-1)) == 0);

さて、4 != 0 が真になることはすでに分かっています。 しかし、どうでしょう。

((4 & (4-1)) == 0)

もちろんこれを訳すとこうなります。

((4 & 3) == 0)

しかし、具体的にどのような 4&3 ?

4の2進表現は100、3の2進表現は011です（&はこれらの数値の2進表現を取ることを忘れないでください）。 というわけで、次のようになります。

100 = 4
011 = 3

これらの値を、小学校の足し算のように積み重ねていくことを想像してください。その & 演算子は、両方の値が 1 に等しい場合、結果は 1 になり、そうでない場合は 0 になることを意味します。 1 & 1 = 1 , 1 & 0 = 0 , 0 & 0 = 0 および 0 & 1 = 0 . そこで、計算をする。

100
011
----
000

そこで、return文がどのように変換されるかを見てみましょう。

return (4 != 0) && ((4 & 3) == 0);

と訳されるようになりました。

return true && (0 == 0);

return true && true;

私たちは皆、次のことを知っています。 true && true は、単純に true この例では、4は2のべき乗であることがわかります。