做图片去重项目的时候我在真实业务里第一次彻底搞懂了汉明距离。当时手里有十几万张用户上传的商品图重复上传率接近三成靠文件名匹配根本拦不住。最后落地方案是每张图生成一个64位的感知哈希指纹然后两两比较汉明距离小于阈值就判定为重复。后来刷LeetCode刷到第461题看到题目名字写着“汉明距离”心里咯噔一下——这不就是我天天在用的那个距离吗但实话实说把它写成一两行代码交上去和真正理解它的来龙去脉、知道它为什么有这么大威力完全是两码事。这篇文章就把这件事聊透。先讲461题怎么解再拆解背后的位运算原理然后把它从刷题场景拉到真实世界通信纠错、图片查重、基因比对全都在用同一把尺子量“差异”。适合刚接触位运算的刷题党也适合做图像去重、相似度检索、内容指纹这类工程需求的朋友。放心我尽量说人话复杂的部分会用具体数字一步步推给你看。1. 汉明距离到底在算什么从LeetCode 461说起1.1 先看题题目其实就一句话461.汉明距离的题目描述非常简短两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y计算并返回它们之间的汉明距离。题目给了一个示例x 1y 4。1 的二进制是 0001高位补零后4 的二进制是 0100逐位对齐看第0位是1和0不同第1位是0和0相同第2位是0和1不同第3位都是0相同。所以答案是 2。我第一次看到这道题的时候觉得很奇怪为什么叫“汉明距离”这么学术的名字后来查了一下才知道这个距离是通信领域的一个基础概念跟汉明码、纠错编码这些听起来就很硬核的东西绑在一起。题目给的条件其实很宽松x 和 y 是非负整数范围是 [0, 2^31)。这意味着你可以把所有输入都当成 32 位以内的无符号整数来算不用担心负数补码的干扰。搞清楚这个前提很重要后面讲踩坑的时候会专门展开。1.2 提出这个概念的人研究的是“信号传错了怎么办”汉明距离这个名字来自美国数学家理查德·汉明Richard Hamming。他在贝尔实验室工作的时候主要研究一个非常实际的问题信号在传输过程中会发生比特翻转0 变成 11 变成 0。接收端怎么知道数据被改了呢又怎么能尽量恢复出原始数据呢汉明的核心想法是把合法的编码看成集合里的点点和点之间定义一种“距离”。如果两个合法编码之间的距离太近传输中随便翻几个比特就可能从 A 变成另一个合法编码 B接收端根本察觉不到出错了。反过来如果所有合法编码两两之间的距离都足够大那么传输中翻了少数几位后接收端一看“这不在合法集合里”就知道出错还能按“离谁最近”的原则猜回原始数据。这个“距离”就是汉明距离两个等长字符串对应位置上有多少个字符不一样。这里的“字符串”不一定是文本字符串二进制串、DNA序列、任意符号序列都适用。一个很直观的类比汉明距离就像单词之间的“改动程度”。cat 和 bat 只有第一个字母不同距离是 1cat 和 dog 三个字母全不一样距离是 3。计算机世界里没有字母只有比特但逻辑完全一致。0101 和 0100 相当于“差一个字母”的两个单词0101 和 1010 则是四个位置全不一样。另外要区分一个孪生概念汉明权重Hamming weight指的是一个二进制数中 1 的个数。比如 0101 的汉明权重是 2。从定义上看汉明权重其实就是“这个数跟全 0 数字之间的汉明距离”。461 这道题考的正是一个组合动作先算两个数之间的异或再数结果里的 1也就是先求“差异位置”再求“差异数量”。理解到这一层题目就已经拿下了。2. 位运算是这道题的核心先异或再数12.1 为什么第一步永远是异或如果不用位运算直接的做法是把 x 和 y 都转成二进制字符串补零到相同长度然后逐位比较。这个思路没错但它把“比较”这个动作做成了 O(len) 的字符串遍历在代码里凭空造出两个临时字符串既慢又费内存。更聪明的做法是让硬件替你做逐位比较这个硬件指令就是异或XOR。异或运算的规则非常简单0 ^ 0 00 ^ 1 11 ^ 0 11 ^ 1 0翻译成人话就是相同为 0不同为 1。你发现没有这个真值表本身就是“对应位是否不同”的判断。所以 x ^ y 的结果里二进制位为 1 的位置恰好就是 x 和 y 不同的位置。异或把“找出所有不同位”这件事从 O(len) 的逐位比较压缩成了一条 CPU 指令。这也是异或在面试题里反复出现的原因。它有三个非常实用的身份无进位加法11 在本位变成 0往前的进位被丢弃、可逆运算a ^ b ^ b 等于 a自己和自己异或等于 0、以及这里的“差异探测器”。大多数“找出不同”“消除重复”的位运算题本质上都是围绕这三点做文章。2.2 拿到异或结果之后数1的三种姿势姿势一内置方法一行代码现代 CPU 基本都有 popcount 指令专门统计一个整数的二进制表示里有几个 1。Python 3.10 开始把这条能力暴露成 int.bit_count()Java 里是 Integer.bitCount()C 里是 __builtin_popcount()。用这种方法代码可以写到极简def hammingDistance(x: int, y: int) - int: return (x ^ y).bit_count()如果你刷题用的 Python 版本在 3.10 以上直接这么写就完事了。这一行代码的时间复杂度在语义上是 O(1)因为 CPU 一条指令就能统计完属于刷题时的最优解。姿势二逐位检查最容易想如果面试环境不让你用内置函数或者你想把原理讲得更清楚就用循环逐位检查def hammingDistance(x: int, y: int) - int: xor x ^ y count 0 while xor: count xor 1 xor 1 return count每次用 xor 1 看最低位是不是 1然后把 xor 右移一位。循环次数是 xor 的二进制位数对 32 位整数来说最多 32 次。这个写法的好处是只依赖两个基础操作与、右移不容易出问题也容易解释给同事听。姿势三布莱恩·克尼根算法位运算爱好者的浪漫第三种方法是把统计过程也换成位运算。核心是这样一个公式n n (n - 1)这一行会把 n 最右边的那个 1 直接清零。def hammingDistance(x: int, y: int) - int: xor x ^ y count 0 while xor: xor xor - 1 count 1 return count为什么 n (n - 1) 能消掉最右边的 1因为 n 减 1 的时候会把最右边的 1 变成 0同时让这个 1 右边的所有 0 都变成 1。拿 1100 举例n 是 1100n-1 是 1011二者按位与结果是 1000——最右边的那个 1 确实没了。循环几次就消了几个 1所以循环次数等于 1 的个数而不是二进制总位数。如果 xor 里 1 很少这个写法会比姿势二快不少。方法时间复杂度空间复杂度适用场景内置 bit_countO(1)CPU popcount 指令O(1)刷题/工程首选Python 3.10逐位检查O(k)k 为二进制位数O(1)讲原理、兼容老环境克尼根算法O(m)m 为 1 的个数O(1)位运算面试加分项、1 稀疏的场景选择建议笔试时写内置方法通常是允许的因为语言本身提供了这个能力不算作弊。工程代码里也建议优先用内置方法它直接映射到 CPU 指令比手写循环都快。教学或写文章时我会把三种都摆出来因为“能把原理讲明白”在面试里往往比“答案对”更重要。3. 手推一遍从输入到答案的完整轨迹3.1 两个数字的完整运算流程用 x1, y4 来完整走一遍。1 的二进制是 00014 的二进制是 0100逐位比较第 0 位1 和 0 不同第 1 位0 和 0 相同第 2 位0 和 1 不同第 3 位0 和 0 相同所以差异位有 2 个答案就是 2。用异或算一遍更直观。1 ^ 4 0001 ^ 0100 0101也就是十进制 5。接下来统计 5 的二进制里有几个 10101 有 2 个答案也是 2。你看整个过程其实只有两步x ^ y然后数 1。我再举一个稍微复杂点的例子这两个数是我当年刷题时习惯拿来手算验证的x93, y73。93 的二进制是 101110173 的二进制是 1001001。逐位对齐第一位都是 1相同第二位 0 和 0相同第三位 1 和 0不同第四位 1 和 1相同第五位 1 和 0不同第六位 0 和 0相同第七位 1 和 1相同。所以差异位是 2 个。用异或验证93 ^ 73 2020 的二进制是 10100里面有 2 个 1。答案同样是 2。这种手算练习特别值得做因为你会发现“逐位比较”和“异或后数1”结果完全一致整个算法逻辑就被验证闭环了。3.2 三种写法的时间和空间实测对比我在本地用 Python 对三种解法各跑了 100 万次输入是 0 到 2^31 之间随机生成的一对整数。结果大致是内置 bit_count 最快克尼根算法次之逐位检查略慢一点bin(x ^ y).count(1) 反而是最慢的因为字符串转换的开销比位运算大得多。实际上 LeetCode 的测试用例下这三种写法都能轻松通过运行时间差异在十几毫秒以内刷题阶段不用过度纠结。到了工程项目里性能差异会被放大。比如我在做图片去重时十几万张图会产生几千万次指纹比较每次比较多花 50 纳秒整体就要多几分钟。所以能用内置 popcount 就用这是真实工程里会注意的细节。空间复杂度方面三种写法都是 O(1)除了 bin(x^y).count(1) 会创建一个临时字符串内存是 O(k)。在 LeetCode 上这种空间开销无所谓但在嵌入式或受限环境下尽量避免字符串转换的写法。3.3 到底选哪种刷题和工程各取所需我给自己定了一个简单的选择规则面试写题先解释“汉明距离 异或结果中 1 的个数”然后写内置方法并顺口提一句“底层是 CPU 的 popcount 指令”。能主动说出底层指令面试官通常会高看一眼。工程代码直接用内置方法优先保证可读性和性能。给别人讲题/写文章逐位检查和克尼根算法都要展示这才是吃透原理的关键。如果你用的是老版本 Python没有 int.bit_count()那就用克尼根算法它不依赖版本而且代码照样简短优雅。4. 汉明距离有什么用从通信纠错到图片去重4.1 通信纠错最小距离决定编码的“免疫力”回到汉明提出这个概念的地方。通信系统里经常出现比特翻转比如发送 000接收端收到 001这算不算出错要回答这个问题得先知道合法编码有哪些。汉明码7,4码是经典的例子有效数据 4 位加上 3 位校验位组成 7 位码字。设计时保证了任意两个合法码字的汉明距离至少是 3。这个 3 意味着什么根据编码理论里的结论如果一套编码的最小汉明距离是 d那它可以检测出 d-1 位错误可以纠正 (d-1)/2 位错误向下取整。距离为 3 时能检出 2 位错误能纠正 1 位错误。用刚才的思路理解如果合法码字只有 000 和 111最小距离是 3。接收端收到 001 时数一下它跟 000 的距离是 1跟 111 的距离是 2按“就近原则”判定它最可能是 000于是错误被纠正了。但如果收的是 011它到 000 的距离是 2到 111 的距离也是 1按最小距离判断会判成 111而原始如果是 000 就纠错了。所以距离为 3 的编码没法处理 2 位错误只能检错。这个“距离越大纠错能力越强”的思想是整个纠错码家族的基石。CRC 校验、RS 码、LDPC 码在设计时核心指标之一就是最小汉明距离。很多做网络协议的人不一定天天算汉明距离但他们在选校验方案时本质上都在做这个权衡。4.2 图像去重感知哈希里的64位指纹这是我真正用过汉明距离的地方。图片去重的做法是把每张图缩放到固定尺寸转灰度做 DCT 变换取低频系数根据中位数二值化最终得到一个 64 位的二进制指纹。这个过程叫感知哈希pHash。听起来复杂但最终产物很简单一张图对应一个 64 位整数。比较两张图是否相似就是比较这两个整数的汉明距离。距离小于等于 10一般认为相似大于 10基本就是不同图片。这个 10 是业界多年调出来的经验阈值不是拍脑袋定的。我自己的实操经验是阈值 10 在电商商品图场景里偏宽松容易把同款不同颜色、不同角度的图也判成重复。后来我把颜色特征单独抽出来参与加权判断或者先用 64 位指纹的前 32 位做粗筛再对候选集细算完整汉明距离。这样既控制误判又把千万次全量比较降成了几十万次候选比较性能立刻上来了。除了图片文本去重也常用 simhash。网页正文抽成 64 位 simhash 指纹两两比较汉明距离小于等于 3 通常视为近似重复文章。音频指纹Chromaprint也是同一个套路提取指纹后比较汉明距离识别听歌识曲里的近似匹配。这些场景的共同特点是先把高维数据压成一个定长的比特串然后用汉明距离处理“相似度”问题。4.3 生物信息与网络两个意想不到的邻居在生物信息里两条等长的 DNA 序列做比对统计对应位置的碱基是否相同差异数就是汉明距离。比如 ATCGGTA 和 ATCGCTA 在第 5 位不同G 和 C距离是 1。基因测序里常说的 SNP 位点本质上就是在人类基因组某一位置上的碱基与参考序列不同单个 SNP 的距离就是 1。当然如果两条序列长度不一样就需要用到更复杂的编辑距离或序列比对算法那是另一个话题了。在网络硬件和通信协议里汉明距离也有身影。最直白的是 MAC 地址48 位的网络硬件地址厂商分配时会尽量避免地址之间距离过近保证区分度。在无线通信中调制解调器选择调制方式、纠错编码时都要看星座点或码字之间的最小汉明距离因为它直接决定误码率的上限。我这几年做项目的感受是汉明距离看似是个刷题概念实际上是一个跨越多个领域的通用度量。凡是“两个定长对象差多少”的问题几乎都能套用。它像是计算机世界里的一把卡尺量不了复杂形状但量“差异”这件事又快又准。5. 新手最容易踩的四个坑5.1 第一坑把两个数分别转二进制字符串再逐位比这种思路不是不能 AC但是把简单问题做复杂了。有些新手写出来是bin(x)[2:].zfill(32)bin(y)[2:].zfill(32)然后 for 循环逐位比较。代码又长又容易出错而且面试官一问“还能更快吗”就卡住。正确方向是一开始就想我需要的是“不同的位置”异或操作天生就是干这个的。先把两个数变成一个数x ^ y问题就化简为“这个数里有多少个 1”。从“两个数的差异”到“一个数的位统计”这个抽象过程就是这道题的全部考点。5.2 第二坑忽略负数场景LeetCode 461 明确写了 x 和 y 是非负整数所以刷题时不用考虑负数。但把这段代码搬到真实项目时如果输入变成负整数事情就复杂了。在 Java 里int 是 32 位补码表示-1 的二进制是 32 个 1Integer.bitCount(-1) 的结果是 32。在 Python 里负数在无限长的二进制补码表示下 -1 是无穷多个 1所以 int.bit_count() 对负数的结果也符合补码语义。如果你期望的是“数学绝对值对应比特位的差异”那就得先取绝对值或者按无符号解释。真实工程里一旦碰到负数先明确语义再动手。注意刷题时题目限定非负整数所以这道题能放心大胆用位运算。但同样的代码放到生产环境如果数据源没有保证非负一定要先做前置校验或按固定宽度转无符号处理。5.3 第三坑把汉明距离和编辑距离混为一谈面试里真有人把这两个概念搞混。汉明距离只适用于等长序列只统计对位替换编辑距离允许插入、删除、替换三种操作给出了把 A 变成 B 的最少操作次数。“abc”和“ab”不能说汉明距离是 1因为长度不等根本没法逐位对齐编辑距离是 1因为删掉 c 就行。LeetCode 72 是编辑距离461 是汉明距离别混。实际上这两类距离对应两类完全不同的应用汉明距离适合固定长度编码的场景指纹、校验码、定长序列编辑距离适合自然语言、可变长度序列的场景。选错了度量方式结果可能错得离谱。5.4 常见坑速查表错误做法错误原因正确做法分别转二进制字符串再比较额外开销大、代码繁琐先 x ^ y 再用位统计固定循环 32 次Python 大整数会超写死上限不通用while xor 直到为 0while 里写 xor - 1 而不是 xor 1移位写成减一会死循环右移用 对负数直接用 bit_count补码语义下的 1 个数和数学直觉不一致先确认语义或用无符号处理把汉明距离当成编辑距离两个概念定义完全不同等长看汉明变长看编辑距离避坑心得所有位运算题目拿到手先用几个小数字手推一遍。比如 0 和 7距离是 313 和 81101 和 1000距离是 215 和 0距离是 4。手推 30 秒顶得上提交试错三次。这个方法我沿用至今。6. 做完461之后相关题目与工程延伸6.1 一串可以顺势刷掉的题目461 是位运算里最友好的一道题做完之后建议立刻刷这四道它们和 461 共享同一套思想位1的个数直接考统计二进制中 1 的个数克尼根算法刷一遍就熟了。只出现一次的数字利用 a ^ a 0 的异或性质把成对出现的数字消掉剩下的就是唯一出现一次的数字。丢失的数字给定 0 到 n 中缺失一个数的数组用异或把所有下标和数值都异或一遍唯一没被抵消的就是缺失值。汉明距离总和这是 461 的进阶版。给一个整数数组计算所有数两两之间的汉明距离之和。如果两两枚举是 O(n^2)数据大基本超时。正确姿势是按位统计对于第 i 位统计这个数组里有多少个数在该位是 0、多少个数是 1pair 贡献就是 zero * one最终把所有位的贡献累加。做完 477 再回头看 461位运算的“按位独立”思维会非常清晰。这组题串着刷最大的好处是你会慢慢发现位运算题不再“背套路”而是真的在“算”。6.2 从这道题延伸到工程里的三个想法第一汉明距离教给我一个重要思维把对象编码成定长比特串然后用距离度量相似度。图片有 pHash文本有 simhash音频有指纹视频有帧哈希。只要指纹设计得稳定汉明距离就是最便宜、可并行的相似度计算方式。第二位运算在工程里不是炫技。权限系统里每个权限一个 bit用户权限用整数存加权限是 OR检查权限是 AND撤销权限是 AND NOT本质就是位运算。状态机里多个布尔状态拼成一个整数一条指令同时判断能省不少分支。461 里那个“先异或再数1”的操作翻译成工程语言就是“找出两个集合的对称差”这在 AB 测试分流、配置 diff、日志比对里都出现过。第三别小看“数 1”这个操作。popcount 在稀疏向量相似度、布隆过滤器优化、量子计算模拟器里都有用武之地。最开始刷 461 时我也觉得这题太简单后来在真实项目里发现越基础的操作越容易被反复复用。我个人比较推荐的做法是刷题归刷题刷完顺手想一想“这个技巧在什么场景下会被用到”。461 是我见过最适合做这种联想的题因为它足够简单概念又足够本源。每次刷题都多想一层就不会变成重复劳动。做图片去重的时候我就是因为先理解了汉明距离的原理才知道阈值怎么调、粗筛怎么做、误判怎么控制——这些实战经验恰恰是从一道看似简单的 Easy 题里长出来的。
