两个二进制字符串的汉明距离不起作用

Question

我在这个网站上发现了一个有趣的算法来计算汉明距离：

def hamming2(x,y):
    """Calculate the Hamming distance between two bit strings"""
    assert len(x) == len(y)
    count,z = 0,x^y
    while z:
        count += 1
        z &= z-1 # magic!
    return count

关键在于这个算法只能处理位串，而我正试图比较两个二进制字符串，但它们是以字符串格式表示的，例如：

'100010'
'101000'

如何使用这个算法让它们运作起来？

- Hyperion

---

什么是问题？有任何错误吗？ - Anand S Kumar

bin(int('100010',2)) 会生成二进制。 - Nizam Mohamed

Answer 1

实现它：

def hamming2(s1, s2):
    """Calculate the Hamming distance between two bit strings"""
    assert len(s1) == len(s2)
    return sum(c1 != c2 for c1, c2 in zip(s1, s2))

并测试它：

assert hamming2("1010", "1111") == 2
assert hamming2("1111", "0000") == 4
assert hamming2("1111", "1111") == 0

- dlask

Answer 2

这是我用来计算汉明距离的方法。
它会计算等长字符串之间的差异数量。

def hamdist(str1, str2):
    diffs = 0
    for ch1, ch2 in zip(str1, str2):
        if ch1 != ch2:
            diffs += 1
    return diffs

- Panos Kalatzantonakis

Answer 3

如果我们要坚持原始算法，需要将字符串转换为整数以便使用位运算符。

def hamming2(x_str, y_str):
    """Calculate the Hamming distance between two bit strings"""
    assert len(x_str) == len(y_str)
    x, y = int(x_str, 2), int(y_str, 2)  # '2' specifies we are reading a binary number
    count, z = 0, x ^ y
    while z:
        count += 1
        z &= z - 1  # magic!
    return count

那么我们可以按照以下方式进行调用：

print(hamming2('100010', '101000'))

尽管这个算法很有趣，但需要将其转换为字符串很可能会抵消它可能具有的任何速度优势。@dlask发布的答案更加简洁。

- Adam Hammes

Answer 4

我认为这很好地解释了两个字符串之间的海明距离

def hammingDist(s1, s2):
    bytesS1=bytes(s1, encoding="ascii")
    bytesS2=bytes(s2, encoding="ascii")
    diff=0
    for i in range(min(len(bytesS1),len(bytesS2))):
        if(bytesS1[i]^bytesS2[i]!=0):
            diff+=1
    return(diff)

- Mikheil Zhghenti