LeetCode 461. 汉明距离
题目描述
题意分析
汉明距离统计两个整数在多少个二进制位置上不同：一边是
0、另一边是1，该位置才贡献一次。比较的是相同位的位置，而不是两个数各自含有多少个1。题目给定非负整数，不必转换成字符串或补齐前导零。异或运算可以直接把所有不同的位置标记出来，再统计这些标记即可。
解法：异或计数
核心思路
[!blue]
异或在两位相同时得到
0，不同时得到1，因此v = x ^ y中每个1恰好对应一个需要计数的位置。问题就变成统计v中1的个数。对非零的
v，最低的1右边全是0。执行v-1时，借位会把这个1变成0，右边的零变成一，而更高位保持不变。再与原来的v按位与，右边位置仍为零，最低的这个1被清除，更高位则完全保留。所以每次
v &= v-1都恰好去掉一个尚未计数的不同位。同步增加计数后，“已计数的位数 + v 中剩余的 1 的数量”始终等于答案。最终v == 0，所有不同位都已计入，循环次数就是汉明距离。
解题步骤
- 计算
v = x ^ y，令count = 0。- 当
v != 0时，清除它最低的一个1，并令count++。- 返回
count。若两数相同，异或结果一开始就是零，循环不执行，答案为零。
代码实现
class Solution {
// 用位运算统计 1 的数量即可。
public int hammingDistance(int x, int y) {
// 异或的一对应两数不同的位
int v = x ^ y;
int count = 0;
while (v != 0) {
// 每次只清除最低的一，循环次数就是不同位数量
v &= v - 1;
count++;
}
return count;
}
}
func hammingDistance(x int, y int) int {
// 用位运算统计 1 的数量即可。
// 异或的一对应两数不同的位
v := x ^ y
count := 0
for v != 0 {
// 每次只清除最低的一，循环次数就是不同位数量
v &= v - 1
count++
}
return count
}
复杂度分析
- 时间复杂度：$O(k+1)$，其中 $k$ 为异或结果中
1的数量，循环恰好执行 $k$ 次。题目只使用非负 32 位整数，最多检查 $31$ 个置位，因此固定整数位宽下为 $O(1)$。- 空间复杂度：$O(1)$，只保存异或值与计数。
关键点总结
[!green]
- 异或保留“哪些位置不同”的信息，单独统计两边的
1无法得到这些位置关系。- 清除最低置位会直接跳过中间的零，工作量只与不同位的数量有关。
- 循环条件是仍有置位，而不是必须扫描到某个固定数值下界。
易错点总结
[!yellow]
- 分别统计一的数量再相减，会把不同位置的位互相抵消。
- 用
v&(v+1)，部分输入会停在非零值不再变化。- 使用强制执行一次的循环，会在两数相等时多计一次。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 191. 位1的个数 | 简单 | 两数异或后统计1的个数，直接复用位计数。 |
| 477. 汉明距离总和 | 中等 | 把一对数的距离扩展为所有数对总和，可按每位0和1的数量乘积统计。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！