[Bit Manipulation][Medium] 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/description

LeetCode - The World's Leading Online Programming Learning Platform

Q. a 와 b를 OR 하여서 c 가 될수 있는 최소 flip 수를 구하라.

 

 

 

Solution

 우선 각 자리 bit는 어떻게 구하나. 

  value & 1 의 결과는 제일 아래 자리의 비트가 된다. 

  이를 value가 0 이 될때까지 shift down 하면서 얻으면 될 것이다. 

 

 OR 연산은 어떻게 작동하나. 

 두 수 중 하나가 1이면 1이다. 

 두 수 모두가 0일때만 결과가 0이 된다. 

 

 이를 감안해서 로직을 만들면, 

 c의 현재 bit가 1 이면, a나 b가 모두 0일때만 둘중 하나를 1로 바꾸면 될 것이다. 

 c의 현재 bit가 0 이라면, a나 b가 모두 0이 되도록 flip을 해야 할 것이다. 

 

 이를 로직으로 만든다. 

 

int minFlips(int a, int b, int c)
{
    int ret = 0;
    while (a!=0 || b!=0 || c!=0)
    {
        int cc = c & 1;
        int aa = a & 1;
        int bb = b & 1;
        if (cc == 0)
        {
            if (aa == 1 && bb == 0)         ++ret;
            else if (aa == 0 && bb == 1)    ++ret;
            else if (aa == 1 && bb == 1)    ret += 2;
        }
        else
        {
            if (aa == 0 && bb == 0) ++ret;
        }
        c >>= 1;
        a >>= 1;
        b >>= 1;
    }
    return ret;
}

 

 

 

결과.