「2の何乗であるか」累乗をビット演算で正しく判定する方法

🎯 はじめに

2の累乗判定は、パフォーマンス重視のシステムや競技プログラミングでは頻出の課題です。簡潔・高速に判定できるビット演算テクニックを使った方法を、C++・Pythonそれぞれに実装します。

🧮 ビット演算アルゴリズム

「n が2の累乗ならば、二進法表現ではちょうど1ビットだけ1」であることを利用します。その性質を用いて以下のアルゴリズムが成り立ちます：

n > 0 かつ (n & (n - 1)) == 0 → n は2の累乗

• n - 1 により、最下位の1を0にし、右側のビットをすべて1にします。
• n & (n - 1) が 0 ならば、元々1つしか1ビットがなかった（＝2の累乗）ことを意味します。

✅ C++版

#include <iostream>
using namespace std;

bool is_power_of_two(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

int main() {
    int n;
    cout << "整数を入力してください: ";
    if (!(cin >> n)) return 0;

    if (is_power_of_two(n))
        cout << n << " は2の累乗です。\n";
    else
        cout << n << " は2の累乗ではありません。\n";

    return 0;
}

• n > 0 によって、負数や0を除外。
• ビット操作はO(1)で高速、定数時間で判定できます。
• サンプル入力：
  • 16 → 「2の累乗です」
  • 18 → 「2の累乗ではありません」

🐍 Python版

def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

if __name__ == "__main__":
    n = int(input("整数を入力してください: "))
    if is_power_of_two(n):
        print(f"{n} は2の累乗です。")
    else:
        print(f"{n} は2の累乗ではありません。")

• n <= 0 の場合 False を返す。
• n & (n - 1) を使う定番テクで簡潔に判定。
• 確認例：
  • 32 → 「2の累乗です」
  • 50 → 「2の累乗ではありません」

🛠 比較と応用

• ループや除算なしで定数時間判定が可能。
• 応用例として「任意の整数セットがbitwise ANDで2の累乗になるか？」などにも展開できます。

💡 まとめ

• アルゴリズム：n > 0 && (n & (n - 1)) == 0
• 特長：
  • 余分なループ・除算なしで高速
  • 実装も非常に簡潔
• 言語別対応：C++・Pythonどちらでも直感的に使える