Pythonでハミング距離を求める方法

ハミング距離とは

2つの整数が与えられたとき、それらの「ハミング距離」を求めることを考えます。ハミング距離とは、2つの数値を2進数で表したときに、ビットが異なる位置の個数のことです。

例として、7と15という2つの整数を見てみましょう。これらを2進数で表すと、それぞれ「0111」と「1111」になります。最上位ビット（MSb）だけが異なるため、この場合のハミング距離は1となります。

解法のアプローチ

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

• i を31から0まで1ずつ減らしながら繰り返します。
  • b1 = x を i ビット右シフトした値と1のAND（最下位ビットの取り出し）
  • b2 = y を i ビット右シフトした値と1のAND
  • b1 と b2 が等しければ答えに0を加算し、等しくなければ1を加算します。
• 最終的な答えを返します。

つまり、各ビット位置ごとに両者の値を比較し、異なっていればカウントを増やしていくというシンプルな方法です。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        ans = 0
        for i in range(31,-1,-1):
            b1 = x>>i&1
            b2 = y>>i&1
            ans += not(b1==b2)
        return ans

ob1 = Solution()
print(ob1.hammingDistance(7, 15))

入力

7
15

出力

1

コードのポイント

• 右シフト演算（>>）：x >> i により、i 番目のビットを最下位ビットの位置まで移動させます。
• AND演算（&1）：移動後の最下位ビットのみを抽出することで、特定の位置のビット値を取得できます。
• not(b1==b2)：Pythonでは真偽値は整数として扱えるため、ビットが異なる場合にTrue（=1）が加算されます。

なお、Pythonでは bin(x ^ y).count('1') のようにXORと文字列カウントを組み合わせることで、より簡潔にハミング距離を求めることも可能です。XORを取ると異なるビット位置だけが1になる性質を利用した方法です。