快速计算C中的汉明距离

Question

我读了关于汉明重量的维基百科文章,并注意到一些有趣的东西:

因此它等同于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

这应该更快,特别是一旦内联.

---

但回到最初的问题.你能把两个弦的XOR的汉明重量找到它们的汉明距离吗？即:

HD = HW (x xor y)

Answer 1

两个相等长度的弦之间的汉明距离,x并且y被定义为它们不同的位置的数量.在x和ybittrings 的情况下,x^y是一个字符串,其中1s与它们不同的位置完全相同.因此HammingDistance(x,y) = Number of 1s in x^y,对于位串.另外,HammingWeight(x) = number of 1s in x对于一个位串x.因此,您的第一个主张HammingDistance(x,y) = HammingWeight(x^y)对于位串是正确的.确定后,很明显您的实施是正确的.