파이썬으로 두 정수의 해밍 거리(Hamming Distance) 계산하기

두 개의 정수가 주어졌을 때, 이 두 수 사이의 해밍 거리(Hamming Distance)를 구하는 문제를 살펴보겠습니다.

해밍 거리란 두 숫자를 이진수로 표현했을 때 서로 다른 비트의 개수를 의미합니다. 예를 들어 7과 15를 이진수로 나타내면 각각 0111과 1111인데, 최상위 비트(MSb)만 서로 다르므로 해밍 거리는 1이 됩니다.

해결 접근 방법

이 문제는 비트 연산을 활용해 다음과 같은 단계로 해결할 수 있습니다.

• i = 31부터 0까지 반복합니다.
  • b1 = x를 i비트만큼 오른쪽 시프트한 후 1과 AND 연산
  • b2 = y를 i비트만큼 오른쪽 시프트한 후 1과 AND 연산
  • 만약 b1과 b2가 같다면 answer에 0을 더하고, 다르다면 answer에 1을 더합니다.
• 모든 반복이 끝나면 answer를 반환합니다.

구현 예제

아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.

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

동작 원리 살펴보기

32비트 정수 기준으로 가장 왼쪽 비트부터 차례대로 검사하며, 각 자리에서 두 수의 비트 값을 추출해 비교합니다. x >> i & 1 연산은 x의 i번째 비트가 0인지 1인지를 알려주며, 두 비트가 일치하지 않을 때마다 카운트를 증가시켜 최종적으로 해밍 거리를 얻게 됩니다.

이 방식은 시간 복잡도 O(1), 즉 고정된 32번의 반복으로 처리되므로 매우 효율적입니다. 파이썬 3.10 이상에서는 내장 함수 (x ^ y).bit_count()를 사용해 XOR 결과의 1 비트 개수를 세는 더 간단한 방법도 활용할 수 있습니다.