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
--
http://mail.python.org/mailman/listinfo/python-list
