1318-或运算的最小翻转次数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给你三个正整数 a、b 和 c。

你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算 a OR b == c 成立的最小翻转次数。

「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。

示例 1：

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2020/01/11/sample_3_1676.png)

**输入：** a = 2, b = 6, c = 5
**输出：** 3
**解释：** 翻转后 a = 1 , b = 4 , c = 5 使得 a OR b == c

示例 2：

**输入：** a = 4, b = 2, c = 7
**输出：** 1

示例 3：

**输入：** a = 1, b = 2, c = 3
**输出：** 0

提示：

  • 1 <= a <= 10^9
  • 1 <= b <= 10^9
  • 1 <= c <= 10^9

预备知识

本题需要用到一些位运算的知识：

  • 对于十进制整数 x，我们可以用 x & 1 得到 x 的二进制表示的最低位，它等价于 x % 2：

    • 例如当 x = 3 时，x 的二进制表示为 11，x & 1 的值为 1；

    • 例如当 x = 6 时，x 的二进制表示为 110，x & 1 的值为 0。

  • 对于十进制整数 x，我们可以用 x & (1 << k) 来判断 x 二进制表示的第 k 位（最低位为第 0 位）是否为 1。如果该表达式的值大于零，那么第 k 位为 1：

    • 例如当 x = 3 时，x 的二进制表示为 11，x & (1 << 1) = 11 & 10 = 10 > 0，说明第 1 位为 1；

    • 例如当 x = 5 时，x 的二进制表示为 101，x & (1 << 1) = 101 & 10 = 0，说明第 1 位不为 1。

  • 对于十进制整数 x，我们可以用 (x >> k) & 1 得到 x 二进制表示的第 k 位（最低位为第 0 位）。如果 x 二进制表示的位数小于 k，那么该表达式的值为零：

    • 例如当 x = 3 时，x 的二进制表示为 11，(x >> 1) & 1 = 1 & 1 = 1，说明第 1 位为 1；

    • 例如当 x = 5 时，x 的二进制表示为 101，(x >> 1) & 1 = 10 & 1 = 0，说明第 1 位为 0。

    • 例如当 x = 6 时，x 的二进制表示为 110，(x >> 3) & 1 = 0 & 1 = 0，说明第 3 位为 0。

方法一：枚举 + 位运算

由于在或（OR）运算中，二进制表示的每一位都是独立的，即修改 a 或 b 二进制表示中的第 i 位，只会影响 a OR b 中第 i 位的值，因此我们可以依次枚举并考虑每一位。注意到 a、b 和 c 均小于 10^9，它们的二进制表示最多有 30 位（包含 31 个二进制位的数最小为 2^30 = 1073741824，已经大于 10^9），因此我们只需要从低位到高位枚举这 30 位即可。

设 a、b 和 c 二进制表示的第 i 位分别为 bit_a、bit_b 和 bit_c，根据 bit_c 的值，会有以下两种情况：

  • 若 bit_c 的值为 0，那么 bit_a 和 bit_b 必须都为 0，需要的翻转次数为 bit_a + bit_b；

  • 若 bit_c 的值为 1，那么 bit_a 和 bit_b 中至少有一个为 1，只有当它们都为 0 时，才需要 1 次翻转；

我们将每一位的翻转次数进行累加，在枚举完所有位之后，就得到了最小翻转次数。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minFlips(int a, int b, int c) {
        int ans = 0;
        for (int i = 0; i < 31; ++i) {
            int bit_a = (a >> i) & 1;
            int bit_b = (b >> i) & 1;
            int bit_c = (c >> i) & 1;
            if (bit_c == 0) {
                ans += bit_a + bit_b;
            }
            else {
                ans += (bit_a + bit_b == 0);
            }
        }
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        ans = 0
        for i in range(32):
            bit_a, bit_b, bit_c = (a >> i) & 1, (b >> i) & 1, (c >> i) & 1
            if bit_c == 0:
                ans += bit_a + bit_b
            else:
                ans += int(bit_a + bit_b == 0)
        return ans

复杂度分析

  • 时间复杂度：O(\log C)，其中 C 为常数，在本题中，C 的值为 10^9。O(\log C) 等价于 C 的位数，也就是我们需要枚举的位数。

  • 空间复杂度：O(1)。

 Comments
On this page
1318-或运算的最小翻转次数