原文链接: https://leetcode-cn.com/problems/minimum-flips-to-make-a-or-b-equal-to-c

英文原文

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  成立的最小翻转次数。

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

 

示例 1：

输入：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

通过代码

高赞题解

解题思路：

对于每一位，翻转两次后效果抵消，因此至多只需要翻转一次。

依次考虑数字二进制下的每一位，即每次取出第一位（num & 1），并将数字向右移动一位（num >>= 1）。

当 (a & 1) | (b & 1) != (c & 1) 时，a 和 b 该位上的数字 av 和 bv 需要进行翻转，存在下面两种情况：

• (c & 1) == 1，av | bv == 0。因此 av 等于 0 且 bv 也等于 0，此时只需要翻转 av 或 bv 即可（两数字其中一个为 1 就能或运算为 1）。
• (c & 1) == 0，av | bv == 1。因此 av 或 bv 中可能有一个是 1 或者两个都是 1，此时需要将等于 1 的所有数字翻转。（两个数字都要为 0 才能或运算为 0）

代码：

[]
class Solution {
    public int minFlips(int a, int b, int c) {
        int ans = 0;
        while (c != 0 || a != 0 || b != 0) {
            // 二进制的第一位数字
            int cv = c & 1, av = a & 1, bv = b & 1;
            c >>= 1;
            a >>= 1;
            b >>= 1;
            // 不需要进行翻转
            if ((av | bv) == cv) {
                continue;
            }
            // 需要进行翻转
            if (cv == 1) {
                ans += 1;
            } else {
                if (av == 1) {
                    ans += 1;
                }
                if (bv == 1) {
                    ans += 1;
                }
            }
        }
        return ans;
    }
}

复杂度分析：

• 时间复杂度：$O(N)$，其中 N 为 a，b，c 的最大二进制位数。

 

---

如果该题解对你有帮助，点个赞再走呗~

统计信息

通过次数	提交次数	AC比率
6513	9931	65.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言