461. 汉明距离

🟢   🔖  位运算  🔗 力扣 LeetCode

题目

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, return theHamming distance between them.

Example 1:

Input: x = 1, y = 4

Output: 2

Explanation:

1 (0 0 0 1)
4 (0 1 0 0)
     ↑   ↑

The above arrows point to positions where the corresponding bits are different.

Example 2:

Input: x = 3, y = 1

Output: 1

Constraints:

• 0 <= x, y <= 231 - 1

Note: This question is the same as 2220: Minimum Bit Flips to Convert Number.

题目大意

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

给你两个整数 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 <= 231 - 1

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

解题思路

1. 位操作：对于每一位，通过位运算来获取 x 和 y 的对应二进制位：

   • (x & 1) 获取 x 最低位的值（0 或 1）。
   • (y & 1) 获取 y 最低位的值（0 或 1）。

2. 比较每一位：如果 x 和 y 对应位不同，即 (x & 1) !== (y & 1)，就增加汉明距离。

3. 右移：为了继续检查下一个二进制位，需要将 x 和 y 各自右移一位，即使用无符号右移运算符 >>>，这将丢弃最低位，检查接下来的二进制位。

4. 重复操作：重复执行上述操作，直到 x 和 y 都为 0。此时，已经检查完了所有的二进制位。

5. 返回结果：返回计算出的汉明距离。

复杂度分析

• 时间复杂度：O(1)，对于一个整数来说，位数最多为 32 位，因此最坏情况下需要执行 32 次操作。
• 空间复杂度：O(1)，只使用了常数空间。

代码

var hammingDistance = function (x, y) {
	let distance = 0;
	while (x > 0 || y > 0) {
		// 直到 x 和 y 都为 0
		if ((x & 1) !== (y & 1)) {
			// 检查最低位是否相同
			distance += 1; // 如果不同，距离加 1
		}
		x >>>= 1; // 右移 x，检查下一个二进制位
		y >>>= 1; // 右移 y，检查下一个二进制位
	}
	return distance; // 返回最终的汉明距离
};

相关题目

题号	标题	题解	标签	难度	力扣
191	位1的个数	[✓]	位运算 分治	🟢	🀄️ 🔗
477	汉明距离总和		位运算 数组 数学	🟠	🀄️ 🔗