LeetCode 第 461 题“汉明距离”是一道经典的位运算问题，旨在计算两个整数在二进制表示下不同位的个数。题目要求简单直接：给定两个整数 x 和 y，计算并返回它们之间的汉明距离。

一、问题解析

汉明距离的定义为两个等长字符串对应位置不同字符的个数。在本题中，我们将其应用于整数的二进制表示。例如，对于 x = 1（二进制 0001）和 y = 4（二进制 0100），它们在第一和第三位不同，因此汉明距离为 2。

二、解决方案

以下是几种常见的解法，从暴力到优化，逐步深入。

方法一：逐位比较法

最直观的方法是逐位比较 x 和 y 的二进制位。我们可以通过循环 32 次（假设为 32 位整数），每次检查最低位是否相同，然后右移一位。

步骤：

1. 初始化计数器 count = 0。
2. 循环 32 次，每次比较 x 和 y 的最低位（通过 x & 1 和 y & 1 获取）。
3. 如果不同，count 加 1。
4. 将 x 和 y 右移一位（x >>= 1, y >>= 1）。
5. 返回 count。

时间复杂度：O(1)，因为固定循环 32 次。
空间复杂度：O(1)。

方法二：异或运算优化

利用位运算中的异或（XOR）操作，可以更高效地解决问题。异或运算的规则是：相同为 0，不同为 1。因此，将 x 和 y 进行异或后，结果中 1 的个数即为汉明距离。

步骤：

1. 计算 z = x ^ y。
2. 统计 z 中 1 的个数。统计方法有多种：

• 循环计数法：类似方法一，循环检查 z 的最低位是否为 1，然后右移。

• Brian Kernighan 算法：这是一种高效算法，通过 z & (z - 1) 不断清除最低位的 1，直到 z 变为 0。每次操作计数器加 1。

时间复杂度：O(1)，因为整数位数固定。
空间复杂度：O(1)。

方法三：内置函数法

许多编程语言提供了内置函数来统计二进制中 1 的个数（例如 Java 的 Integer.bitCount() 或 Python 的 bin().count('1')）。这种方法代码简洁，但底层实现通常基于高效算法。

三、代码示例（Python）

以下是方法二的 Python 实现，使用 Brian Kernighan 算法：

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

四、应用场景

汉明距离在计算机科学中有广泛的应用，例如：

• 错误检测与纠正：在网络传输或存储系统中，用于衡量数据差异。
• 信息检索：在相似性搜索中，比较二进制特征向量。
• 密码学：评估密钥或哈希值的差异。

五、

LeetCode 461 题通过位运算的核心技巧，帮助开发者熟悉异或操作和二进制处理。掌握此类问题不仅能提升算法能力，还能加深对计算机底层原理的理解。建议在解题时优先考虑异或结合 Brian Kernighan 算法，以实现高效且简洁的解决方案。