文章目录
- 摘要
- 描述
- 题解答案
- 题解代码分析
- 为什么一定要用异或？
- 怎么数 1 的个数？
- Swift 可运行 Demo 代码
- 代码逐步解析
- 示例测试及结果
- 与实际场景结合
- 时间复杂度
- 空间复杂度
- 总结
摘要
汉明距离这道题，属于那种题目极短、考点极准的类型。
表面看是在让你数二进制里有多少位不一样，但实际上是在考你对位运算的理解是否到位。
如果你在写业务代码时对位运算有点“下意识躲开”，那这道题正好是一个非常好的切入口。
描述
题目给你两个整数x和y，要求你算它们的汉明距离。
什么叫汉明距离？说人话就是：
把两个数都转成二进制，从低位到高位一位一位对比，有多少位不一样，就是多少。
举个最直观的例子：
x = 1 -> 0001 y = 4 -> 0100你会发现有两位不同，所以结果是2。
这类问题在实际开发中其实并不陌生，比如：
- 判断两个配置标志位差异
- 计算数据版本变更程度
- 网络协议中校验位的差异判断
题解答案
这道题最标准、最推荐的解法只有一句话：
先做异或，再数 1 的个数
原因很简单：
异或（XOR）有一个非常好的性质
- 相同位：0
- 不同位：1
所以
x ^ y的二进制中，有多少个1，就是汉明距离
题解代码分析
为什么一定要用异或？
假设有两个位：
| x | y | x ^ y |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
你会发现：
- 异或的结果，刚好标记了所有“不同的位置”
- 不需要你手动逐位比对
这是位运算里最“干净”的用途之一。
怎么数 1 的个数？
有两种常见方式：
- 循环右移，一位一位数
- 使用经典技巧：
n & (n - 1)消掉最低位的 1
这里我推荐第二种，既高效又优雅。
Swift 可运行 Demo 代码
importFoundationclassSolution{funchammingDistance(_x:Int,_y:Int)->Int{varn=x^yvarcount=0// Brian Kernighan 算法whilen>0{n&=(n-1)count+=1}returncount}}代码逐步解析
varn=x^y这一步是整个解法的核心。
n的每一位为 1，代表x和y在该位不同
whilen>0{n&=(n-1)count+=1}这段代码的作用是：
- 每执行一次，都会把
n中最右边的一个 1 变成 0 - 执行多少次，就说明原来有多少个 1
这比“循环 32 次逐位判断”要高效得多，尤其在 1 很少的情况下。
示例测试及结果
letsolution=Solution()print(solution.hammingDistance(1,4))// 2print(solution.hammingDistance(3,1))// 1print(solution.hammingDistance(0,0))// 0print(solution.hammingDistance(7,10))// 3输出结果：
2 1 0 3完全符合预期。
与实际场景结合
汉明距离在工程里其实非常常见，只是你可能没注意到名字而已。
几个典型场景：
特征相似度计算
- 比如权限位、开关位的差异判断
网络通信
- 用来判断数据包头部变化
版本对比
- 判断新旧配置差了多少个标志位
安全领域
- 判断哈希结果的相似程度（基础概念）
这道题的解法，属于那种：
一旦你记住了，以后在代码里会经常用到。
时间复杂度
O(k)其中k是x ^ y中 1 的个数。
最坏情况下（全是 1），也只是 32 次循环。
空间复杂度
O(1)只用了几个整型变量，没有任何额外数据结构。
总结
汉明距离这道题，非常适合作为：
- 位运算入门题
- 面试中“送分但容易写复杂”的题
- 提醒自己：位运算并不难，而且很实用
