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
以上是 C ++中所有可能子集的XOR之和 的全部内容， 来源链接： utcz.com/z/316580.html
