C++에서 OR b를 c와 동일하게 만들기 위한 최소 뒤집기

양수 a, b, c가 3개 있다고 가정합니다. (a OR b ==c )를 만들기 위해 a와 b의 일부 비트에서 필요한 최소 플립을 찾아야 합니다. 여기서는 비트 OR 연산을 고려합니다.

플립 연산은 단일 비트 1을 0으로 변경하거나 이진 표현에서 비트 0을 1로 변경하는 것으로 구성됩니다. 따라서 a :0010이고 b :=0110이면 c는 0101이고 뒤집힌 후 a는 0001이 되고 b는 0100이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ans :=0
• 0에서 31 사이의 i에 대해
  • bitC :=(c / 2^i) AND 1
  • bitA :=(a / 2^i) AND 1
  • bitB :=(b / 2^i) AND 1
  • (bitA OR bitB)가 bitC와 같지 않으면
    • bitC가 0인 경우
      • bitA =1이고 bitB =1이면 ans를 2로 늘리고, 그렇지 않으면 ans를 1로 늘립니다.
    • 그렇지 않으면 1만큼 증가
• 반환

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minFlips(int a, int b, int c) {
      int ans = 0;
      for(int i = 0; i < 32; i++){
         int bitC = (c >> i) & 1;
         int bitA = (a >> i) & 1;
         int bitB = (b >> i) & 1;
         if((bitA || bitB) != bitC){
            if(!bitC){
               if(bitA == 1 && bitB == 1){
                  ans += 2;
               }
               else {
                  ans += 1;
               }
            }
            else{
               ans += 1;
            }
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.minFlips(2,6,5));
}

입력

2
6
5

출력

3