C++で解く：配列全体とのXOR和が指定した数kになる値を求める方法

問題の概要

本記事では、与えられた配列とある数とのXOR（排他的論理和）の合計が、指定された数kと等しくなるような「その数」を求める問題を解説します。

まず、具体的な例を見てみましょう。

入力: arr[] = {1, 2, 3, 4, 5}, k = 10
出力: 11
説明: 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 11 = 10

入力: arr[] = {12, 23, 34, 56, 78}, k = 6
出力: 73

このように、配列内のすべての要素と答えとなる数をXORした結果がkになる値を導き出すのが目的です。

解法の鍵となるXORの性質

この問題を効率的に解くには、XOR演算子が持つ重要な性質を利用します。それは次の通りです。

A ^ B = C ならば、A ^ C = B が成り立つ

つまり、XORには「同じ値を2回XORすると元に戻る」という可逆性があります。この性質を応用することで、答えを簡単に求められます。

アプローチの手順

解法は非常にシンプルです。以下の手順に従います。

1. 配列を走査し、すべての要素のXOR和を計算します。
2. そのXOR和とkをXORします。その結果が求める答えになります。

これは、配列全体のXOR和をA、答えをBとすると A ^ B = k という関係が成り立ち、前述のXORの性質から B = A ^ k と変形できるためです。

C++による実装コード

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = { 1, 2, 3, 4, 5 }; // 与えられた配列
    int n = sizeof(arr) / sizeof(int); // 配列のサイズ
    int k = 10; // 与えられたk
    int answer = 0;
    for(int i = 0; i < n; i++) // 配列を走査して
        // XOR和を計算
        answer ^= arr[i];

    answer ^= k; // kとXORして答えを求める
    cout << answer << "\n"; // 答えを出力
    return 0;
}

実行結果

11

コードの解説

このプログラムでは、まず変数answerを0で初期化し、forループを使って配列の各要素を順番にXORしていきます。これにより配列全体のXOR和が得られます。

次に、得られたXOR和に対してkをXOR演算します。XORの可逆性により、この結果こそが「配列全体とのXOR和がkになる数」です。最後にその値を出力して処理を終えます。

計算量は配列の走査のみで済むため、O(n)という非常に効率的なアルゴリズムになっています。

まとめ

本チュートリアルでは、「与えられた配列とのXOR和が指定された数kになる数」を求める問題を取り上げました。XOR演算子の可逆的な性質を活かせば、配列のXOR和を計算してkとXORするだけで答えが得られることを学びました。

今回紹介したロジックは、C言語やJava、Pythonなど他のプログラミング言語でも同様に実装できます。ビット演算の理解を深める良い練習問題なので、ぜひ自分でも試してみてください。