我来给你讲解 LeetCode 第 461 题「汉明距离」。

题目描述

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

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

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
不同的位置有2处

示例 2：

输入：x = 3, y = 1
输出：1

解题思路详解

第一步：理解汉明距离的本质

汉明距离衡量的是两个等长字符串（在这里是二进制表示）在对应位置上不同字符的个数。

对于两个整数，我们需要：

1. 比较它们在每个二进制位上的值
2. 统计有多少个位是不同的

第二步：关键思路 - 异或运算

异或运算（XOR）有一个重要特性：相同为0，不同为1。

这正是我们需要的！如果对两个数进行异或运算：

• 对应位相同的结果是0
• 对应位不同的结果是1

举例：

x = 1  → 0001
y = 4  → 0100
x ^ y  → 0101  (十进制为5)

异或结果中1的个数就是汉明距离。

第三步：问题转化

现在问题转化为：计算一个整数的二进制表示中1的个数。

这就是著名的"位计数"问题。

第四步：计算1的个数 - 方法1：逐位检查

最直观的方法是检查每一位是否为1：

def hammingDistance(x, y):
    xor = x ^ y  # 得到差异位图
    distance = 0
    
    # 检查32位整数（题目约束）
    for i in range(32):
        # 检查第i位是否为1
        if (xor >> i) & 1:
            distance += 1
    
    return distance

工作原理：

• xor >> i：将xor右移i位，让第i位变成最低位
• & 1：与1进行与运算，只保留最低位
• 如果结果是1，说明该位是1，距离加1

第五步：计算1的个数 - 方法2：Brian Kernighan算法

更高效的方法是使用Brian Kernighan算法：

def hammingDistance(x, y):
    xor = x ^ y
    distance = 0
    
    while xor:
        distance += 1
        xor = xor & (xor - 1)  # 清除最低位的1
    
    return distance

算法原理：

• xor & (xor - 1) 会清除xor的最低位的1
• 每次清除一个1，直到xor变为0
• 清除的次数就是1的个数

举例说明：

xor = 5 (二进制 0101)

第一次循环：
xor = 0101
xor - 1 = 0100
xor & (xor - 1) = 0100, distance = 1

第二次循环：
xor = 0100  
xor - 1 = 0011
xor & (xor - 1) = 0000, distance = 2

结束，汉明距离为2

第六步：复杂度分析

• 时间复杂度： O(1)

  • 整数位数固定（32位），两种方法都是常数时间
  • Brian Kernighan算法在最坏情况下需要32次循环

• 空间复杂度： O(1)

  • 只使用了常数级别的额外空间

第七步：完整代码实现

def hammingDistance(x, y):
    xor = x ^ y
    count = 0
    
    # Brian Kernighan算法
    while xor:
        count += 1
        xor &= xor - 1  # 清除最低位的1
    
    return count

总结

汉明距离问题的解题步骤：

1. 理解需求：统计两个数二进制表示中不同位的个数
2. 关键转化：使用异或运算得到差异位图
3. 问题简化：转化为统计1的个数问题
4. 选择算法：Brian Kernighan算法高效清除最低位的1
5. 实现优化：得到简洁高效的解决方案

这个题目很好地展示了如何通过位运算技巧将复杂问题转化为简单问题。