或运算结果等于 c 的最少翻转次数 图解题解
这道题到底在问什么
- 输入
- a=2, b=6, c=5
- 输出
- 3
- 输入
- a=4, b=2, c=7
- 输出
- 1（只差一位补成 1）
- 输入
- a=1, b=2, c=3
- 输出
- 0（已经满足）
最优解：一步一步想明白
- 3记住两句:c 这位是 1 就「至少要有一个 1」;c 这位是 0 就「a、b 这位的 1 全要清掉」。下面逐列套用。
- 4把 a、b、它们的 OR、以及目标 c 都摊成 9 位二进制对齐排好(高位在左)。接下来从最左一列开始,逐列裁决这一位要不要翻、翻几次。
- 5第 1 列(从左数):a 这位 x = 1,b 这位 y = 0,当前 OR = 1,目标 c 这位 z = 1。
- 6z=1 且 x、y 里已有 1 → OR 已经是 1,达标,本列代价 0。
c 这位要 1,而 a、b 这位至少已有一个 1,OR 天然是 1,无需翻转。本列代价 0。 - 7第 2 列(从左数):a 这位 x = 0,b 这位 y = 1,当前 OR = 1,目标 c 这位 z = 1。
- 8z=1 且 x、y 里已有 1 → OR 已经是 1,达标,本列代价 0。
c 这位要 1,而 a、b 这位至少已有一个 1,OR 天然是 1,无需翻转。本列代价 0。 - 9第 3 列(从左数):a 这位 x = 1,b 这位 y = 0,当前 OR = 1,目标 c 这位 z = 0。
- 10z=0 但有 1 个 1 → 这 1 个 1 要清成 0,本列代价 1。
c 这位要 0,所以 a、b 这位上凡是 1 的都得翻成 0。这里有 1 个 1(标红),本列代价 1。 - 11第 4 列(从左数):a 这位 x = 1,b 这位 y = 0,当前 OR = 1,目标 c 这位 z = 0。
- 12z=0 但有 1 个 1 → 这 1 个 1 要清成 0,本列代价 1。
c 这位要 0,所以 a、b 这位上凡是 1 的都得翻成 0。这里有 1 个 1(标红),本列代价 1。 - 13第 5 列(从左数):a 这位 x = 0,b 这位 y = 1,当前 OR = 1,目标 c 这位 z = 1。
- 14z=1 且 x、y 里已有 1 → OR 已经是 1,达标,本列代价 0。
c 这位要 1,而 a、b 这位至少已有一个 1,OR 天然是 1,无需翻转。本列代价 0。 - 15第 6 列(从左数):a 这位 x = 0,b 这位 y = 1,当前 OR = 1,目标 c 这位 z = 0。
- 16z=0 但有 1 个 1 → 这 1 个 1 要清成 0,本列代价 1。
c 这位要 0,所以 a、b 这位上凡是 1 的都得翻成 0。这里有 1 个 1(标红),本列代价 1。 - 17第 7 列(从左数):a 这位 x = 1,b 这位 y = 0,当前 OR = 1,目标 c 这位 z = 1。
- 18z=1 且 x、y 里已有 1 → OR 已经是 1,达标,本列代价 0。
c 这位要 1,而 a、b 这位至少已有一个 1,OR 天然是 1,无需翻转。本列代价 0。 - 19第 8 列(从左数):a 这位 x = 1,b 这位 y = 1,当前 OR = 1,目标 c 这位 z = 1。
- 20z=1 且 x、y 里已有 1 → OR 已经是 1,达标,本列代价 0。
c 这位要 1,而 a、b 这位至少已有一个 1,OR 天然是 1,无需翻转。本列代价 0。 - 21第 9 列(从左数):a 这位 x = 0,b 这位 y = 0,当前 OR = 0,目标 c 这位 z = 0。
- 22z=0 且 x=0、y=0 → OR 已是 0,达标,本列代价 0。
c 这位要 0,而 a、b 这位本就都是 0,OR 是 0,无需翻转。本列代价 0。 - 23九列逐位裁决完毕,把每列代价加起来:本例最少翻转 3 次。各位互不干扰,加法即得全局最优。
⚠️ 容易写错的地方
✗ 错：z 为 0 时只翻一个 1
✓ 对：z 为 0 要把 a、b 这位的每个 1 都清掉,代价是 x + y
OR 要为 0,必须两边都为 0,两个 1 就得翻两次
✗ 错：z 为 1 时把两个 0 各翻一次
✓ 对：z 为 1 且都为 0 时只需翻一个,代价 1
OR 只要有一个 1 就达标,翻一个足矣
✗ 错：位宽取太小漏掉高位
✓ 对：循环到第 30 位(覆盖 10^9 的全部位)
少扫高位会漏算那些位的代价
完整代码（Python / C++ / Java）
Python
class Solution:
def minFlips(self, a: int, b: int, c: int) -> int:
ans = 0
for i in range(31):
x = (a >> i) & 1
y = (b >> i) & 1
z = (c >> i) & 1
if z == 1:
if x == 0 and y == 0:
ans += 1
else:
ans += x + y
return ansC++
class Solution {
public:
int minFlips(int a, int b, int c) {
int ans = 0;
for (int i = 0; i < 31; ++i) {
int x = (a >> i) & 1, y = (b >> i) & 1, z = (c >> i) & 1;
if (z) ans += (x == 0 && y == 0);
else ans += x + y;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int minFlips(int a, int b, int c) {
int ans = 0;
for (int i = 0; i < 31; i++) {
int x = (a >> i) & 1, y = (b >> i) & 1, z = (c >> i) & 1;
if (z == 1) ans += (x == 0 && y == 0) ? 1 : 0;
else ans += x + y;
}
return ans;
}
}复杂度
时间
O(1)
固定扫 31 个二进制位,与数值大小无关
空间
O(1)
只用几个整型变量累加
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 或运算结果等于 c 的最少翻转次数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么各位之间可以独立计算、直接相加?+
OR 是按位运算,第 i 位的 OR 只取决于 a、b 的第 i 位,和其他位无关;翻转某一位也只影响那一位。所以每位的最小代价彼此独立,总最小代价就是各位代价之和,不会互相牵制。
如果不用循环逐位,能否用一行位运算搞定?+
可以。补 1 部分:c 要 1 但 OR 为 0 的位,数量是 popcount(c & ~(a | b))。清 1 部分:c 要 0(即 c 这位是 0)却出现 1 的位,要分别数 a、b 里被 c 置 0 的 1,即 popcount((~c) & a) + popcount((~c) & b)。三部分相加就是答案。注意 ~c 在补码里高位全是 1,实现时把范围限定在 31 位(只看第 0 到 30 位)再做与运算,避免高位的 1 混进来。逐位循环更直观,位运算版更短。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 或运算结果等于 c 的最少翻转次数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。