获取整数数组汉明距离的最快方法 [英] Fastest way to get hamming distance for integer array

问题描述

让a和b是具有8位整数(0-255)的相同大小的向量.我想计算那些矢量不同的位数，即通过这些数字的二进制表示的级联形成的矢量之间的汉明距离.例如:

Let a and b be vectors of the same size with 8-bit integers (0-255). I want to compute the number of bits where those vectors differs i.e. a Hamming distance between vectors formed by concatenation of binary representations of those numbers. For example:

a = [127,255]
b= [127,240]

使用numpy库

np.bitwise_xor(a,b)
# Output: array([ 0, 15])

我现在需要二进制表示上述数组的每个元素，并在数组的所有元素中计数1.上面的示例的汉明距离为0 + 4 =4.在Python中对此有任何快速而优雅的解决方案吗?

What I need is now to binary represent each element of the above array and count number of 1s in all the elements of the array. The above example will give hamming distance of 0+4 = 4. Any fast and elegant solution for this in Python?

推荐答案

方法1:我们可以将它们广播为二进制位&计算不同位数，就像这样-

Approach #1 : We could broadcast them into binary bits & count number of different bits, like so -

def hamming_distance(a, b):
    r = (1 << np.arange(8))[:,None]
    return np.count_nonzero( (a & r) != (b & r) )

样品运行-

In [144]: a = [127,255]
     ...: b = [127,240]
     ...: 

In [145]: hamming_distance(a, b)
Out[145]: 4

方法2::使用 查看全文