2220. 转换数字的最少位翻转次数
2220. 转换数字的最少位翻转次数
题目
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 is111
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 get110
, flip the second bit from the right to get101
, flip the fifth bit from the right (a leading zero) to get10111
, 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
的汉明距离。
位操作:对于每一位,通过位运算来获取
start
和goal
的对应二进制位:(start & 1)
获取start
最低位的值(0 或 1)。(goal & 1)
获取goal
最低位的值(0 或 1)。
比较每一位:如果
start
和goal
对应位不同,即(start & 1) !== (goal & 1)
,就增加位反转次数。右移:为了继续检查下一个二进制位,需要将
start
和goal
各自右移一位,即使用无符号右移运算符>>>
,这将丢弃最低位,检查接下来的二进制位。重复操作:重复执行上述操作,直到
start
和goal
都为 0。此时,已经检查完了所有的二进制位。返回结果:返回最终的位反转次数。
复杂度分析
- 时间复杂度:
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 的最少操作次数 | 位运算 数组 | 🟠 | 🀄️ 🔗 |