C++で可能なすべてのサブセットのXORの合計

この問題では、n個の数の配列aar[]が与えられます。私たちのタスクは、すべての可能なサブセットのXORの合計を見つけるプログラムを作成することです。

ここでは、配列のすべてのサブセットが見つかります。次に、サブセットごとに、サブセットの要素のXORを見つけて、それらを合計変数に追加します。

問題を理解するために例を見てみましょう

Input: arr[] = {5, 1, 4}
Output: 20
Explanation: XOR of all subsets:
{5} = 5
{1} = 1
{4} = 4
{5, 1} = 4
{5, 4} = 1
{1, 4} = 5
{5, 1, 4} = 0
Sum of XOR = 5 + 1 + 4 + 4 + 1 + 5 = 20

この問題の簡単な解決策は、ループを使用して配列のすべての可能なサブセットを検索し、サブセットごとにすべての要素のXORを検索して、合計を更新することです。最後に合計を返します。

これは効果的なアプローチではありません。値が大きい場合、時間計算量は指数関数的に増大します。

効率的なアプローチは、XORのプロパティを使用することです。ここでは、配列のすべての要素のORを見つけて、ビットをチェックします。 i番目が設定されている場合は、合計を（2 ^（n-1 + i））で更新します。

例

ソリューションの動作を説明するプログラム

#include <iostream>
#include <math.h>
using namespace std;
int subSetXORSum(int arr[], int n) {
   int bitOR = 0;
   for (int i=0; i < n; ++i)
   bitOR |= arr[i];
   return (bitOR * pow(2, n-1));
}
int main() {
   int arr[] = {1, 5, 4};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Sum of XOR of all possible subsets is "<<subSetXORSum(arr, size);
}

出力

Sum of XOR of all possible subsets is 20