数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究给定集合的所有可能子集按位或的总和
问题陈述包括打印给定集合的所有可能子集的按位或的总和。
集合是相似类型数据的集合。任何集合的子集都是包含集合中某些元素或给定集合的所有元素的集合。任何集合的子集数量由 $\mathrm{2^{n}−1}$ 给出，其中 n 是给定集合中元素的数量。
例如，a={1,2,3,4,5} 是给定的集合。
{1}. {2,3}, {1,2,3,4} 等被称为 a 的子集，因为它们包含 a 中存在的元素。我们将对给定集合的所有可能子集应用按位或运算符并对结果求和。
OR 运算符的语法
int a,b; int c= a || b;
运算符（‘||’）将返回 a 和 b 的 OR 的结果。
在这个问题中，我们将得到一个大小为 N 的数组。我们需要找到数组所有可能子集的 OR 并对它们求和。数组所有子集的按位或之和将是我们需要的输出。
让我们用下面的例子来理解这个问题。
输入
a[]={2, 4, 6}
输出
36
解释 - 我们在输入中得到了大小为 3 的数组。a 的子集数量将是 $\mathrm{2^{n}−1}$，即 $\mathrm{2^{3}−1=7}$。它们是 {2}, {4}, {6}, {2,4}, {2,6}, {4,6} 和 {2,4,6}。对每个子集应用 OR 运算
{2} =2
{4}=4
{6}=6
{2,4}=2 || 4=6
{2,6}= 2||6=6
{4,6}= 4||6=6
{2,4,6}= 2||4||6=6
以上是 a 的所有可能子集的 OR。所有结果的总和为 36，这是所需的输出。
通过这种方式，我们需要计算大小为 n 的 a 的所有子集的 OR，它将等于 $\mathrm{2^{n}−1}$，并对每种情况取 OR。对每个子集应用按位或运算符后，每个子集的结果之和将是我们需要的答案。
让我们看看解决问题的算法。
算法
由于任何给定大小为 n 的数组的所有可能子集的数量可以是 $\mathrm{2^{n−1}}$。因此，为较大的 n 值生成给定数组的所有可能子集，然后计算所有生成的子集的 OR 将花费很多运行时间，这将是解决问题的朴素方法。
相反，解决问题的有效方法可以采用数组中所有元素的二进制形式，并计算具有特定位为 1 的子集的数量，然后计算总和。
按位或运算符按以下方式工作
1 || 1 = 1
0 || 0 = 0
0 || 1 = 1
1 || 0 = 1
参考按位或运算符的属性，我们可以得出结论，如果子集中任何一个元素的特定位为 1，则结果将包含该位为 1 或 0 等于 1。
我们将简单地计算数组中第 i 位为 0 的元素的数量，并将它们存储在一个大小为 32 的数组中，以获取第 i 位为 0 的子集的数量。为此，我们将从 i=0 迭代到 i<31，然后在嵌套循环中迭代给定数组以检查数组中每个元素的第 i 位。
我们可以通过计算特定元素和 1<<i 的按位 AND 来检查数组中每个元素的第 i 位。如果两个位都是 1，则 AND 运算符返回 1，如果任何一个位为 0，则返回 0。
注意：<< 是左移运算符，它将特定数字的位左移。如果我们将 1 左移 i 位，则结果将是 1*2^i。
在计算数组中第 i 位为 0 的元素数量后，我们可以使用公式 $\mathrm{2^{n−1}}$ 获取我们可以使用这些元素形成的子集的数量，其中 n 将是数组中第 i 位为 0 的元素的数量。
所有子集的按位或之和可以通过以下方式计算
$\mathrm{sum=((2^{n−1})−2^{numner\:of\:elements\:with\:ith\:bit\:0}−1)*2^{i}}$
这里，n=给定数组中的元素数量。
i=位数，其中 i 的范围从 0 到 31。
如果子集中的任何元素的第 i 位为 1，则根据 OR 运算符的属性，结果将具有该第 i 位为 1。从 0 到 31 的每个 i 的第 i 位为 1 的所有子集的总数乘以 2^i 将给出数组所有子集的 OR 的结果总和。
因此，从所有子集的总数中减去每个元素第 i 位为 0 的子集的数量将给出第 i 位为 1 的子集的数量。
我们将使用上述算法，这可能是解决问题的有效方法。
方法
在我们的方法中用 C++ 实现上述算法的步骤
为了计算给定数组的所有子集的按位或之和，我们将创建一个函数。
我们将创建一个大小为 32 的数组来存储具有特定位为 0 的元素的数量。
从 i=0 迭代到 i<32 以检查数组中每个元素的第 i 位。在嵌套 for 循环中迭代以使用 AND 运算符检查每个元素的第 i 位。如果数组中任何元素的第 i 位为 0，则对于每个第 i 位为 0 的元素，将创建的数组中第 i 个索引处的值增加 1。
一旦我们得到了数组中第 i 位为 0 的元素的数量，我们将在从 i=0 到 i<32 的 for 循环中再次迭代以计算所有可能子集的 OR 之和。
现在对于第 i 次迭代，我们将通过从数组的所有子集的数量中减去第 i 位为 0 的子集的数量，并将结果乘以 2^i 来计算第 i 位为 1 的子集的数量，以获得总和。我们可以使用 2^n−1 获取第 i 位为 0 的子集的数量，其中 n 将是我们存储在创建的数组中的第 i 位为 0 的元素的数量。
给定数组的所有子集的按位或总和可以通过在每次迭代后更新总和来获得，以检查最多 31 的每个第 i 位。
例子
//C++ code to find the sum of bitwise OR of all the subsets of the given array
#include<bits/stdc++.h>
using namespace std;
//function to calculate sum of bitwise OR of all subsets
int sum(int a[], int N){
int bits[32]={0}; //to store the number of elements with ith bit as 0
for(int i=0;i<32;i++){ //to check for every bit
for(int j=0;j<N;j++){ //to check elements with ith bit as 0
//checking ith bit of each element in the array using AND operator
//left shift 1 by i
if((a[j]&(1<<i))==0){
bits[i]++; //if ith bit is 0 of the element increase bits[i] by 1
}
}
}
int sum=0; //to store the sum of OR of all the subsets
for(int i=0;i<32;i++){ //to calculate the total sum
//number of subsets with a element with ith bit as 1 multiplied by 2^i
sum = sum + ((pow(2,N)-1)-(pow(2,bits[i])-1))*pow(2,i);
}
return sum; //return the sum
}
int main()
{
int a[]={2, 3, 7, 10, 4};
int N;
N=sizeof(a)/sizeof(a[0]); //calculating the size of the array
//calling the function
cout<<"The total sum of OR of all the subsets of a : "<<sum(a,N)<<endl;
int b[] = {5, 9, 25, 52, 32, 21, 15};
N=sizeof(b)/sizeof(b[0]);
cout<<"The total sum of OR of all the subsets of a : "<<sum(b,N)<<endl;
return 0;
}
输出
The total sum of OR of all the subsets of a : 308 The total sum of OR of all the subsets of a : 6492
时间复杂度 - O(N)，其中 N 是给定数组的大小。
空间复杂度 - O(1)，因为我们只创建了一个大小为 32 的数组，使空间复杂度为 O(32)，等于 O(1)。我们正在使用恒定的空间来解决问题。
结论
本文涵盖了计算给定数组的所有可能子集的按位或的问题。我们在文章中提出了一个有效的技术，并在我们的方法中应用了该算法，以在 C++ 中有效地解决问题，运行时间为 O(N)，并使用恒定空间，而不是查找数组的所有子集并确定 OR。
阅读完这篇文章后，我希望您对问题和用于在 C++ 中解决问题的算法有了更好的理解。
210 次查看
