（LeetCodeHot100）461. 汉明距离——hamming-distance

zhangzhang2025-11-132025-11-13

461. 汉明距离——hamming-distance

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

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

示例 1：

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

示例 2：

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

提示：

0 <= x, y <= 231 - 1

这种题没见过，直接学

前言

汉明距离广泛应用于多个领域。在编码理论中用于错误检测，在信息论中量化字符串之间的差异。

两个整数之间的汉明距离是对应位置上数字不同的位数。

根据以上定义，我们使用异或运算，记为 ⊕，当且仅当输入位不同时输出为 1。

fig1

计算 x 和 y 之间的汉明距离，可以先计算 x⊕y，然后统计结果中等于 1 的位数。

现在，原始问题转换为位计数问题。位计数有多种思路，将在下面的方法中介绍。

方法一：内置位计数功能

思路及算法

大多数编程语言都内置了计算二进制表达中 1 的数量的函数。在工程中，我们应该直接使用内置函数。

代码

class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

1. 异或运算（^）的作用

^ 是按位异或运算符，其运算规则是：
两个二进制位相同则结果为 0，不同则结果为 1。

2.Integer.bitCount：

统计这个新整数的二进制中 1 的个数，这个个数就是 x 和 y 的汉明距离。

复杂度分析

时间复杂度：O(1)。不同语言的实现方法不一，我们可以近似认为其时间复杂度为 O(1)。
空间复杂度：O(1)。

方法二：移位实现位计数

思路及算法

在锻炼算法能力时，重复造轮子是不可避免的，也是应当的。因此读者们也需要尝试使用各种方法自己实现几个具有位计数功能的函数。本方法将使用位运算中移位的操作实现位计数功能。

fig2

代码核心逻辑：先通过异或找不同位，再用移位 + 按位与统计不同位的数量（即 1 的个数）。

步骤拆解（3 步搞定）

异或找不同位：计算 s = x ^ y

异或规则是 “相同为 0，不同为 1”，所以 s 的二进制中，1 的位置就是 x 和 y 二进制不同的位置（这是汉明距离的核心）。
移位 + 按位与统计 1 的个数：
- 初始化计数器 ret=0，循环直到 s=0（所有位都检查完）。
- 每次循环：
  - s & 1：提取 s 的最低位（1 则为 1，0 则为 0），加到计数器（统计当前位是否是不同位）。
  - s >>= 1：将 s 右移 1 位（舍去已检查的最低位，让次低位变成新的最低位）。
返回计数器结果：计数器的值就是不同位的数量（汉明距离）。

示例演示（x=1，y=4）

x=1（001），y=4（100）→ s=001 ^ 100 = 101（十进制 5），ret=0。
第 1 次循环：s&1=101&001=1 → ret=1；s>>1=10（十进制 2）。
第 2 次循环：s&1=10&01=0 → ret 不变；s>>1=1（十进制 1）。
第 3 次循环：s&1=1&1=1 → ret=2；s>>1=0（循环结束）。
返回 2（正确，汉明距离为 2）。

class Solution {
    public int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            ret += s & 1;
            s >>= 1;
        }
        return ret;
    }
}