LeetCode 1318. 或运算的最小翻转次数
目录
题目描述
题意分析
题目给出三个正整数
a、b、c。一次操作可以挑a或b的任意一个二进制位，把它从 0 改成 1、或者从 1 改成 0；c是固定的目标，不允许改动。要求返回让a OR b == c成立所需的最少操作次数。约束里有两个信号值得留意。第一，只能改
a和b，c只读，所以「目标」是完全确定的，我们要做的是把a、b调整到某个满足a' | b' == c的状态，代价是被改动的位数。第二，一次操作只动一个位，代价按位计数，这意味着总代价天然就是各个位上代价的累加，而不是某种整体度量。最关键的观察是：各个二进制位互不影响。按位或的定义本身就是逐位独立计算的 ——
a | b的第i位只由a的第i位和b的第i位决定，和其它位没有半点关系；而一次翻转也只影响一个位，不会像加法那样产生进位去污染邻位。于是「让整个a | b等于c」就等价于「对每一个i，让第i位上的或值等于c的第i位」，而这些子目标之间没有任何冲突或竞争：为某一位付出的翻转对别的位毫无副作用，某一位的选择也不会限制别的位。因此总的最少代价就等于每一位单独最少代价之和。这一步把一个看上去要在「到底翻哪些位」的指数级组合里搜索的问题，降成了对每一位做常数次判断的统计问题。
边界情形有几处要照顾到。其一，
a | b本来就等于c时答案是 0，这不需要特判，逐位统计自然会得出 0。其二，c的二进制位数可能比a、b都长（例如a = 1, b = 1, c = 8），也可能比它们都短（例如a = 8, b = 8, c = 1），所以扫描的位范围必须覆盖三个数中最长的那个，任何单独一个数提前变成 0 都不代表可以收工。其三，c某一位是 1 而a、b该位都是 0 时，只需要翻一个就够了，不是两个。
解法：逐位独立计数
核心思路
既然各位独立，就把注意力收缩到单独一个二进制位上，把这一位的所有可能情形穷尽列出来。设该位上
a的取值是x、b的取值是y、c的取值是z，三者都只能取 0 或 1，那么按z分成两大类、一共四种情形。情形一，
z = 1且x、y里至少有一个 1。此时x | y已经是 1，正好等于z，代价为 0。它显然是最小的，因为代价不可能为负。特别注意这里不需要把多出来的那个 1 翻掉 —— 或运算只要求「至少一个 1」，x和y同时为 1 时x | y仍然是 1。情形二，
z = 1且x、y都是 0。此时x | y是 0，不等于 1，必须动手。把x或y中任意一个翻成 1，或值立刻变成 1，代价为 1。它最小的理由是：一次都不翻时或值是 0、不满足要求，所以代价至少是 1，而 1 次已经足以达成，下界被取到。情形三，
z = 0且x、y中恰好有一个 1。要让x | y等于 0，就必须让x和y同时为 0（这是或值为 0 的唯一可能），所以那个 1 必须被翻成 0，代价为 1。情形四，
z = 0且x、y都是 1。理由同上，两个 1 都必须被翻成 0，少翻一个都不行，代价为 2。把情形三和情形四合起来看会更整齐：
z = 0时代价恰好等于x + y，也就是a、b在该位上 1 的个数。原因是「或值为 0」把x、y的终态唯一地钉死成(0, 0)，没有任何选择空间，代价就是从当前状态变到这个唯一终态需要改的位数 —— 终态只有一个、别无他选，所以这个代价必然也是最小的。反过来，
z = 1时合法终态有三种：(0, 1)、(1, 0)、(1, 1)。我们手上有选择权，于是挑离当前状态最近的那个：只要当前已经有 1，就选包含这个 1 的终态（代价 0）；否则任选一位补上 1（代价 1）。永远不会需要翻两个位，因为翻一个就够了。正确性到这里就完整了：每一位的代价都取到了该位的下界，而各位之间互不干扰、可以同时各自取到下界，所以这些下界之和就是全局最小值，不存在「牺牲某一位换取另一位」的余地。
解题步骤
- 初始化答案
ans = 0。它将累加每一位的代价，因为各位独立、总代价就是逐位代价之和。- 从第 0 位到第 31 位遍历下标
i。之所以固定跑满 32 位、而不是「某个数右移成 0 就停」，是因为三个数的有效位数各不相同，c的高位可能远超a、b，定长循环能一劳永逸地避免漏位。- 每一轮用
(a >> i) & 1、(b >> i) & 1、(c >> i) & 1取出三个数在第i位上的值。右移i位把目标位挪到最低位，再与 1 做与运算把其余位清零，这是取单个位的标准写法。- 若
c的该位是 1：只有当a、b该位都是 0 时才把ans加 1，否则不加。因为或运算只要求至少有一个 1，已经有 1 就等于白拿。- 若
c的该位是 0：把a、b该位的取值直接加到ans上。因为终态被唯一钉死成两个 0，有几个 1 就得翻几次，绝不能只记一次。- 循环结束后返回
ans，它就是全局最少翻转次数。以
a = 2, b = 6, c = 5走一遍。三个数的二进制是a = 010、b = 110、c = 101，第 3 位及更高位上三个数全是 0，属于「要 0 且本来没有 1」，代价都是 0，所以只看低三位。第 0 位上a是 0、b是 0、c是 1，属于「要 1 却一个都没有」，翻任意一个即可，代价 1。第 1 位上a是 1、b是 1、c是 0，属于「要 0 却有两个 1」，两个都得翻，代价 2。第 2 位上a是 0、b是 1、c是 1，属于「要 1 且已经有 1」，代价 0。三位相加得 1 加 2 加 0 等于 3，与官方答案一致。按这个方案翻完之后a变成001、b变成100，a | b正好是101，也就是 5。
代码实现
class Solution {
public int minFlips(int a, int b, int c) {
int ans = 0;
for (int i = 0; i < 32; i++) { // 定长遍历 32 位，避免任一数提前归零导致漏位
int bitA = (a >> i) & 1; // 取出 a 的第 i 位
int bitB = (b >> i) & 1; // 取出 b 的第 i 位
int bitC = (c >> i) & 1; // 取出 c 的第 i 位
if (bitC == 1) {
if (bitA == 0 && bitB == 0) { // 要 1 却都是 0：翻任意一个即可，代价 1
ans++;
}
// 已经至少有一个 1，代价 0，多余的 1 不必翻掉
} else {
ans += bitA + bitB; // 要 0：a、b 该位上的每个 1 都必须翻掉
}
}
return ans;
}
}
func minFlips(a int, b int, c int) int {
ans := 0
for i := 0; i < 32; i++ { // 定长遍历 32 位，避免任一数提前归零导致漏位
bitA := (a >> i) & 1 // 取出 a 的第 i 位
bitB := (b >> i) & 1 // 取出 b 的第 i 位
bitC := (c >> i) & 1 // 取出 c 的第 i 位
if bitC == 1 {
if bitA == 0 && bitB == 0 { // 要 1 却都是 0：翻任意一个即可，代价 1
ans++
}
// 已经至少有一个 1，代价 0，多余的 1 不必翻掉
} else {
ans += bitA + bitB // 要 0：a、b 该位上的每个 1 都必须翻掉
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(1)$。循环固定执行 32 次，每次只做常数次移位、与运算和加法，与输入的具体数值无关。若按有效位数来记，则是 $O(\log \max(a,b,c))$，因为真正需要检查的位数就是三个数中最大者的二进制长度。
- 空间复杂度：$O(1)$。只用了一个答案累加器和三个存放当前位取值的临时变量，没有随输入规模增长的额外空间。
关键点总结
- 若一个整体最优问题在各个维度上互不影响（改动一个维度不会波及其它维度，各维度的目标也不互相冲突），就可以把整体最优拆成逐维度最优再求和。这条原则能把搜索问题直接降级为统计问题。
- 判断「能否逐位独立处理」的判据是有没有跨位耦合。按位或、按位与、按位异或都不产生进位，天然逐位独立；加法、减法、乘法带进位或借位，绝不能这样拆。
- 面对布尔取值的组合，穷尽枚举真值表比凭直觉推导可靠得多。本题只有三个布尔量、八种组合，归成四类后每一类的最小代价都能一眼定死，不给「想当然」留缝隙。
- 求最小代价时，先看终态是否唯一。终态唯一时没有选择空间，代价就等于当前状态与终态的差异量；终态有多个时才需要在候选里挑离当前状态最近的那个。
- 用定长循环（如 32 位）遍历二进制位，而不是「某个数右移到 0 就停」，可以一次性消除多个数有效位数不相等所带来的漏位风险。
- 取单个二进制位的惯用写法是
(x >> i) & 1；只需判断某位是否为 1 时也可以写成(x & (1 << i)) != 0，省掉一次移位取值。
易错点总结
c该位为 0 时只算一次翻转，没有把a、b的两个 1 都算上（写成if (bitA == 1 || bitB == 1) ans++）：用例a = 2, b = 6, c = 5会输出 2，正确答案是 3。第 1 位上a、b都是 1 而c是 0，两个 1 都必须翻成 0、代价是 2，只记一次就少算了一次翻转。c该位为 1 且a、b都为 0 时算成两次翻转（写成ans += 2）：用例a = 2, b = 6, c = 5会输出 4、正确答案是 3；用例a = 1, b = 1, c = 3会输出 2、正确答案是 1。或运算只要有一个 1 就成立，翻第二个是纯粹的浪费。c该位为 1 时要求a、b恰好有一个 1（写成if (bitA + bitB != 1) ans++，把或误当成异或的成立条件）：用例a = 3, b = 3, c = 3会输出 2，正确答案是 0。1 | 1就是 1，多出来的那个 1 根本不需要翻掉。- 把目标条件整体当成
a XOR b == c（写成if ((bitA ^ bitB) != bitC) ans++）：用例a = 2, b = 6, c = 5会输出 1，正确答案是 3。题目要求的是或而不是异或，而且异或版本的逐位代价规则与或完全不同。- 直接数
(a | b) ^ c里 1 的个数当答案（等价于误以为每个不匹配的位都只要翻一次就能修好）：用例a = 2, b = 6, c = 5会输出 2，正确答案是 3。不匹配的位确实只有两个，但其中一位需要两次翻转 —— 不匹配位数和翻转次数不是一回事。- 用
while (a != 0 && b != 0 && c != 0)做循环终止条件：用例a = 1, b = 1, c = 2会输出 2，正确答案是 3。处理完第 0 位后a、b都右移成 0，循环提前退出，c第 1 位上那个「要 1 却都没有」的代价 1 被整整漏掉。- 循环终止条件漏掉
c，写成while (a != 0 || b != 0)：用例a = 1, b = 1, c = 2会输出 2，正确答案是 3。a、b归零后c剩下的高位里还有 1 没处理，同样少算。这类写法在a = 2, b = 6, c = 5上恰好能得到 3，光靠官方样例根本发现不了。- 循环终止条件漏掉
a、b，写成while (c != 0)：用例a = 1, b = 2, c = 1会输出 0，正确答案是 1。c归零后a、b高位残留的 1 本来每一个都必须翻成 0，却一个也没被统计到。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 461. 汉明距离 | 简单 | 同样逐位比对两个数，但只数「不同的位数」，不存在本题那种「要 0 时一位可能要翻两次」的非对称代价 |
| 191. 位1的个数 | 简单 | 只统计单个数里 1 的个数、没有目标值约束，相当于本题「c 位为 0 时数 1 的个数」这一分支的最简形态 |
| 剑指 Offer 15. 二进制中1的个数 | 简单 | 重点在 n & (n - 1) 消除最低位 1 的技巧，用「跳过 0 位」替代本题的定长 32 位扫描 |
| 136. 只出现一次的数字 | 简单 | 靠异或的自反律整体消除成对元素，用的是运算律而非逐位统计，不需要拆位就能出答案 |
| 137. 只出现一次的数字 II | 中等 | 也走「按位独立处理」的路子，但每一位要对出现次数取模 3，是本题逐位思想在计数场景下的推广 |
| 260. 只出现一次的数字 III | 中等 | 用某一位是否为 1 把元素分成两组，把逐位信息当作分治的依据而不是代价的来源 |
| 371. 两整数之和 | 中等 | 反例式对照：加法的位之间存在进位耦合，正因为不能逐位独立处理，才必须反复迭代到进位为空 |