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.

해밍 거리?

조건

예제

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 생각

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   

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