Mô phỏng thuật toán Khoảng cách Hamming

Hamming Distance · Nhóm: Bit & Mặt nạ

Khoảng cách Hamming giữa x và y là số vị trí bit khác nhau, tính bằng popcount(x ^ y): XOR cho bit 1 đúng ở nơi hai số khác nhau, rồi đếm số bit 1.

Ý tưởng

Tính z = x ^ y: bit 1 ở nơi x và y khác nhau, bit 0 ở nơi giống nhau.

Đếm số bit 1 của z (popcount) bằng cách lặp count += z & 1, z >>= 1.

Số bit 1 đếm được chính là khoảng cách Hamming.

Vì sao đúng

XOR biến việc so từng cặp bit thành một số duy nhất z đánh dấu mọi vị trí lệch; đếm bit 1 của z gọn gàng cho ra ngay số vị trí khác nhau.

Mã Python

def hamming_distance(x, y):
    z = x ^ y                 # XOR: 1 where bits differ, 0 where equal
    count = 0
    while z:                  # count the set bits of z (popcount)
        count += z & 1        # add the lowest bit
        z >>= 1               # drop it and continue
    return count              # number of differing bit positions

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.