[解決済み] なぜ (n & -n) == n ならば n は 2 のべき乗なのか？

質問

java.util.Randomソースの294行目 は言う

if ((n & -n) == n) // i.e., n is a power of 2
    // rest of the code

これはなぜでしょうか？

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

記述が完全に正確でないのは (0 & -0) == 0 が、0は2の累乗ではありません。 もっと良い言い方をすると

((n & -n) == n) nが2の累乗、または2の累乗の負、または0であるとき。

n が 2 の累乗である場合、2 進法の n は 1 と 0 が続くものとなります。 -2 の補数の n は逆数 + 1 で、ビットはこのように並びます。

 n      0000100...000
-n      1111100...000
 n & -n 0000100...000

なぜこのような仕組みになっているかというと、2の補数とは逆数＋1であると考えるからです。 -n == ~n + 1

n          0000100...000
inverse n  1111011...111
                     + 1
two's comp 1111100...000

を足して2の補数を得るときに、1をずっと繰り越すので。

もしnが2の累乗以外だったら†、2の補数にはそのキャリーによって最高ビットが設定されないので、結果はビットが欠けることになります。

† - またはゼロまたは2のべき乗の負......冒頭で説明したとおりです。