Pythonで2つの数値が1ビットだけ異なるかどうかを判定する方法

はじめに

2つの整数 x と y が与えられたとき、これらの数値が1ビット位置だけ異なっているかどうかを判定する方法を解説します。

例えば、x = 25、y = 17 の場合を考えてみましょう。それぞれ2進数に変換すると、x = 11001、y = 10001 となります。比較してみると、異なるのは1ビット位置のみです。この場合、判定結果は True になります。

解決のアプローチ

この問題は、XOR(排他的論理和)を使うことで効率的に解決できます。手順は以下の通りです。

• x と y のXORを計算して z とする
• z に含まれるセットビット(1になっているビット)の数を数える
• セットビットの数が1であれば True を返す
• それ以外の場合は False を返す

XOR演算では、同じビット位置の値が異なる場合にのみ結果が1になります。つまり、2つの数値が1ビットだけ異なるのであれば、XORの結果には必ずセットビットが1つだけ含まれることになります。この性質を利用することで、シンプルかつ確実に判定が可能です。

サンプルコード

def bit_count(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

def solve(x, y):
    return bit_count(x ^ y) == 1

x = 25
y = 17
print(solve(x, y))

上記のコードでは、まず bit_count 関数で数値のセットビットの数を数えています。ビットごとのAND演算(n & 1)で最下位ビットを取り出し、右シフト(n >>= 1)を繰り返すことで全ビットを走査します。その後、solve 関数内で x と y のXORを計算し、その結果のセットビット数が1かどうかを返しています。

入力

x = 25, y = 17

出力

True

補足:より簡潔な書き方

Pythonでは、組み込み関数 bin() を使えば、セットビットのカウントをさらに簡潔に記述できます。

def solve(x, y):
    return bin(x ^ y).count('1') == 1

また、Python 3.10以降では (x ^ y).bit_count() メソッドを直接使うこともできるため、環境に応じて選択するとよいでしょう。

まとめ

2つの数値が1ビットだけ異なるかどうかの判定は、「XORを取ってセットビットの数を数える」というアプローチで簡単に実装できます。計算量はビット長に依存するものの、非常に軽量な処理のため、ハミング距離の計算やエラー検出など、さまざまな場面で応用できるテクニックです。