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
热门推荐
10 妈妈病人出院祝福语简短
11 工资涨高祝福语简短
12 女儿蛋糕祝福语简短精辟
13 对女儿生日祝福语简短
14 生日祝福语 简短独特男童
15 生日祝福语宿舍舍友 简短
16 班务总结祝福语大全简短
17 对爸爸的简短祝福语
18 感谢教官文案祝福语简短