LeetCode 1318. 或运算的最小翻转次数

约 5 分钟
文章信息 3 个分类 1 个标签
分类
LeetCode 中等 LeetCode 75
标签
位运算

题目描述

✅ 1318. 或运算的最小翻转次数

image-20260928234003432

image-20260928234003435

题意分析

每次可以把 a 或 b 的某一位从零翻成一，或从一翻成零，求让按位或的结果 a | b 等于固定目标 c 所需的最少翻转次数。目标 c 本身不能修改。

一次只改一个输入数的一位，所以同一个目标位可能需要修改两次。题目给定的都是不超过 10^9 的正整数，三十二位扫描足以覆盖全部需要考虑的位置。

解法：按位独立计算或运算的修正成本

核心思路

[!blue]

按位或不会产生进位，某一位的结果只由 a、b 在这一位的两个二进制值决定。翻转某位也不影响其他位，因此可以先求每一位的最少代价，再把它们相加。

如果目标位为零，或运算要求两个输入位都为零。原来哪一边为一，就必须把那一边翻成零；有一个一需要一次，两个都是一需要两次，代价直接等于 bitA + bitB。这些翻转全部不可省略，因为留下任意一个一都会使或结果仍为一。

如果目标位为一，只需至少一个输入位为一。当前已经有一时不必修改，两个都是一也合法；只有两边都为零时，才需要任选一边翻成一，恰好一次就足够。

每一位的代价既是必须支付的下界，也能按上述方法独立达到。所有位置一起执行这些最优修改互不干扰，所以总和就是整体最优，不需要搜索不同位之间的翻转组合。

用右移并与一按位相与取得每个位值。代码固定处理三十二位，不会因为某个输入较早没有高位而漏掉其他输入或目标的高位；输入范围之外三者都为零，自然没有额外成本。

解题步骤

  1. 初始化总翻转数为零，枚举位下标零到三十一。
  2. 分别提取 a、b、c 在当前位的值。
  3. 目标为零时，把两个输入位的和加到答案。
  4. 目标为一且两个输入位都为零时加一次，其余情况不增加。
  5. 返回各位最小代价之和。

代码实现

class Solution {
    public int minFlips(int a, int b, int c) {
        int ans = 0;

        // 定长遍历 32 位，避免任一数提前归零导致漏位
        for (int i = 0; i < 32; i++) {
            // 取出 a 的第 i 位
            int bitA = (a >> i) & 1;
            // 取出 b 的第 i 位
            int bitB = (b >> i) & 1;
            // 取出 c 的第 i 位
            int bitC = (c >> i) & 1;

            if (bitC == 1) {
                // 要 1 却都是 0：翻任意一个即可，代价 1
                if (bitA == 0 && bitB == 0) {
                    ans++;
                }
                // 已经至少有一个 1，代价 0，多余的 1 不必翻掉
            } else {
                // 要 0：a、b 该位上的每个 1 都必须翻掉
                ans += bitA + bitB;
            }
        }

        return ans;
    }
}

func minFlips(a int, b int, c int) int {
    ans := 0
    // 定长遍历 32 位，避免任一数提前归零导致漏位
    for i := 0; i < 32; i++ {
        // 取出 a 的第 i 位
        bitA := (a >> i) & 1
        // 取出 b 的第 i 位
        bitB := (b >> i) & 1
        // 取出 c 的第 i 位
        bitC := (c >> i) & 1
        if bitC == 1 {
            // 要 1 却都是 0：翻任意一个即可，代价 1
            if bitA == 0 && bitB == 0 {
                ans++
            }
            // 已经至少有一个 1，代价 0，多余的 1 不必翻掉
        } else {
            // 要 0：a、b 该位上的每个 1 都必须翻掉
            ans += bitA + bitB
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：固定三十二位下为 $O(1)$；若推广为 B 位表示，则为 $O(B)$。
  • 空间复杂度：$O(1)$，仅保存当前三个比特和累计次数。

关键点总结

[!green]

  • 位之间没有进位或联动，局部最小代价可以直接相加。
  • 目标零要求两个输入都清零，目标一只要求至少保留或建立一个一。
  • 统计的是实际输入位翻转数，不只是输出结果中有多少个位不匹配。

易错点总结

[!yellow]

  • 只数 (a | b) ^ c 中的一，会漏掉目标为零且两边都为一时必须支付的第二次翻转。
  • 目标为一且输入已经有一，却仍翻掉另一个一，会增加本不需要的修改。
  • 只循环到某一个输入归零，其他输入或目标仍可能在更高位存在差异。
  • 将目标 c 也作为可修改对象，会解出不同于原题的问题。

相似题目

题目 难度 关联与区别
461. 汉明距离 简单 同样逐位统计差异，但本题一个目标位可能需要修改两个输入位，不能直接当成汉明距离。
191. 位1的个数 简单 位计数可用于汇总需要修改的位，需先按或运算真值表正确区分单次与双次代价。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/21325613
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！