Pythonで数値の最初と最後のビットだけがセットされているかを判定する方法

問題の概要

ある数値 n が与えられたとき、その2進表現において「最初(最上位)」と「最後(最下位)」の位置にのみビットがセットされている(1になっている)かどうかを判定します。

例えば、入力が n = 17 の場合、2進表現は 10001 となり、最初と最後の位置にだけ 1 が存在するため、結果は True になります。

解決のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• n が 1 と等しい場合は True を返します(2進表現が「1」のみで、最初と最後の位置が一致しているため)。
• それ以外の場合は、「n - 1 が 2 のべき乗であるか」を判定します。2のべき乗であれば True、そうでなければ False を返します。

この手法が有効な理由は、最初と最後のビットのみがセットされた数値は「2^k + 1」の形で表せるからです。この値から 1 を引くと「2^k」となり、必ず 2 のべき乗になります。

サンプルコード

def is_pow_of_two(n):
    return (n & n-1) == 0

def solve(n):
    if n == 1:
        return True
    return is_pow_of_two(n-1)

n = 17
print(solve(n))

入力

17

出力

True

ポイント解説

(n & n-1) == 0 というビット演算は、数値が 2 のべき乗かどうかを判定する定番のテクニックです。2 のべき乗の数値から 1 を引くと下位のビットがすべて反転するため、元の数値との AND 演算の結果が 0 になります。この性質を利用することで、ループや除算を使わずに O(1) の計算量で判定が可能です。