C++で考えられるすべての部分集合のXORの合計を求める方法

問題の概要

この記事では、n個の数値を含む配列 arr[] が与えられたとき、考えられるすべての部分集合（サブセット）のXORの合計を求める方法を解説します。

手順としては、まず配列のすべての部分集合を列挙し、各部分集合ごとに要素同士のXORを計算します。そして、得られた値をすべて足し合わせたものが答えになります。

具体例で理解しよう

入力: arr[] = {5, 1, 4}
出力: 20

各部分集合のXOR:
{5} = 5
{1} = 1
{4} = 4
{5, 1} = 4
{5, 4} = 1
{1, 4} = 5
{5, 1, 4} = 0

XORの合計 = 5 + 1 + 4 + 4 + 1 + 5 = 20

素朴な解法：すべての部分集合を列挙する

最も直感的な解き方は、ループ処理によって配列から取り得るすべての部分集合を生成し、それぞれの部分集合について全要素のXORを計算、その結果を合計変数に加算していき、最後に合計値を返すというものです。

しかし、このアプローチには大きな欠点があります。部分集合の総数は 2^n 個にもなるため、配列のサイズ n が大きくなると計算時間が指数関数的に増大してしまい、実用的とは言えません。

効率的な解法：XORの性質を活用する

XORの性質をうまく使えば、配列をたった一度走査するだけで答えを求められます。ポイントは以下の通りです。

• まず、配列内の全要素の論理和（OR）を計算します。
• あるビット位置 i がORの中で立っている（1である）とき、そのビットはちょうど 2^(n-1) 個の部分集合のXOR結果に現れます。
• したがって、そのビットが合計に寄与するのは 2^i × 2^(n-1) ＝ 2^(n-1+i) となります。
• これをすべてのビットについてまとめると、最終的な答えは「全要素のOR × 2^(n-1)」というシンプルな式で表せます。

C++での実装例

上記の効率的な解法をC++で実装したプログラムがこちらです。

#include <iostream>
#include <math.h>
using namespace std;

// すべての部分集合のXORの合計を求める関数
int subSetXORSum(int arr[], int n) {
    int bitOR = 0;
    // 全要素のORを計算
    for (int i = 0; i < n; ++i)
        bitOR |= arr[i];
    // 答えは「OR × 2^(n-1)」
    return (bitOR * pow(2, n-1));
}

int main() {
    int arr[] = {1, 5, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"考えられるすべての部分集合のXORの合計は "<<subSetXORSum(arr, size);
}

出力結果

考えられるすべての部分集合のXORの合計は 20

計算量の比較

この効率的な解法は、配列を一度走査するだけなので、時間計算量は O(n) です。一方、すべての部分集合を列挙する素朴な解法は O(n × 2^n) もの時間がかかるため、要素数が増えるほど両者の差は大きく開きます。XORやORといったビット演算の性質を理解しておくことで、一見複雑な問題も劇的にシンプルに解けるようになる好例と言えるでしょう。