[LeetCode] 1318. 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 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-flips-to-make-a-or-b-equal-to-c
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一道位运算的题目。对于数字 a 和 b 来说，如果想使他们 OR 的结果等于 c，那么需要保证每一位上的数字的 OR 的结果都与c对应位置上的 digit 一致。思路是我们从右往左遍历二进制数字的32位，对于每一位上的数字而言，如果a的最低位 OR b的最低位 == c的最低位则不需要flip；如果不满足这个条件，则分如下两种情况flip

如果c的最低位 = 1但是 (a | b) 不满足，则说明a或者b起码有一个的最低位要变成1，count++
如果c的最低位 = 0但是 (a | b) 不满足，则说明a或者b的最低位都要是0才行，此时我们根据 a的最低位和 b的最低位到底是什么数字来判断到底需要flip几次

最后将a, b, c三者都右移一位，直到遍历完32位为止。

时间O(1) - 32次操作

空间O(1)

Java实现

 1 class Solution {
 2     public int minFlips(int a, int b, int c) {
 3         // A,B,C三个数字当前位是什么数字
 4         int curA = 0;
 5         int curB = 0;
 6         int curC = 0;
 7         // 需要flip的次数
 8         int count = 0;
 9         for (int i = 0; i < 32; i++) {
10             // 判断A,B,C三个数字的最低位是什么数字
11             if ((a & 1) == 1) {
12                 curA = 1;
13             } else {
14                 curA = 0;
15             }
16             if ((b & 1) == 1) {
17                 curB = 1;
18             } else {
19                 curB = 0;
20             }
21             if ((c & 1) == 1) {
22                 curC = 1;
23             } else {
24                 curC = 0;
25             }
26             if ((curA | curB) != curC) {
27                 // A | B != 0
28                 if (curC == 0) {
29                     if (curA == 1) {
30                         count++;
31                     }
32                     if (curB == 1) {
33                         count++;
34                     }
35                 }
36                 // A | B != 1
37                 else if (curC == 1) {
38                     count++;
39                 }
40             }
41             a = a >> 1;
42             b = b >> 1;
43             c = c >> 1;
44         }
45         return count;
46     }
47 }

LeetCode 题目总结