Hamming Distance

godavemon davefowler at gmail.com
Thu Jun 19 19:27:58 EDT 2008


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?

Thanks!



More information about the Python-list mailing list