Hamming Distance - Algorithm Example

Algorithm Example

The Python function hamming_distance computes the Hamming distance between two strings (or other iterable objects) of equal length, by creating a sequence of zero and one values indicating mismatches and matches between corresponding positions in the two inputs, and then summing the sequence.

def hamming_distance(s1, s2): assert len(s1) == len(s2) return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))

The following C function will compute the Hamming distance of two integers (considered as binary values, that is, as sequences of bits). The running time of this procedure is proportional to the Hamming distance rather than to the number of bits in the inputs. It computes the bitwise exclusive or of the two inputs, and then finds the Hamming weight of the result (the number of nonzero bits) using an algorithm of Wegner (1960) that repeatedly finds and clears the lowest-order nonzero bit.

unsigned hamdist(unsigned x, unsigned y) { unsigned dist = 0, val = x ^ y; // Count the number of set bits while(val) { ++dist; val &= val - 1; } return dist; }