Hamming Distance

Hans Terlouw J.P.Terlouw at astro.rug.nl
Fri Jun 27 16:33:19 CEST 2008


godavemon wrote:
> I need to calculate the Hamming Distance of two integers.  The hamming
> distance is the number of bits in two integers that don't match.
> ...

What about letting the bits count themselves in a parallel adding scheme:

def hamming(i, j):
    i ^= j
    i = ((i&04444444444)>>2)+((i&022222222222)>>1)+(i&011111111111)
    i = ((i&07070707070)>>3)+(i&030707070707)
    return int(i%63)

This should work for 32-bit integers as from Python 2.4. For earlier Pythons the 
result of i^j must be positive, effectively limiting i and j to 31 bit integers.

I didn't do any speed comparisons with other methods.

Hans



More information about the Python-list mailing list