Hamming masofasi

Ikkita butun son x va y berilgan. Ularning Hamming masofasini toping.

Hamming masofasi — x va y ning ikkilik ko'rinishlarida farq qiladigan bit pozitsiyalari soni.

Kirish:  x = 1, y = 4
Chiqish: 2

1 = 0001
4 = 0100
      ^^   ← 2 ta pozitsiyada farq qiladi

Kirish:  x = 3, y = 1
Chiqish: 1

3 = 011
1 = 001
     ^    ← 1 ta pozitsiyada farq qiladi

Kirish:  x = 0, y = 0
Chiqish: 0   // bir xil, farq yo'q

Asosiy g'oya: XOR va popcount

XOR (^) operatsiyasi ikki son uchun: - farq qilgan pozitsiyalarda 1 - bir xil pozitsiyalarda 0

1 = 0001
4 = 0100
XOR = 0101   // farqlangan pozitsiyalar 1

Keyin 0101 dagi 1 bitlarni sanash — bu popcount (yoki Hamming weight).

Demak: HAMMING_DISTANCE(x, y) = POPCOUNT(x XOR y).

Pseudocode

FUNCTION HAMMING_DISTANCE(x, y)
    xor_result = x XOR y
    RETURN COUNT_ONES(xor_result)

FUNCTION COUNT_ONES(n)
    count = 0
    WHILE n > 0
        n     = n & (n - 1)   // eng quyi 1 bitni o'chirish
        count = count + 1
    RETURN count

Yoki bitta funksiyada:

FUNCTION HAMMING_DISTANCE(x, y)
    n     = x XOR y
    count = 0
    WHILE n > 0
        n     = n & (n - 1)
        count = count + 1
    RETURN count

Bosqichma-bosqich dry run

x = 1 = 0001, y = 4 = 0100:

n = x XOR y = 0001 XOR 0100 = 0101

Qadam 1:
  n     = 0101
  n & (n-1) = 0101 & 0100 = 0100
  count = 1

Qadam 2:
  n     = 0100
  n & (n-1) = 0100 & 0011 = 0000
  count = 2

n = 0 → to'xtash
RETURN 2

x = 3 = 011, y = 1 = 001:

n = 011 XOR 001 = 010

Qadam 1:
  n     = 010
  n & (n-1) = 010 & 001 = 000
  count = 1

n = 0 → to'xtash
RETURN 1

Vaqt va xotira murakkabligi

Xususiyat	Qiymat	Izoh
Vaqt	`O(1)`	32-bitli sonda ko'pi bilan 32 bit
Xotira	`O(1)`	Bir nechta o'zgaruvchi

Hamming masofasining real qo'llanishlari

Ma'lumotlarni uzatish. Richard Hamming bu masofani raqamli aloqa tizimida xatolarni aniqlash va tuzatish uchun taklif qildi (1950). Uzatilgan va qabul qilingan kod o'rtasidagi Hamming masofasi xatolar sonini ko'rsatadi.

Biometrika. Barmoq izi, yuz yoki iris izi binar vektor sifatida ifodalanadi. Ikki naqsh o'rtasidagi Hamming masofasi ularning o'xshashligini o'lchaydi.

DNK ketma-ketliklari. Ikki DNK zanjirining mos pozitsiyalarida qancha farq borligini aniqlash.

Kriptografiya. Maxfiy kalit va taxmindagi kalit orasidagi farq aniqlashda.

Edge case'lar

x = y: x XOR y = 0, Hamming masofasi 0.

x = 0, y = 0xFFFFFFFF: XOR = 0xFFFFFFFF = 1111...1 — 32 ta 1 bit, masofa 32.

Salbiy sonlar. 32-bitli ishorali sonda salbiy sonlar ikkilik to'ldiruvchida ifodalanadi. x = -1 = 1111...1. Masala ishorali sonlar uchun berilsa, XOR natijasining 1 bitlari hali ham farqlangan pozitsiyalarni to'g'ri ko'rsatadi.

Xulosa

Hamming masofasi — x XOR y dagi 1 bitlar soni. XOR farqlangan pozitsiyalarni belgilaydi, popcount ularni sanaydi.

Ikki bosqich: xor = x ^ y, keyin popcount(xor). Har ikkalasi O(1) — 32-bitli sonda ko'pi bilan 32 operatsiya.