Hamming Distance
Hans Terlouw
J.P.Terlouw at astro.rug.nl
Fri Jun 27 10:33:19 EDT 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