461 Hamming Distance

• 461 Hamming Distance
  • 문제
    • 해밍 거리?
  • 조건
  • 예제
  • 해결
    • 1st
      • 1 생각
      • 1 코드
      • 1 결과: 성공
    • 2nd 리트코드 다른 풀이
      • 2nd 코드

461 Hamming Distance

문제

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, return the Hamming distance between them.

해밍 거리?

• 정보 이론에서, 같은 길이의 두 문자열 사이의 해밍 거리는 해당하는(corresponding) 심볼들이 서로 다른 위치의 수
• 말이 어려운데, 같은 길이의 두 문자열에서 서로 다른 문자가 몇 개 있는지를 찾는 문제라고 보면 될 거 같다

조건

• $0 \le x, y \le 2^{31} - 1$

예제

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.

Input: x = 3, y = 1
Output: 1

해결

1st

1 생각

• 같은 길이에 서로 다른 위치의 수를 찾는 문제니, 136 Single Number와 마찬가지로 XOR을 사용하면 좋을 거 같다

1 코드

import timeit
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        def decimal_to_binary(num, bit = 8):
            result = ""
            while num > 0:
                result = str(num % 2) + result
                num //= 2
            return result.rjust(bit, "0") if bit > 0 else result


        return decimal_to_binary(x ^ y, 0).count("1")

    def hammingDistance2(self, x: int, y: int) -> int:
        return bin(x ^ y).count("1")


s = Solution()

""" print(s.hammingDistance(1, 4))
print(s.hammingDistance(3, 1))
print(s.hammingDistance(0, 0)) 
print(s.hammingDistance(30, 2147483647))"""

print(timeit.timeit(lambda: s.hammingDistance(30, 2147483647), number=100000)) # 0.9807200999999999
print(timeit.timeit(lambda: s.hammingDistance2(30, 2147483647), number=100000)) # 0.04811129999999997

• 문자열로 만들어서 카운트하는 건 역시 시간이 오래 걸린다

1 결과: 성공

Runtime: 28 ms
Memory Usage: 14.2 MB

2nd 리트코드 다른 풀이

2nd 코드

# 12 ms
def hammingDistance3(self, x: int, y: int) -> int:
    m = max(x, y)
    n = min(x, y)

    bits = 0

    while m:
        r1 = m % 2 == 0 
        r2 = n % 2 == 0
        
        if r1 != r2:
            bits += 1
            
        m >>= 1
        n >>= 1
        
    return bits

# 16 ms
def hammingDistance4(self, x: int, y: int) -> int:
    res = x^y
    count = 0
    
    for i in range(32):
        if res&1:
            count+=1
        res = res>>1
        
    return count   

• 다른 풀이 모두
  • 비트를 순차적으로 비교하고,
  • 그 다음 1비트씩 우측으로 쉬프트하여 버리면서
  • 카운트를 하는 로직
• 둘 다 bin().count() 사용보다 더 빠르다고 나와 있는데 timeit으로 테스트 해보면 그렇지가 않다

print(timeit.timeit(lambda: s.hammingDistance(43243, 2147483647), number=10000))  # 0.08998709999999999
print(timeit.timeit(lambda: s.hammingDistance2(43243, 2147483647), number=10000)) # 0.005768099999999998
print(timeit.timeit(lambda: s.hammingDistance3(43243, 2147483647), number=10000)) # 0.06952909999999998
print(timeit.timeit(lambda: s.hammingDistance4(43243, 2147483647), number=10000)) # 0.0418421000000000

• time으로 체크해봐도 bin() 사용하는 hammingDistance2가 가장 빠르다.