LeetCode 第 461 题：汉明距离（Hamming Distance）

题目描述

汉明距离指的是两个整数在二进制表示下，对应位不同的数量。给你两个整数 x 和 y，要求计算它们之间的汉明距离。

示例：

输入: x = 1, y = 4
输出: 2
解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
不同位有2个

解题思路

步骤 1：理解核心问题

汉明距离的关键是逐位比较两个数的二进制位是否相同。我们需要一种方法快速找出所有不同的位。

步骤 2：关键技巧——异或运算

异或运算（XOR）有一个重要特性：

• 如果两个位相同，结果为 0
• 如果两个位不同，结果为 1

因此：

• 先计算 x XOR y，得到一个整数 diff
• diff 的二进制表示中，1 的个数就是汉明距离

示例：

x = 1  → 二进制 0001
y = 4  → 二进制 0100
x XOR y = 0101 → 有2个1

步骤 3：计算二进制中 1 的个数

接下来需要高效计算 diff 中 1 的个数。常用方法：

方法 1：逐位检查

• 遍历 diff 的每一位（例如 32 位整数）
• 检查当前位是否为 1：(diff >> i) & 1
• 统计所有为 1 的位

代码模拟：

def hammingDistance(x, y):
    diff = x ^ y
    count = 0
    for i in range(32):  # 假设32位整数
        if (diff >> i) & 1:  # 检查第i位是否为1
            count += 1
    return count

方法 2：布赖恩·克尼根算法（Brian Kernighan's Algorithm）

更高效的方法：利用 n & (n-1) 可以消除最低位的 1。

原理：

• n & (n-1) 会将 n 的最低位的 1 变为 0
• 每次操作消除一个 1，直到 n 变为 0
• 操作次数就是 1 的个数

示例（diff = 5 = 0101）：

初始: diff = 5 (0101), count = 0
第一步: diff = 5 & 4 = 0101 & 0100 = 0100 = 4, count = 1
第二步: diff = 4 & 3 = 0100 & 0011 = 0000 = 0, count = 2
结束

代码实现：

def hammingDistance(x, y):
    diff = x ^ y
    count = 0
    while diff:
        diff &= diff - 1  # 消除最低位的1
        count += 1
    return count

复杂度分析

• 时间复杂度： O(k)，其中 k 是 diff 中 1 的个数（布赖恩·克尼根算法最坏情况 O(32)）
• 空间复杂度： O(1)，只用了常数空间

总结

汉明距离的计算巧妙运用了异或运算和位操作：

1. 异或找差异：x ^ y 直接标出所有不同的位
2. 统计 1 的个数：用 n & (n-1) 高效计数

这种方法既简洁又高效，是位运算的经典应用场景。