ระยะทางแฮมมิงใน Python

พิจารณาว่าเรามีจำนวนเต็มสองจำนวน เราต้องหาระยะทางแฮมมิงของพวกมัน ระยะทางแฮมมิงคือจำนวนบิตที่ต่างกันระหว่างสองตัวเลข เช่นถ้าตัวเลขคือ 7 และ 15 ในทศนิยมสองคือ 0111 และ 1111 ที่นี่บิต MSB ต่างกัน ดังนั้นระยะทางแฮมมิงคือ 1

วิธีการแก้ปัญหา

• สำหรับ i = 31 ลงถึง 0:
  • b1 = เลื่อนขวาของ x (i AND 1 ครั้ง)
  • b2 = เลื่อนขวาของ y (i AND 1 ครั้ง)
  • ถ้า b1 = b2 ให้ answer := answer + 0 มิฉะนั้น answer := 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