C++で配列の全要素にXOR演算を適用して合計を最小化する方法

問題の説明

サイズNの配列が与えられます。配列の各要素とある整数XとのXOR演算を行ったとき、その結果の合計が最小となるようなXを見つけてください。

例として、入力配列が arr[] = {8, 5, 7, 6, 9} の場合、最小合計は 30 になります。

各配列要素の2進数表現は次のとおりです。

8 : 1000
5 : 0101
7 : 0111
6 : 0110
9 : 1001

X = 5 のとき、XOR演算後の各値と合計は以下のようになります。

8 ^ 5 = 13
5 ^ 5 = 0
7 ^ 5 = 2
6 ^ 5 = 3
9 ^ 5 = 12
合計 = 30(13 + 0 + 2 + 3 + 12)

アルゴリズム

1. 32ビット整数を扱うため、サイズ32のビットマップ(bitMap)を作成します。
2. 配列を走査し、各要素について以下を処理します。
   a. 要素の0番目のビットが立っている場合、bitMap[0]のカウントをインクリメントします。
   b. 1番目のビットが立っている場合、bitMap[1]のカウントをインクリメントします。以降のビットも同様に処理します。
3. bitMap配列を走査してXを求めます。
   if bitMap[i] > n/2 ならば、X = X + pow(2, i)
4. 入力配列を走査し、各要素とXのXOR演算を行います。
5. 演算結果の合計を計算して返します。

なぜこの方法が機能するのか

XOR演算では、Xの特定のビットが1である位置に対応する配列要素のビットが反転します(0は1に、1は0に変わります)。あるビット位置が配列の半分を超える要素で1になっている場合、Xのそのビットを1に設定すると、「1→0」に変わる要素の数が「0→1」に変わる要素の数を上回るため、合計を減らすことができます。逆に、そのビットが半分以下の要素にしか立っていなければ、Xのビットは0のままにします。この処理を各ビット位置について行うことで、合計が最小になるXが得られます。

実装例(C++)

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
const int MAX_SIZE = 32;

int getSum(int *arr, int n){
    int bitMap[MAX_SIZE];
    int bitLength = 0;
    int sum = 0;
    fill(bitMap, bitMap + MAX_SIZE, 0);
    for (int i = 0; i < n; ++i) {
        int num = arr[i];
        int f = 0;
        while (num > 0) {
            int rem = num % 2;
            num = num / 2;
            if (rem == 1) {
                bitMap[f]++;
            }
            ++f;
            bitLength = max(bitLength, f);
        }
    }
    int candidate = 0;
    for (int i = 0; i < bitLength; ++i) {
        int num = pow(2, i);
        if (bitMap[i] > n / 2) {
            candidate += num;
        }
    }
    for (int i = 0; i < n; ++i) {
        sum += arr[i] ^ candidate;
    }
    return sum;
}

int main(){
    int arr[] = {8, 5, 7, 6, 9};
    cout << "Minimum sum: " << getSum(arr, SIZE(arr)) << "\n";
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum sum: 30