汉明距离怎么算:从二进制异或数 1 到纠错码与图片查重

汉明距离这个名字听着抽象,定义其实只有一句话:两个等长的串,把它们按位置一格一格对齐,数出对不上的位置有几个,这个个数就是汉明距离。它不插入、不删除,只做位置对位置的比较,所以两边必须长度完全相同,否则这个距离根本没有定义。

一个最小的例子:数对应位不同的个数

先看二进制。1011 和 1001 摆在一起:

1 0 1 1
1 0 0 1
    ^

逐位看,第一位都是 1,第二位都是 0,第三位一个 1 一个 0,第四位都是 1。只有第三位对不上,所以汉明距离是 1。

再换一个极端的:1010101 和 0101010,七位里每一位都不同,距离就是 7。字符串也是同理,课本里常用的例子是 karolin 对 kathrin,第 3、4、5 位分别是 r 对 t、o 对 h、l 对 r,其余都对得上,距离是 3。

整个过程就是这么朴素,没有递归也没有动态规划。你可以在 /zh/t/hamming-distance/ 里直接把两个串填进去,不同的位置会并排高亮出来,省得自己用手指点。

二进制为什么是异或后数 1

如果两个输入是整数,逐位对齐听起来要先转二进制、再补前导零,很麻烦。其实有个更干净的办法:把两个数异或,再数结果里有几个 1。

异或的规则是相同得 0、不同得 1。所以两个数异或之后,凡是原来某一位相同的地方都变成 0,凡是不同的地方都变成 1。于是异或结果里 1 的个数,正好就是两个数对应位不同的个数,也就是汉明距离。

举例,42 的二进制是 101010,13 是 001101,异或得到 100111,里面有四个 1,所以距离是 4。数 1 的位个数这件事有个专门的名字,叫 popcount,也叫汉明权重。

这里有个常被忽略的细节:补几个前导零完全不影响结果。0001 对 0010 和 1 对 2,异或后都只有两个 1,距离都是 2,因为高位补的 0 异或 0 还是 0,不贡献任何 1。所以别在输入前手动补零。

和编辑距离差在哪

很多人把汉明距离和编辑距离(Levenshtein)搞混,这是最容易踩的坑。

编辑距离除了替换,还允许插入和删除,所以能比对不等长的串。kitten 变 sitting 的编辑距离是 3。汉明距离只允许替换,拿一个位置对另一个位置比,因此要求两边等长。

它们只有在不涉及插入删除时才一致。abc 对 acb,汉明数出 2 次替换,编辑距离也是 2;可一旦出现错位一格的情况,两者会立刻分叉。判断标准很简单:两个输入天然对齐、长度固定时用汉明,比如两段定长编码或两个寄存器;一个串可能多出或少了字符时,就该用编辑距离,这时可以转去 /zh/t/text-diff/ 看逐行逐字的差异。

它到底用在哪里

汉明距离是检错和纠错码的根基。一段最小汉明距离为 d 的编码,能检出最多 d 减 1 个比特错误,能纠正其中一半。所以设计定长编码时,你会去测所有码字两两之间的距离,只要有一对测出来是 2,这一对就太近,它们之间的单比特错误就纠不了。

第二个常见场景是相似哈希。感知哈希(pHash)或局部敏感哈希会把一张图、一段内容压成一串定长比特,两个哈希的比特距离很小就算近似匹配。查重图片时,把两张图各自的 64 位 pHash 按整数异或、数 1 的位,距离小于约 10 通常就是同一张图换了尺寸或压缩率,距离很大才是真的不同图片。

它还出现在 DNA 序列比对、通信传输的误码统计,以及在二进制向量上做最近邻搜索的场景里。本质都一样:输入天然等长且按位对齐,数差异个数就够了。

我自己的踩坑

我第一次用汉明距离做图片去重时,把两个 pHash 当成普通十进制数相减,结果一堆明显是同一张的图被判成不同。后来才反应过来,相减比的是数值大小,而我要的是有几位不一样,这两件事毫不相干。换成异或后数 1,误判立刻没了。如果你想顺手看看这些数在二进制下到底长什么样,可以拿 /zh/t/base-converter/ 把十进制和二进制来回换一下,对着比特看会清楚很多。

汉明距离就是这么一个定义短、用途广的小工具:数对应位不同的个数,二进制下等价于异或后的 popcount。记住它和编辑距离的分界线,知道什么时候该等长对齐、什么时候该容忍插入删除,你就不会再把两个数字相减当成相似度了。

Made by Toolora · Updated 2026-06-13