使 a OR b 等于 c 的最少翻转次数如何逐位计算？

简化版

要让 (a | b) == c，可以逐位独立分析。若 c 当前位为 1，则 a 或 b 至少一个为 1，若二者都是 0，需要翻转 1 次；若 c 当前位为 0，则 a 和 b 都必须为 0，当前位有几个 1 就要翻转几次。

详细版

OR 运算每一位互不影响，所以遍历 0 到 30 位即可。取出 abit=(a>>i)&1、bbit=(b>>i)&1、cbit=(c>>i)&1。当 cbit==1 时，只在 abit+bbit==0 时加 1；当 cbit==0 时，加上 abit+bbit。

时间复杂度 O(1)，因为整数位数固定；空间复杂度 O(1)。这题的关键不是写循环，而是把 OR 的真值表转成翻转成本。

完整版教学

一、为什么可以逐位独立处理

按位 OR 的结果第 i 位只由 a 和 b 的第 i 位决定，不会产生进位，也不会影响其他位。

result[i] = a[i] OR b[i]

所以总翻转次数就是每一位最小翻转次数的加和。和加法不同，这里没有跨位依赖。

二、OR 真值表怎么看

OR 的规则是：只要有一个 1，结果就是 1；两个都是 0，结果才是 0。

a 位	b 位	a OR b
0	0	0
0	1	1
1	0	1
1	1	1

记忆钩子：OR 要变 1 只缺一个 1，OR 要变 0 必须清掉所有 1。

翻转成本就来自这张表。

三、当 c 当前位是 1

目标位为 1 时，a 和 b 至少有一个当前位为 1 即可。

a=0,b=0 => 需要翻 1 次
a=1,b=0 => 0 次
a=0,b=1 => 0 次
a=1,b=1 => 0 次

如果两个都是 0，随便把其中一个翻成 1 就够了，所以成本是 1，不是 2。

四、当 c 当前位是 0

目标位为 0 时，a 和 b 当前位都必须是 0。

a=1,b=1 => 两个都要翻，成本 2
a=1,b=0 => 成本 1
a=0,b=1 => 成本 1
a=0,b=0 => 成本 0

这正好等于 abit + bbit。

五、代码模板

int minFlips(int a, int b, int c) {
    int ans = 0;
    for (int i = 0; i < 31; i++) {
        int abit = (a >> i) & 1;
        int bbit = (b >> i) & 1;
        int cbit = (c >> i) & 1;
        if (cbit == 1) {
            if (abit == 0 && bbit == 0) ans++;
        } else {
            ans += abit + bbit;
        }
    }
    return ans;
}

如果题目范围包含更高位，可以循环到 32 或使用 while (a != 0 || b != 0 || c != 0)。

六、用数字例子推演

设 a=2(010)、b=6(110)、c=5(101)：

位 0：a=0,b=0,c=1 => 需要 1 次
位 1：a=1,b=1,c=0 => 需要 2 次
位 2：a=0,b=1,c=1 => 需要 0 次

总共需要 3 次翻转。

七、常见误区与追问

误区：当 c 位为 1 时把两个 0 都翻成 1。 OR 只需要一个 1，翻 1 次够了。
误区：当 c 位为 0 时只翻一个 1。 如果 a、b 都是 1，两个都必须清零。
误区：用整体数值差判断。 位运算目标必须逐位分析，数值差没有意义。
追问：为什么没有进位？ OR 是逐位逻辑运算，每位互不影响。
追问：循环多少位？ 取决于输入范围，LeetCode 常见正整数 31 位足够。
追问：能否用位表达式优化？ 可以，但逐位真值表更适合面试解释。

八、加强记忆

这题记住 OR 的两个目标：要 1，至少一个 1；要 0，两个都得 0。c 位为 1 时，只有 a,b 都为 0 才补 1 次；c 位为 0 时，a,b 有几个 1 就翻几个。逐位独立，没有进位，这是位运算题最大的简化。

简化版

详细版