Hamming Distance

The Hamming distance between two equal-length strings is the number of positions where they differ.

Definition

The Hamming distance counts the positions at which two strings of equal length disagree. Between 1011 and 1001 the distance is 1, because they differ in a single bit.

Computing it for bits

Kronos motion — number counters

For two integers, XOR them and count the 1 bits in the result. Each 1 marks a position where the values differed, so the population count of the XOR is the Hamming distance.

Minimum distance of a code

A code's error-handling power comes from its minimum distance, the smallest Hamming distance between any two valid codewords. Codewords spaced far apart are hard to confuse even after several bit flips.

Detection and correction bounds

A code with minimum distance d can detect up to d−1 errors and correct up to ⌊(d−1)/2⌋ errors. This is why single-error correction needs distance 3 and double-error detection needs distance 4.

Beyond error codes

Hamming distance also measures dissimilarity in fields such as bioinformatics, information retrieval, and clustering, wherever two fixed-length sequences must be compared position by position.

python

def hamming(a, b):
    return bin(a ^ b).count('1')
print(hamming(0b1011, 0b1001))  # 1
print(hamming(0b0000, 0b1111))  # 4