C++で (a OR b) を c と等しくするための最小ビット反転回数

問題概要

3つの正の整数 a、b、c が与えられたとき、a と b の一部のビットを反転して (a OR b == c) を成立させるために必要な最小の反転回数を求めます。ここでの OR は、ビット単位の論理和(ビットごとの OR 演算)を指します。

「反転(フリップ)操作」とは、2進数表現において任意の1ビットを 1→0 または 0→1 に変更することです。たとえば、a = 0010、b = 0110、c = 0101 の場合、反転後は a = 0001、b = 0100 となり、a OR b = 0101 = c が成立します。

解法のアプローチ

この問題は、各ビット位置を独立に評価することで解けます。32ビット整数を前提に、0 ビット目から 31 ビット目まで順に調べていきます。

• 答えとなるカウンタ ans を 0 で初期化します。
• i を 0 から 31 までループします。
  • bitC := (c を i 回右シフト) AND 1 —— c の i ビット目を取り出します。
  • bitA := (a を i 回右シフト) AND 1 —— a の i ビット目を取り出します。
  • bitB := (b を i 回右シフト) AND 1 —— b の i ビット目を取り出します。
  • (bitA OR bitB) が bitC と一致しない場合:
    • bitC が 0 のとき:bitA と bitB が両方 1 なら ans に 2 を加算(両方を 0 に反転する必要があるため)、それ以外は 1 を加算します。
    • bitC が 1 のとき:ans に 1 を加算します(どちらか一方を 1 に反転すればよいため)。
• 最後に ans を返します。

なぜこの手順で正しいのか

ビットごとの OR の性質を考えると、各ビット位置での必要な反転回数は次のように決まります。

• c のビットが 1 の場合:a と b の少なくとも一方が 1 なら一致。両方 0 のときは、どちらか一方を 1 に反転すればよいので反転回数は 1。
• c のビットが 0 の場合:a と b が両方 0 なら一致。片方だけ 1 ならその 1 ビットを反転して回数 1。両方 1 なら両方を 0 に反転する必要があり回数 2。

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

動作の解説

a = 2(010)、b = 6(110)、c = 5(101) の場合をビットごとに確認してみます。

• 0 ビット目:bitA = 0、bitB = 0、OR = 0、bitC = 1 → 不一致。bitC が 1 なので ans に 1 を加算(ans = 1)。
• 1 ビット目:bitA = 1、bitB = 1、OR = 1、bitC = 0 → 不一致。bitC が 0 かつ両方 1 なので ans に 2 を加算(ans = 3)。
• 2 ビット目:bitA = 0、bitB = 1、OR = 1、bitC = 1 → 一致。

合計の反転回数は 3 となり、出力結果と一致します。

計算量

ループは固定の 32 回で実行されるため、時間計算量は O(1)(定数時間)、追加で必要なメモリも O(1) です。入力の大きさに関わらず一定の処理時間で答えを求められるのが特徴です。