Hamming Distance

godavemon davefowler at gmail.com
Fri Jun 20 05:04:04 CEST 2008


Awesome!  Thanks a lot.

On Jun 19, 5:00 pm, Mensanator <mensana... at aol.com> wrote:
> 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