2220. 转换数字的最少位翻转次数

🟢   🔖  位运算  🔗 力扣 LeetCode

题目

A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0.

• For example, for x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc.

Given two integers start and goal, return _theminimum number of bit flips to convert _start togoal.

Example 1:

Input: start = 10, goal = 7

Output: 3

Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps:

• Flip the first bit from the right: 101 0 -> 101 1.
• Flip the third bit from the right: 1 0 11 -> 1 1 11.
• Flip the fourth bit from the right: 1 111 -> 0 111.

It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.

Example 2:

Input: start = 3, goal = 4

Output: 3

Explanation: The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps:

• Flip the first bit from the right: 01 1 -> 01 0.
• Flip the second bit from the right: 0 1 0 -> 0 0 0.
• Flip the third bit from the right: 0 00 -> 1 00.

It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.

Constraints:

• 0 <= start, goal <= 10^9

Note: This question is the same as 461: Hamming Distance

题目大意

一次 位翻转 定义为将数字 x 二进制中的一个位进行 翻转 操作，即将 0 变成 1 ，或者将 1 变成 0 。

• 比方说，x = 7 ，二进制表示为 111 ，我们可以选择任意一个位（包含没有显示的前导 0 ）并进行翻转。比方说我们可以翻转最右边一位得到 110 ，或者翻转右边起第二位得到 101 ，或者翻转右边起第五位（这一位是前导 0 ）得到 10111 等等。

给你两个整数 start 和 goal ，请你返回将 start 转变成 goal 的 最少位翻转 次数。

示例 1：

输入： start = 10, goal = 7

输出： 3

解释： 10 和 7 的二进制表示分别为 1010 和 0111 。我们可以通过 3 步将 10 转变成 7 ：

• 翻转右边起第一位得到：101** 0** -> 101** 1 。**
• 翻转右边起第三位：1** 0** 11 -> 1** 1** 11 。
• 翻转右边起第四位：** 1** 111 -> 0 111 。

我们无法在 3 步内将 10 转变成 7 。所以我们返回 3 。

示例 2：

输入： start = 3, goal = 4

输出： 3

解释： 3 和 4 的二进制表示分别为 011 和 100 。我们可以通过 3 步将 3 转变成 4 ：

• 翻转右边起第一位：01** 1** -> 01 0 。
• 翻转右边起第二位：0** 1** 0 -> 0** 0** 0 。
• 翻转右边起第三位：** 0** 00 -> 1 00 。

我们无法在 3 步内将 3 变成 4 。所以我们返回 3 。

提示：

• 0 <= start, goal <= 10^9

注意： 本题与 461. 汉明距离 相同。

解题思路

最小的位反转次数其实就是 start 和 goal 的汉明距离。

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

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

2. 比较每一位：如果 start 和 goal 对应位不同，即 (start & 1) !== (goal & 1)，就增加位反转次数。

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

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

5. 返回结果：返回最终的位反转次数。

复杂度分析

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

代码

/**
 * @param {number} start
 * @param {number} goal
 * @return {number}
 */
var minBitFlips = function (start, goal) {
	let count = 0;
	while (start > 0 || goal > 0) {
		// 直到 start 和 goal 都为 0
		if ((start & 1) !== (goal & 1)) {
			// 检查最低位是否相同
			count += 1; // 如果不同，距离加 1
		}
		start >>>= 1; // 右移 start，检查下一个二进制位
		goal >>>= 1; // 右移 goal，检查下一个二进制位
	}
	return count; // 返回最终的位翻转次数
};

相关题目

题号	标题	题解	标签	难度	力扣
1318	或运算的最小翻转次数	[✓]	位运算	🟠	🀄️ 🔗
2997	使数组异或和等于 K 的最少操作次数		位运算 数组	🟠	🀄️ 🔗