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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

一次 位翻转 定义为将数字 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 <= 109

方法一：位运算

思路与算法

为了使得位翻转操作的次数最少，我们应当只对 start 与 goal 数值不同的二进制位执行翻转操作，而对应的最少次数即为这两个数字不同的二进制位数量。

为了求出 start 与 goal 不同的二进制位数量，我们可以计算两个数按位异或后的数值 tmp} = \textit{start} \oplus \textit{goal。根据异或运算的定义，tmp 某一二进制位为 1 当且仅当 start 与 goal 在该位数值不同。因此，tmp 的二进制表示中 1 的数量即为 start 与 goal 不同的二进制位数量。我们计算并返回该值即可。

关于如何计算一个整数二进制表示中 1 的数量，读者可以参考「191. 位1的个数」的题解 ，本文中我们将使用循环检查二进制位的方法计算。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minBitFlips(int start, int goal) {
        int res = 0;
        int tmp = start ^ goal;
        while (tmp) {
            res += tmp & 1;
            tmp >>= 1;
        }
        return res;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        res = 0
        tmp = start ^ goal
        while tmp:
            res += tmp & 1
            tmp >>= 1
        return res

复杂度分析

  • 时间复杂度：O(\log M)，其中 M = \max(\textit{start}, \textit{goal}) 为两数的较大值，即为计算异或数值中 1 的位数的时间复杂度。

  • 空间复杂度：O(1)。

 Comments
On this page
2220-转换数字的最少位翻转次数