LeetCode 461. 汉明距离

Skyme2026/8/26大约 4 分钟

LeetCode 461. 汉明距离

题目核心

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

例如：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

解题思考过程

第一步：理解问题

汉明距离 = 二进制逐位比对，有多少位不一样。

第二步：暴力做法（32 位逐位取）

对每一位 i，分别取出 x 的第 i 位和 y 的第 i 位，不同就计数加 1。

时间：O(1)（32 次操作，常数）
空间：O(1)

这就是贴的代码思路，也是最直观的写法。

第三步：优化写法 — 利用异或的性质

回忆异或的性质：相同为 0，不同为 1。

x ^ y 的二进制表示中，1 所在的位置 = 对应位不同的位置。

所以只需要先算 z = x ^ y，然后统计 z 里有多少个 1 即可。

这和暴力 32 位复杂度一样常数级，但代码更紧凑。

第四步：再进一步 — Brian Kernighan 算法

如果两个数只有几位不同，用 z & (z - 1) 可以一次消掉 z 的最低位 1。这样循环的次数就不再是固定 32 次，而是有几个 1 就循环几次。在极端情况下（比如两数几乎相同、只有 1 个 1）更快。

时间：O(1)，但次数更少
空间：O(1)

解法一：逐位取与比对（当前版本）

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function (x, y) {
  let ans = 0;
  for (let i = 0; i < 32; i++) {
    let a = (x >> i) & 1;
    let b = (y >> i) & 1;
    ans += a ^ b;
  }
  return ans;
};

代码逐行解释

let ans = 0;

ans 记录"不同位的数量"，也就是汉明距离。

for (let i = 0; i < 32; i++) {

整数在 JS 中是 32 位有符号整数（位运算按 32 位处理），所以逐位扫描 0～31，共 32 次。

let a = (x >> i) & 1;
let b = (y >> i) & 1;

取 x 和 y 的第 i 位（从最低位 0 开始）：

x >> i：把第 i 位右移到最低位。
& 1：和二进制最低位的 1 做按位与，只保留最低位的值（0 或 1），其他位全部清零。

这样 a 就等于 x 第 i 位的 bit，b 等于 y 第 i 位的 bit。

ans += a ^ b;

对这两个 bit 做异或：

a == b → 结果是 0 → 不加。
a != b → 结果是 1 → ans 加 1。

执行过程示例

x = 1, y = 4：

x = 1 = 0b 0000_0000_0000_0000_0000_0000_0000_0001
y = 4 = 0b 0000_0000_0000_0000_0000_0000_0000_0100

i=0: a=1, b=0, 1^0=1 → ans=1
i=1: a=0, b=0 → 0, ans=1
i=2: a=0, b=1 → 1, ans=2
i=3~31: a=0,b=0 → 全 0
最终 ans=2 ✓

解法二：先异或再数 1 的个数

核心：先 x ^ y 拿到不同位对应的 1，再数 1 个数。

var hammingDistance = function (x, y) {
  let z = x ^ y;
  let ans = 0;
  for (let i = 0; i < 32; i++) {
    ans += (z >> i) & 1;
  }
  return ans;
};

一行版（toString(2) 转二进制串，配合正则/过滤数 1）：

var hammingDistance = function (x, y) {
  return (x ^ y).toString(2).split('0').join('').length;
};

面试时更推荐"先异或 + 32 次数 1"的写法，清晰稳定。toString 写法虽然短，但属于 JS 内置库，算法题中一般不作为首要答案。

解法三：Brian Kernighan 优化

利用 z & (z - 1) 每次消掉 z 的最低位 1。循环次数等于 1 的个数：

var hammingDistance = function (x, y) {
  let z = x ^ y;
  let ans = 0;
  while (z !== 0) {
    z &= z - 1;   // 消掉最低位的 1
    ans++;
  }
  return ans;
};

原理图解

假设 z = 6 = 110
z - 1 = 5 = 101

z & (z-1) = 110 & 101 = 100   ← 原来末尾那个 1 被消掉了

再重复一次：
z=4=100, z-1=3=011
z & (z-1) = 100 & 011 = 000   ← 又消掉一个 1

总共循环 2 次，等于 z 中 1 的个数。

易错点

循环 32 次不要少：有的位虽然表面高位是 0，但负数是补码表示，也要算进去。固定 32 位最稳。
>> 和 >>> 的区别：正数一样，负数用 >> 会补符号位 1（算术右移），但这里因为 & 1 只取最低位，所以不受影响。如果要右移最高位并当成无符号数，用 >>>。
不要把异或搞成同或：不同为 1 的判断是异或 ^，如果误写成 & 或 | 结果就错。
Brian Kernighan 算法在 z=0 时不进循环：返回 0 刚好正确（两数完全相同汉明距离就是 0）。

复杂度对比

写法	操作次数	特点
逐位双取	固定 32 次	直观，容易想到
异或 + 逐位取	固定 32 次	循环里只数一个数，代码更简洁
Brian Kernighan	几个 1 就几次	稀疏 1 时最快

三者都是 O(1) 常数时间，实际面试中写任意一种都可以，推荐异或 + 32 位统计或Brian Kernighan，前者最好写，后者稍微有点"技巧分"。