C ++中所有可能子集的XOR之和

在这个问题中，我们得到了n个数字的数组aar []。我们的任务是创建一个程序，以查找所有可能子集的XOR之和。

在这里，我们将找到数组的所有子集。然后，对于每个子集，我们将找到子集元素的XOR并将它们添加到sum变量中。

让我们举个例子来了解这个问题，

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的属性。在这里，我们将找到数组所有元素的“或”并检查这些位。如果设置了ith，则用（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