Minimum Flips To Make A or B Equal to C

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

分析

位运算分析
- 对每一位（从低位到高位）分别判断 a 、b 、c 的二进制表示：
- x = a >> i & 1：表示 a 的第 i 位
- y = b >> i & 1：表示 b 的第 i 位
- z = c >> i & 1：表示 c 的第 i 位
根据 z 的值，分情况讨论：
- 如果 z = 0 ：
  - 需要 x = 0 且 y = 0，因此：需要翻转的次数 = x + y
- 如果 z = 1 ：
  - 至少需要 x = 1 或 y = 1 。若 x = 0 且 y = 0 ，则需要翻转 1
循环计算

逐位处理 a 、b 和 c ，根据上述规则累加所需的翻转次数

终止条件

由于题目限制 a, b, c 小于 1e9，其最大值在 2^30 以内，因此只需处理前 30 位即可

时间复杂度

O(1)

空间复杂度

O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution
{
public:
    int minFlips(int a, int b, int c)
    {
        int res = 0;
        // 遍历 30 位
        for (int i = 0; i < 30; ++i)
        {
            int x = a >> i & 1; // a 的第 i 位
            int y = b >> i & 1; // b 的第 i 位
            int z = c >> i & 1; // c 的第 i 位

            if (z == 0)  // 如果 z 为 0
                res += x + y; // 需要翻转 x 和 y 中的所有 1
            else if (!x && !y) // 如果 z 为 1 且 x 和 y 都为 0
                ++ res; // 至少需要翻转一个 0 为 1
        }
        return res; // 返回总翻转次数
    }
};