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

題目描述

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⁹
• 1 <= b <= 10⁹
• 1 <= c <= 10⁹

解答

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))

Jerry Wu7 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;
    }
}

JimJun 7, 2023

Reference

回到題目列表