Easy

题目描述

数字 x 的一次位翻转操作是指选择 x 二进制表示中的任意一位，将其从 0 变为 1 或从 1 变为 0。

例如，对于 x = 7，其二进制表示是 111，我们可以选择任意一位（包括未显示的前导零）并翻转它。我们可以翻转右边第一位得到 110，翻转右边第二位得到 101，翻转右边第五位（前导零）得到 10111 等。

给定两个整数 start 和 goal，返回将 start 转换为 goal 所需的最少位翻转次数。

示例 1:

输入: start = 10, goal = 7
输出: 3
解释: 10 和 7 的二进制表示分别为 1010 和 0111。我们可以通过 3 步将 10 转换为 7：
- 翻转右边第一位: 1010 -> 1011
- 翻转右边第三位: 1011 -> 1111
- 翻转右边第四位: 1111 -> 0111
可以证明我们无法在少于 3 步的情况下将 10 转换为 7。因此，我们返回 3。

示例 2:

输入: start = 3, goal = 4
输出: 3
解释: 3 和 4 的二进制表示分别为 011 和 100。我们可以通过 3 步将 3 转换为 4：
- 翻转右边第一位: 011 -> 010
- 翻转右边第二位: 010 -> 000
- 翻转右边第三位: 000 -> 100
可以证明我们无法在少于 3 步的情况下将 3 转换为 4。因此，我们返回 3。

约束条件:

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

注意: 这道题与第 461 题：汉明距离相同。

提示:

  • 如果 start 和 goal 中某一位的值不同，则需要翻转该位。
  • 考虑使用 XOR 操作来确定哪些位需要翻转。

解题思路

这道题的核心思路是找出两个数字在二进制表示中有多少位不同，每个不同的位都需要进行一次翻转操作。

分析过程

我们可以通过异或（XOR）操作来解决这个问题。异或操作有一个重要性质：相同的位得到0，不同的位得到1。因此，start ^ goal 的结果中，1的个数就是需要翻转的位数。

例如：

  • start = 10 (1010), goal = 7 (0111)
  • 1010 XOR 0111 = 1101
  • 1101中有3个1，所以需要3次翻转

解法思路

方法一：使用内置函数 大多数编程语言都提供了计算二进制中1的个数的内置函数，这是最简洁的解法。

方法二：位运算技巧 使用 n & (n-1) 的技巧可以消除最低位的1，重复此操作直到数字变为0，操作次数就是1的个数。

方法三：逐位检查 通过不断右移和检查最低位来统计1的个数。

推荐使用方法一，因为它最简洁且效率很高。

代码实现

class Solution {
public:
    int minBitFlips(int start, int goal) {
        return __builtin_popcount(start ^ goal);
    }
};

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        return (start ^ goal).bit_count()

public class Solution {
    public int MinBitFlips(int start, int goal) {
        return System.Numerics.BitOperations.PopCount((uint)(start ^ goal));
    }
}

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

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)使用内置函数计算位数，对于32位整数是常数时间
空间复杂度O(1)只使用常数额外空间

相关题目