The Hamming distance between two strings of the same length is the number of positions in which the corresponding symbols are different. This metric, proposed by Richard W. Hamming in his seminal paper "Error Detecting and Error Correcting Codes", Bell System Technical Journal 26(2):147-160 (1950), also expresses the least number of (intended or unintended) substitutions needed to change one string to another.

Here is a Wikipedia image with a brief explanation and examples:

Example: Hamming Distance between ATCGATCG and ATCCATGG is 2.

Besides being used in computer- and communications-related fields such as information theory, coding theory, and cryptography, the Hamming distance concept has also found its way into genomics for the comparison of genomic sequences. Its importance can also be judged by the fact that modern microprocessors have a specific instruction (POPCNT, "population count") for counting the number of bits set to 1.

Assuming two bit strings of equal length, x and y, the 'obvious' algorithm to calculate the Hamming distance between them is to count the number of bits in the result of the expression 'x xor y', as shown in the following Python code:

1 2 3 4 5 6 7 8 9 | `def` `hamming1(x,y):` ` ` `"""Calculate the Hamming distance between two bit strings"""` ` ` `assert` `len` `(x) ` `=` `=` `len` `(y)` ` ` `count,z ` `=` `0` `,` `int` `(x,` `2` `)^` `int` `(y,` `2` `)` ` ` `while` `z:` ` ` `if` `z&` `1` `:` ` ` `count ` `+` `=` `1` ` ` `z >>` `=` `1` ` ` `return` `count` |

While searching the web the other day, I have come across a very elegant algorithm for the same purpose, which can be coded in Python as follows:

1 2 3 4 5 6 7 8 | `def` `hamming2(x,y):` ` ` `"""Calculate the Hamming distance between two bit strings"""` ` ` `assert` `len` `(x) ` `=` `=` `len` `(y)` ` ` `count,z ` `=` `0` `,` `int` `(x,` `2` `)^` `int` `(y,` `2` `)` ` ` `while` `z:` ` ` `count ` `+` `=` `1` ` ` `z &` `=` `z` `-` `1` `# magic!` ` ` `return` `count` |

Apart from being 50% faster than the first one, its simplicity is awesome! After being counted, the lowest-order nonzero bit is cleared .

## Comments