Hamming Distance
Robert Kern
robert.kern at gmail.com
Fri Jun 20 02:02:13 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. I
> thought there'd be a function in math or scipy but i haven't been able
> to find one. This is my function but it seems like there should be a
> faster way. I do this computation many times and speed up is
> important.
>
> def hamdist( a, b , bits = 32):
> def _hamdist( x, bits):
> if bits:
> return (x & 1) + _hamdist(x >> 1, bits-1)
> return x & 1
> return _hamdist( a ^ b, bits)
>
>
> Another alternative would be to convert the XOR to a binary string and
> count the # of 1's.
>
> Which would be fastest? Are there better alternatives?
I think this works:
In [26]: hexbits = {'0': 0,
....: '1': 1,
....: '2': 1,
....: '3': 2,
....: '4': 1,
....: '5': 2,
....: '6': 2,
....: '7': 3,
....: '8': 1,
....: '9': 2,
....: 'A': 2,
....: 'B': 3,
....: 'C': 2,
....: 'D': 3,
....: 'E': 3,
....: 'F': 4}
In [28]: def hamming(a, b):
....: return sum(hexbits[h] for h in hex(a^b)[2:])
....:
In [29]: hamming(1,1)
Out[29]: 0
In [30]: hamming(1,2)
Out[30]: 2
In [31]: hamming(2,2)
Out[31]: 0
In [32]: hamming(2,3)
Out[32]: 1
This might be a wee faster, I haven't timed it:
sum(map(h.get, hex(a^b)[2:]))
--
Robert Kern
"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco
More information about the Python-list
mailing list