C++でAとBのXORがCと等しくなるようにフリップする最小ビットをカウントします

長さNの3つの2進数列 A、B、C が与えられます。それぞれの数列は1つの2進数を表しています。このとき、A と B のXOR（排他的論理和）の結果が C と一致するようにするために、A または B のビットを反転（フリップ）する必要のある最小回数を求めるのが本記事の目的です。

XOR演算の真理値表

まず、XOR演算の真理値表をおさらいしておきましょう。

上の表からわかるように、X と Y が同じ値であれば X XOR Y は 0 となり、異なる値であれば 1 となります。この性質を利用することで、A と B のどのビットを反転すれば C に到達できるかを効率的に判定できます。

反転が必要かどうかの判定条件

各桁 i について、以下の4つのケースに分けて考えます。

• A[i] == B[i] かつ C[i] == 0 の場合 → 反転は不要
• A[i] == B[i] かつ C[i] == 1 の場合 → A[i] または B[i] のどちらか一方を反転し、カウントを +1
• A[i] != B[i] かつ C[i] == 0 の場合 → A[i] または B[i] のどちらか一方を反転し、カウントを +1
• A[i] != B[i] かつ C[i] == 1 の場合 → 反転は不要

入力例と出力例

例1

入力：

A[] = { 0,0,0,0 }　B[] = { 1,0,1,0 }　C[] = { 1,1,1,1 }

出力：

Required flips : 2

解説：

A[0] xor B[0] → 0 xor 1 = 1、C[0]=1 なので反転不要
A[1] xor B[1] → 0 xor 0 = 0、C[1]=1 なので反転（カウント=1）
A[2] xor B[2] → 0 xor 1 = 1、C[2]=1 なので反転不要
A[3] xor B[3] → 0 xor 0 = 0、C[3]=1 なので反転（カウント=2）

例2

入力：

A[] = { 0,0,1,1 }　B[] = { 0,0,1,1 }　C[] = { 0,0,1,1 }

出力：

Required flips : 2

解説：

A[0] xor B[0] → 0 xor 0 = 0、C[0]=0 なので反転不要
A[1] xor B[1] → 0 xor 0 = 0、C[1]=0 なので反転不要
A[2] xor B[2] → 1 xor 1 = 0、C[2]=1 なので反転（カウント=1）
A[3] xor B[3] → 1 xor 1 = 0、C[3]=1 なので反転（カウント=2）

アルゴリズムのアプローチ

• 配列 a[]、b[]、c[] にそれぞれ2進数の各ビットを格納します。
• 関数 flipCount(int A[], int B[], int C[], int n) は、配列 a、b、c とその長さ n を引数として受け取り、「A XOR B」が C と一致するようにするために A[] または B[] のビットを反転する必要のある回数を返します。
• 変数 count は反転回数を表し、初期値は 0 です。
• forループを使って、i = 0 から i = N-1 まで各ビットを順番に走査します。
• 各ビットについて、A[i] と B[i] が等しく C[i] が 1 であれば count をインクリメントします。
• 同様に、A[i] と B[i] が異なり C[i] が 0 であれば count をインクリメントします。
• 最後に count を結果として返します。

このアルゴリズムの計算量は O(N) であり、配列を一度走査するだけで答えが求まるため非常に効率的です。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
int flipCount(int A[], int B[], int C[], int N){
    int count = 0;
    for (int i=0; i < N; ++i){
        // A[i] と B[i] が等しい場合、XORの結果は0。C[i] が 1 なら反転が必要
        if (A[i] == B[i] && C[i] == 1)
            ++count;
        // A[i] と B[i] が異なる場合、XORの結果は1。C[i] が 0 なら反転が必要
        else if (A[i] != B[i] && C[i] == 0)
            ++count;
    }
    return count;
}
int main(){
    // N はビットの総数を表す
    int N = 5;
    int a[] ={1,0,0,0,0};
    int b[] ={0,0,0,1,0};
    int c[] ={1,0,1,1,1};
    cout <<"Minimum bits to flip such that XOR of A and B equal to C :"<<flipCount(a, b, c,N);
    return 0;
}

出力

Minimum bits to flip such that XOR of A and B equal to C :2

まとめ

本記事では、2進数列 A と B のXORが C と一致するようにするために必要な最小ビット反転回数を求める方法を解説しました。ポイントは、XORの真理値表の性質を利用して「同じ値なら0、異なる値なら1」という規則性に基づき、各桁ごとに反転の要否を線形時間 O(N) で判定できることです。シンプルな条件分岐だけで実装できるため、競技プログラミングやビット演算の基礎学習にも最適な問題といえます。