在C语言中快速计算汉明距离

Question

我阅读了维基百科关于Hamming Weight的文章并注意到了一些有趣的东西：

因此，它等价于与长度相同的全零字符串的 汉明距离。对于最典型的情况，即一串位，这是该串中1的数量。在这个 二进制情况下，它也被称为种群计数， popcount 或横向求和。

[强调是我的]

所以我想到了一个问题。 我能不能通过对两个字符串进行XOR操作，然后获取结果字符串的汉明重量（POPCOUNT）来计算它们之间的汉明距离？

类似于以下代码（使用gcc内置函数）:

#include <stdint.h>

int hammingDistance (uint64_t x, uint64_t y) {
        uint64_t res = x ^ y;
        return __builtin_popcountll (res);
}

---

至于为什么我想要这样做，嗯，在某些平台上，是的，这只会转化为gcc调用一个计算popcount的函数。例如，在没有popcnt的x64上，gcc输出结果为(Godbolt's GCC Online):

hammingDistance:
    sub rsp, 8
    xor rdi, rsi
    call    __popcountdi2
    add rsp, 8
    ret

另一方面，如果您有一个支持POPCOUNT的平台，例如包括nehalem及其后续型号（具有POPCNT）的x64型号，则可以获得如下的结果（Godbolt的GCC在线版）：

hammingDistance:
    xor rdi, rsi
    popcnt  rax, rdi
    ret

应该会快很多，特别是一旦内联。

---

但回到最初的问题。你能通过计算两个字符串的异或值的汉明重量来找到它们的汉明距离吗？也就是：

HD = HW (x xor y)

- haneefmubarak

---

你是在问两个二进制字符串异或后的汉明重量是否等于它们的汉明距离吗？（答案：是的，这显然可以从定义中得出。）还是你在寻求将这种高效方法推广到一般字符串的方法？ - Pradhan

我想要询问第一个问题，以及我的实现是否也有效。 - haneefmubarak

值得注意的是，popcnt并不总是最快的解决方案。在英特尔Haswell处理器上，AVX2寄存器内查找表方法更快。可以测试各种人口统计方法的实用程序在此处：http://notabs.org/blcutil/。 - user1940376

Answer 1

两个等长字符串x和y之间的海明距离被定义为它们相异位置的数量。如果x和y是位串，则x^y 是在不同位置上恰好具有 1 的字符串。因此，对于位串，HammingDistance(x，y) = x^y中1的数目。同时，对于位串x，HammingWeight(x) = x中1的数目。因此，你的第一个声明，HammingDistance(x,y) = HammingWeight(x^y) 对于位串来说是正确的。经过这样一番论证，显然你的实现是正确的。

- Pradhan

---

两个答案都很好；话虽如此，我会将这个标记为正确的，因为它是第一个。 - haneefmubarak

Answer 2

是的，这可以行得通。对于每个比特位，当且仅当输入的比特位不同时，该比特位为1。因此，应用于整个比特向量时，结果具有与输入具有不同比特位（HD）的不同位数（HW）。而你的代码似乎完美地利用了这种关系。实际上，在你链接到的汉明重量文章进一步提到了这个快捷方式（高效实现）：

两个单词A和B的汉明距离可以计算为A xor B的汉明重量。

- user395760

---

哇，我猜浏览并不总是有效的。将来我会尝试花更多时间真正阅读。 - haneefmubarak