汉明距离如何用位运算求解？（LeetCode 461）

简化版

两个整数的汉明距离，就是它们二进制表示中不同位的个数。先做 x ^ y，相同位变 0，不同位变 1；再统计异或结果里 1 的数量即可。常用写法是不断执行 n &= n - 1 消掉最低位的 1，循环次数等于 1 的个数。

详细版

int hammingDistance(int x, int y) {
    int n = x ^ y;
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

x ^ y 把“是否不同”编码成位模式：不同为 1，相同为 0。
n & (n - 1) 每次清除 n 的最低位 1。
如果是固定 32 位整数，也可以逐位右移检查，但清低位 1 的循环通常更快，循环次数只与 1 的个数有关。
时间复杂度 O(k)，k 为异或结果中 1 的个数，最坏 O(32)；空间 O(1)。

完整版教学

一、汉明距离的定义先落到位上

汉明距离表示两个等长编码在多少个位置不同。对于整数题，等长编码就是固定宽度二进制，例如 32 位。题目不是问两个数差多少，而是问它们的位模式差多少。

例子：x=1，y=4。

1 = 001
4 = 100
不同位置有第 0 位和第 2 位，所以距离为 2

这也是很多人容易混淆的地方：1 和 4 的数值差是 3，但汉明距离是 2。面试回答要明确这是位级比较。

二、为什么第一步一定想到异或

异或的真值表正好表达“不同”：

a	b	a ^ b	含义
0	0	0	相同
0	1	1	不同
1	0	1	不同
1	1	0	相同

所以 x ^ y 后，结果中每个 1 都代表原来对应位不同。问题立刻从“比较两个数”变成“统计一个数里有多少个 1”，这就是汉明重量问题。

三、如何统计 1：逐位扫和清低位 1

直接逐位扫描可以这样写：

int count = 0;
for (int i = 0; i < 32; i++) {
    count += (n >>> i) & 1;
}

更常见的位运算写法是 n &= (n - 1)。原因是 n-1 会把最低位的 1 变成 0，并把它右边的 0 变成 1；再与原数相与，最低位的 1 就被清掉。

n     = 101100
n - 1 = 101011
n&(n-1)=101000

每循环一次，恰好少一个 1，因此循环次数就是答案。

记忆钩子：汉明距离先异或，把“不同”变成 1；再数 1，把“有几个不同位”数出来。

四、用一个完整数字例子走一遍

设 x=14，y=9：

x = 1110
y = 1001
x^y = 0111

异或结果 0111 有 3 个 1，所以汉明距离是 3。用清低位 1 推演：

0111 -> 0110, count=1
0110 -> 0100, count=2
0100 -> 0000, count=3

最终 n=0 停止，返回 3。这个例子能同时说明异或和 n&(n-1) 两个技巧。

五、和 Number of 1 Bits 的关系

汉明距离可以看成“先异或再做汉明重量”。如果面试官之前问过 Number of 1 Bits，这题通常是它的直接组合。

题目	输入	核心步骤	输出含义
Number of 1 Bits	一个整数 n	统计 n 中 1 的个数	单个数的 1 位数量
Hamming Distance	两个整数 x,y	统计 `x^y` 中 1 的个数	两个数不同位数量
Total Hamming Distance	一个数组	按位统计 0/1 组合数	所有数对不同位总和

这张表的价值是帮助你把题型串起来，而不是每题孤立背代码。

六、语言与固定宽度的注意点

LeetCode 461 给的是非负整数，使用 Java 的 int 时 x ^ y 仍在 32 位补码范围内。因为输入非负且通常范围有限，while (n != 0) 没问题。若题目扩展到可能出现负数，逐位扫描时要使用无符号右移 >>>，否则算术右移会持续补符号位。

对于 Python，整数不是固定 32 位补码，处理负数时必须先限定宽度，例如 n &= 0xffffffff。不过原题不需要扩展到负数，面试里点到这个差异即可。

七、常见误区与追问

误区：把汉明距离理解成两个数的绝对差。 它比较的是二进制位是否相同，不是数值大小差。
误区：直接统计 x 和 y 的 1 个数差。 两个数 1 的数量相同也可能位完全不同，必须先异或。
误区：忘记 n&(n-1) 是清最低位 1。 它不是简单减 1，也不是右移一位。
追问：时间复杂度到底是 O(1) 还是 O(k)？ 在固定 32 位整数下可说 O(1)，更细地说清低位 1 循环执行 k 次，k 是 1 的数量。
追问：如果要求所有数对的汉明距离总和怎么办？ 不要两两异或，应按每一位统计 1 的个数 c，贡献 c*(n-c)。
追问：为什么异或后数 1 就够了？ 异或真值表已经把每一位是否不同编码成 0/1，数 1 就是数不同位。

八、加强记忆

汉明距离的两步主线是：x ^ y 把不同位标成 1，n &= n-1 每次消掉一个 1。看到“两个数有多少位不同”，不要先想减法，也不要分别数 1；先异或，再复用汉明重量。固定 32 位下复杂度可视为 O(1)，空间 O(1)。

简化版

详细版