数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中所有可能子集的异或和
在这个问题中，我们给定一个包含n个数字的数组aar[]。我们的任务是创建一个程序来找到所有可能子集的异或和。
在这里，我们将找到数组的所有子集。然后，对于每个子集，我们将找到子集元素的异或，并将它们添加到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解决这个问题的一个简单方法是使用循环找到数组的所有可能子集，然后对于每个子集找到所有元素的异或并更新sum。最后返回sum。
这并不是一个有效的方法，对于较大的值，时间复杂度将呈指数增长。
一种有效的方法是利用异或的特性。在这里，我们将找到数组所有元素的异或，并检查位。如果第i位被设置，则使用(2^(n-1+i))更新sum。
示例
程序说明我们解决方案的工作原理：
#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
更新于：2020年8月17日
354 次浏览
广告