単一のビット演算で数が2のべき乗であるかどうかを判定する
正の整数
n が与えられたとき、それが2のべき乗であるかどうかを調べます。実は、単一のビット演算を使って簡単に判定できます。2のべき乗となる数のビット表現を考えると、ビット列の中に 1 がひとつだけ存在し、それ以外のビットはすべて 0 になっています。2^n の数 | 2進数表現 |
8 | 1000 |
32 | 100000 |
128 | 10000000 |
ランダムな数 | 2進数表現 |
7 | 111 |
67 | 1000011 |
144 | 10010000 |
これは2進数表現の定義からもわかります。ビット列のある位置に1が立っていれば、その位置が表す2のべき乗分が足し合わさります（たとえば 67 = 1 + 2 + 0 + 0 + 0 + 0 + 64、8 = 0 + 0 + 0 + 8）。つまり、ビット列に
1 が一つだけということは、その位置の2のべき乗分だけが含まれていることを意味します。したがって、問題は n のビット列に 1 がちょうど一つだけあるかを確認することになります。この判定を簡単に行う方法として、
n & (n-1) のビットANDを取り、それが0かどうかを確認するやり方があります。計算結果が0であれば、それは2のべき乗です。2のべき乗ではない数に対しては、
n & (n-1) の結果が0にはなりません:- 7 & 6 = 111 & 110 = 110 (6)
- 67 & 66 = 1000011 & 1000010 = 1000010 (66)
- 144 & 143 = 10010000 & 10001111 = 10000000 (128)
しかし、2のべき乗の数では常に結果が0になります:
- 8 & 7 = 1000 & 111 = 0
- 32 & 31 = 100000 & 11111 = 0
- 128 & 127 = 10000000 & 1111111 = 0
💡
直感
n と n-1 を考えると、n のビット表現に最上位ビット以外にも 1 が含まれる場合は、その2つの最上位ビットが保たれます。もし n が2のべき乗であれば、ビット列の中にある唯一の 1 が最上位ビットだけなので、n-1 では最上位ビットが落ちて他のビットが 1 に変わります。
一方、多くの他の数 (6, 67, 144 など) はビット列に複数の 1 を含んでおり、1 を引いても最上位ビットが同じように消えるとは限りません。
入力
入力の最初の行には、整数
n (2 ≤ n ≤ 10^9) が1つ与えられます。出力
もし
n が2のべき乗であれば Yes、そうでなければ No と出力してください。例
Input | Output |
8 | Yes |
17 | No |
2048 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB