Hamming Distance

[Robert Kern]

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