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

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สำหรับ i =31 เหลือ 0
  • b1 =การเลื่อนขวาของ x (i AND 1 ครั้ง)
  • b2 =การเลื่อนขวาของ y (i AND 1 ครั้ง)
  • ถ้า b1 =b2 ให้ตอบ :=answer + 0 มิฉะนั้น ให้ตอบ :=answer + 1
• ส่งคืนคำตอบ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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)
         #if not(b1==b2):
            # print(b1,b2,i)
      return ans
ob1 = Solution()
print(ob1.hammingDistance(7, 15))

อินพุต

7
15

ผลลัพธ์

1