Pythonで2つの数値のバイナリ表現がアナグラムかどうかを判定する方法

はじめに

2つの整数 x と y が与えられたとき、それぞれのバイナリ（2進数）表現が互いにアナグラム（桁の並べ替え）の関係にあるかどうかを判定する方法を紹介します。

例として、x = 9、y = 12 のケースを考えてみましょう。9 の2進表現は「1001」、12 の2進表現は「1100」です。「1001」の桁を入れ替えると「1100」と一致するため、この2つはアナグラムの関係にあり、結果は True になります。

解決のアプローチ

この問題は、とてもシンプルな考え方で解くことができます。2進表現を構成するのは「0」と「1」だけなので、両者に含まれる「1」の個数（セットビット数）を比較すればよいのです。

• x と y の2進表現における「1」の個数が同じ場合 → True を返す
• それ以外の場合 → False を返す

実装例

def set_bit_count(num) :
    cnt = 0
    while num:
        cnt += num & 1
        num >>= 1
    return cnt
def solve(x, y) :
    if set_bit_count(x) == set_bit_count(y):
        return True
    return False
x = 9
y = 12
print(solve(x, y))

set_bit_count 関数では、ビット演算 num & 1 によって最下位ビットが「1」かどうかを確認し、num >>= 1 で右シフトしながら数値全体を走査することで、セットビットの総数を数えています。この処理を x と y の両方に適用し、結果が一致するかどうかを比較しているわけです。

入力

9, 12

出力

True

補足：より簡潔な書き方

Python では、組み込み関数 bin() を使うことで、セットビット数をさらに簡単に求められます。

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

bin(x) は数値を「0b1001」のような2進数文字列に変換するため、その文字列に含まれる「1」をカウントするだけでセットビット数が得られます。可読性を重視する場合はこちらの方法がおすすめです。

まとめ

2進表現のアナグラム判定は、「1」の個数が一致するかどうかを確認するだけで実現できます。ビット演算を使った実装でも、bin() を使った実装でも、どちらも計算量は数値のビット長に比例する程度で、非常に効率的に処理できます。