1318.Minimum Flips to Make a OR b Equal to c
===

###### tags: `Medium`,`Bit Manipulation`

[1318. Minimum Flips to Make a OR b Equal to c](https://leetcode.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^

### 解答

#### C++

class Solution {
public:
    int minFlips(int a, int b, int c) {
        return __builtin_popcount((a | b) ^ c) + \
            __builtin_popcount(a & b & ((a | b) ^ c));
    }
};

若 `a[i] == 1`, `b[i] == 1`, `c[i] == 0`
* 則 `(a[i] | b[i]) ^ c[i] = 1`，代表需要 flip 一次
* 但是事實上需要 flip 兩次，因為`a[i]`, `b[i]` 都要 flip
* 所以需要額外計算 `builtin_popcount(a & b & ((a | b) ^ c))`

> [name=Jerry Wu][time=7 June, 2023]

#### C#

public class Solution {
    public int MinFlips(int a, int b, int c) {
        int diff = (a | b) ^ c;
        return BitCount(diff) + BitCount(a & b & (~c & diff));
    }

    // 網路查的
    private int BitCount(int n) {
        uint v = (uint)n;
        v = v - ((v >> 1) & 0x55555555);                    
        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
        v = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
        return (int)v;
    }
    
    // 亂湊的...好像很慢
    private int BitCount(int n) {
        long bits =
            ((((n & 0x88888888) * (long)0x11111111) >> 31) & 0xF) +
            ((((n & 0x44444444) * (long)0x22222222) >> 31) & 0xF) +
            ((((n & 0x22222222) * (long)0x44444444) >> 31) & 0xF) +
            ((((n & 0x11111111) * (long)0x88888888) >> 31) & 0xF);
        return (int)bits;
    }
}

>[name=Jim][time=Jun 7, 2023]
### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)