算法 - 汉明距离

Posted on

1. 题目

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

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

示例:

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

2. 解题思路

2.1 异或 + 统计 1 的个数

对应位不同 ⟺ 异或后该位为 1。所以：

  1. n = x ^ y
  2. 统计 n 的二进制中 1 的个数（population count）。

统计 1 的个数有两种经典写法：

  • 逐位 n & 1 后右移。

  • n & (n - 1) 每次抹掉最低位的 1，循环次数 = 1 的个数，更优。

  • 时间复杂度：O(1)（最多 32 位），空间复杂度：O(1)。

注意：JS 的位运算按 32 位有符号整数处理，本题 LeetCode 数据范围 0 ≤ x, y ≤ 2³¹-1，用 ^、& 安全；若涉及无符号右移请用 >>>。

3. TypeScript 实现

3.1 Brian Kernighan 算法（推荐）

1
2
3
4
5
6
7
8
9
10
11
function hammingDistance(x: number, y: number): number {
    let n = x ^ y;
    let count = 0;
    while (n) {
        n = n & (n - 1); // 抹掉最低位的 1
        count++;
    }
    return count;
}

console.log(hammingDistance(1, 4)); // 2

3.2 内置位计数（一行流）

1
2
3
const hammingDistanceBitCount = (x: number, y: number): number =>
    (x ^ y).toString(2).split("0").join("").length;
// 或 (x ^ y).toString(2).match(/1/g)?.length ?? 0

4. 面试延伸

4.1 总汉明距离（LeetCode 477）

给数组 nums，求所有数对汉明距离之和。逐位暴力 O(n²·32) 会超时，按位统计更优：

对第 i 位，统计数组中该位为 1 的个数 ones，为 0 的个数 zeros = n - ones，则该位对总距离的贡献为 ones * zeros（每一位独立）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function totalHammingDistance(nums: number[]): number {
    let total = 0;
    const n = nums.length;

    for (let i = 0; i < 32; i++) {
        let ones = 0;
        for (const x of nums) {
            ones += (x >>> i) & 1;
        }
        total += ones * (n - ones); // 该位 1 与 0 的两两配对数
    }

    return total;
}
  • 时间复杂度：O(32·n)，空间复杂度：O(1)。

4.2 知识点

  • n & (n-1) 技巧：可用于判断 2 的幂、统计位 1 个数、求两数异或差异。
  • 汉明距离是「信息/编码」基础概念，延伸可谈海明码纠错。

难度：简单 | LeetCode 461 / 477 | 位运算