LeetCode 题解工作台
转换数字的最少位翻转次数
一次 位翻转 定义为将数字 x 二进制中的一个位进行 翻转 操作，即将 0 变成 1 ，或者将 1 变成 0 。 比方说， x = 7 ，二进制表示为 111 ，我们可以选择任意一个位（包含没有显示的前导 0 ）并进行翻转。比方说我们可以翻转最右边一位得到 110 ，或者翻转右边起第二位得到 101…
1
题型
8
代码语言
3
相关题
当前训练重点
简单 · 位运算·操作·driven·solution·strategy
答案摘要
根据题目描述，我们只需要计算 $\textit{start} \oplus \textit{goal}$ 的二进制表示中有多少个 1 即可。 时间复杂度 $O(\log n)$，其中 是题目中整数的大小。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 位运算·操作·driven·solution·strategy 题型思路
题目描述
一次 位翻转 定义为将数字 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 ： - 翻转右边起第一位得到：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 <= 109
注意：本题与 461. 汉明距离 相同。
解题思路
方法一：位运算
根据题目描述，我们只需要计算 的二进制表示中有多少个 1 即可。
时间复杂度 ，其中 是题目中整数的大小。空间复杂度 。
class Solution:
def minBitFlips(self, start: int, goal: int) -> int:
return (start ^ goal).bit_count()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(number of set bits) because we only iterate over differing bits using efficient bit counting. Space complexity is O(1) as no extra storage proportional to input size is needed. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Look for direct bit manipulation solutions using XOR rather than iterative bit flipping.
- question_mark
Check if candidate counts differing bits accurately without redundant operations.
- question_mark
Watch if they handle edge cases where start or goal is zero efficiently.
常见陷阱
外企场景- error
Attempting to simulate each flip step instead of using XOR leads to unnecessary complexity.
- error
Failing to count only differing bits can result in off-by-one errors.
- error
Ignoring integer constraints might cause overflow in some languages.
进阶变体
外企场景- arrow_right_alt
Compute minimum bit flips for arrays of numbers pairwise.
- arrow_right_alt
Determine bit flips required to convert start to goal under a fixed number of bits.
- arrow_right_alt
Count flips to match multiple goals simultaneously using bitwise aggregation.