题目描述

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

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

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

样例

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

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

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

限制

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

算法

(按位判定) $O(\log \max(a, b, c))$

1. 按二进制位逐位判定。
2. 如果这一位中 c 的值为 1，但 a 和 b 的值为 0，则答案加 1。
3. 如果这一位中 c 的值为 0，如果 a 或者 b 的值为 1，则答案都加 1。

时间复杂度

• 最多有 $O(\log \max(a, b, c))$ 位，每一位仅需要常数时间判断，故时间复杂度是 $O(\log \max(a, b, c))$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int ans = 0;
        for (int i = 0; i < 30; i++) {
            int x = (a >> i) & 1;
            int y = (b >> i) & 1;
            int z = (c >> i) & 1;

            if (z == 1) {
                if (x == 0 && y == 0)
                    ans++;
            } else {
                if (x == 1)
                    ans++;
                if (y == 1)
                    ans++;
            }
        }

        return ans;
    }
};