[LeetCode] 1318. Minimum Flips to Make a OR b Equal to c #1318

grandyang · 2019-05-30T16:34:35Z

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

Example 1:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (`a` OR `b` == `c`)

Example 2:

Input: a = 4, b = 2, c = 7
Output: 1

Example 3:

Input: a = 1, b = 2, c = 3
Output: 0

Constraints:

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

这道题给了三个正整数a，b和c，现在说是可以翻转a和b的二进制数上的任意位，问最少需要翻转多少次就可以使得 a OR b 等于c。这题不算一道难题，主要就是要分析一下各种情况:

当c为0的时候，a和b必须要都为0，才能或起来和c相等。所以只要a和b中有1的话都必须翻转，所以翻转的次数就就是 a+b（注意这里a，b，c 只看作一位数字）。
当c为1的时候，则a和b中只要至少有一个是1就可以了，那么唯一需要翻转的情况就是当a和b同时为0的时候，这种情况可以通过计算 a OR b，若值为0，则说明a和b都是0，此时需要翻转一个。这里可以用 1 - (a | b) 这个式子来概括所有的情况。当a和b中至少有一个1的时候，a | b 值为1，则整个表达式值为0，表示不用翻转。

有了上面的分析之后，代码就很容易写了。因为要遍历整型数的每一位，则最多遍历 32 次就行了，对于每次遍历，通过 & 1 操作来取出最低位上的数字，然后通过上面的逻辑来计算需要翻转的个数加到结果 res 中，再分别对a，b和c右移一位，继续循环即可，参见代码如下：

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            int mc = c & 1, ma = a & 1, mb = b & 1;
            if (mc == 0) {
                res += ma + mb;
            } else {
                res += 1 - (ma | mb);
            }
            a >>= 1; b >>= 1; c >>= 1;
        }
        return res;
    }
};

Github 同步地址:

#1318

参考资料：

https://leetcode.com/problems/minimum-flips-to-make-a-or-b-equal-to-c/description/

https://leetcode.com/problems/minimum-flips-to-make-a-or-b-equal-to-c/solutions/479998/c-bitwise-xor-solution-1-line/

https://leetcode.com/problems/minimum-flips-to-make-a-or-b-equal-to-c/solutions/477690/java-python-3-bit-manipulation-w-explanation-and-analysis/

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~