Easy

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

  • 0 <= x, y <= 2^31 - 1

**注意：**此题与 2220. 转换数字的最少位翻转次数 相同。

解题思路

解题思路

汉明距离问题本质上就是统计两个数二进制表示中不同位的个数。我们可以从以下几个角度来解决：

方法一：异或 + 位计数（推荐）

  1. 使用异或运算 x ^ y 得到一个新数，该数的二进制表示中，1 的位置就是 x 和 y 对应位不同的位置
  2. 统计异或结果中 1 的个数，即为汉明距离

方法二：逐位比较

遍历每一位，比较 x 和 y 在该位上是否相同，如果不同则计数器加一。

方法三：使用内置函数

某些语言提供了直接计算二进制中 1 的个数的函数，如 Python 的 bin().count('1')。

其中方法一是最优解，利用了异或运算的性质，既简洁又高效。异或运算 a ^ b 当且仅当 a 和 b 不同时结果为 1，这正好符合汉明距离的定义。

代码实现

class Solution {
public:
    int hammingDistance(int x, int y) {
        int xor_result = x ^ y;
        int count = 0;
        while (xor_result) {
            count += xor_result & 1;
            xor_result >>= 1;
        }
        return count;
    }
};

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x ^ y).count('1')

public class Solution {
    public int HammingDistance(int x, int y) {
        int xorResult = x ^ y;
        int count = 0;
        while (xorResult != 0) {
            count += xorResult & 1;
            xorResult >>= 1;
        }
        return count;
    }
}

var hammingDistance = function(x, y) {
    let xorResult = x ^ y;
    let count = 0;
    while (xorResult !== 0) {
        count += xorResult & 1;
        xorResult >>= 1;
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)n 为 max(x, y)，需要遍历所有二进制位
空间复杂度O(1)只使用了常数级别的额外空间

相关题目