python - 获得整数数组汉明距离的最快方法

Question

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

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

使用 numpy 库

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

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

Answer 1

方法#1:我们可以将它们广播成二进制位并计算不同位的数量，就像这样-

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

sample 运行-

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

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

方法#2:使用bitwise-xor操作，我们可以找出a和b之间不同二进制位的个数-

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