11

我阅读了有关Hamming Weight的 Wikipedia 文章并注意到一些有趣的事情：

因此它等价于Hamming distance相同长度的全零字符串。对于最典型的情况，一串位，这是字符串中 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. 例如，在没有 的 x64 上popcnt，gcc吐出（Godbolt 的 GCC Online）：

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

OTOH，如果你有一个支持 POPCOUNT 的平台，比如 x64 模型，包括nehalem和之后（有POPCNT），你会得到（Godbolt 的 GCC Online）：

hammingDistance:
    xor rdi, rsi
    popcnt  rax, rdi
    ret

这应该更快，尤其是内联后。

但回到最初的问题。你能用两个字符串的异或的汉明权重来找到它们的汉明距离吗？IE：

HD = HW (x xor y)
4

2 回答 2

6

两个相等长度的字符串之间的汉明距离，x和y，定义为它们不同的位置数。在 和 是位串的情况下x，y是x^y一个字符串，其中1s 恰好位于它们不同的位置。因此，HammingDistance(x,y) = Number of 1s in x^y, 对于位串。此外，HammingWeight(x) = number of 1s in x对于 bitstring x。因此，您的第一个主张HammingDistance(x,y) = HammingWeight(x^y)对于位串是正确的。确定这一点后，很明显您的实现是正确的。

于 2014-08-02T20:23:31.790 回答
3

是的，这行得通。对于每个位，当且仅当输入位不同时，该位才为 1。因此，应用于整个位向量，结果具有与输入具有不同位 (HD) 一样多的一位 (HW)。而且您的代码似乎很好地利用了这种关系。实际上，您链接到的汉明权重文章（高效实现）中甚至进一步提到了此快捷方式：

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

于 2014-08-02T20:21:34.283 回答