Hamming Distance

John Machin sjmachin at lexicon.net
Fri Jun 20 01:51:10 CEST 2008


On Jun 20, 9:27 am, 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

Isn't it a "binary string" already?

> count the # of 1's.

My guess is that counting the 1-bits in (a ^ b) would be hard to beat,
and that a recursive function is just not in the race.

>
> Which would be fastest?

Implement both and time them.

>  Are there better alternatives?

I doubt it.

BTW one presumes that your integers are non-negative ...

HTH

Cheers,
John



More information about the Python-list mailing list