Hamming Distance
Mensanator
mensanator at aol.com
Fri Jun 20 02:00:44 CEST 2008
On Jun 19, 6:27 pm, godavemon <davefow... at gmail.com> 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?
Yep, use the gmpy module.
>>> import gmpy
>>> help(gmpy.hamdist)
Help on built-in function hamdist in module gmpy:
hamdist(...)
hamdist(x,y): returns the Hamming distance (number of bit-
positions
where the bits differ) between x and y. x and y must be mpz, or
else
get coerced to mpz.
>>> gmpy.hamdist(15,6)
2
>>> gmpy.hamdist(2**177149,10**53330)
61877
>>> gmpy.hamdist(2**177149-1,10**53330)
115285
>
> Thanks!
More information about the Python-list
mailing list