Hamming distance
The conceptFlip one bit and the letter 'A' becomes 'C'
Hamming distance counts the positions where two equal-length strings differ. In ASCII, 'A' is 01000001 and 'C' is 01000011. Only the second bit from the right differs, so their distance is 1.
For bits there's a shortcut. XOR (exclusive or) gives 1 where two bits differ and 0 where they match. So XOR the two values and count the 1s, a count called the popcount.
It only works for strings of the same length, because it compares position 1 with position 1, position 2 with position 2, and so on. It never shifts anything or lines up an inserted character. That's the job of edit distance.
What it’s forCounts how many bits two equal-length binary values differ in.
d(x, y) = popcount(x ⊕ y)
- x, y
- the two bit strings being compared, of equal length, e.g. two 64-bit hashes
- ⊕
- XOR: gives 1 in each position where x and y differ, 0 where they match
- popcount
- the number of 1 bits in a value
- d
- the Hamming distance, from 0 (identical) up to the length in bits
What it givesA single whole number: how many bit flips turn x into y.
- x = 10110, y = 11100
- x ⊕ y = 01010
- popcount(01010) = 2, so d = 2