C++ 给定集合的所有可能子集的位或之和

问题陈述包括打印给定集合的所有可能子集的位或之和。

集合 是一组相似类型的数据。任何集合的子集都是包含集合的一些元素或所有给定集合的元素的集合。任何集合的子集数量由\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并求和。所有子集的按位OR的和将成为我们的所需输出。

让我们通过下面的例子来理解这个问题。

输入

a[]={2, 4, 6}

输出

36

解释 − 我们在输入中给出了大小为3的数组. a 的子集的数量将是 2^{n}−1，即 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，这是我们需要的输出。

这样，我们需要计算 a 的所有子集的OR结果，其大小为n, 为 \mathrm{2^{n}−1}，并对每种情况进行OR操作。在对所有子集应用位OR运算符后，得到的每个子集的结果的总和将是我们需要的答案。

下面是解决问题的算法。

算法

因为给定数组大小n的所有可能子集的数量为 \mathrm{2^{n−1}}。 因此，为更大的 n 生成给定数组的所有可能子集，然后计算所有生成的子集的OR将花费大量运行时间，这将是解决问题的朴素方法。

相反，一种 高效的方法 是将数组中的所有元素取二进制形式，并计算特定位为1的子集的数量并计算其总和。

按位OR运算符的工作原理如下：

1 || 1 = 1

0 || 0 = 0

0 || 1 = 1

1 || 0 = 1

根据按位OR运算符的特性，我们可以得出结论: 如果任何一个子集中存在某个位为1的元素，则结果将包含该位为1。即 1 OR 0 等于 1。

我们将简单地计算具有第 i 位为0的数组中的元素数量，并将其存储在大小为32的数组中，以获取具有第 i 位为0的子集数量。为此，我们在一个循环中从 i=0 到 i<31 中进行迭代，然后在给定的数组的嵌套循环中进行迭代，检查数组中每个元素的第 i 位。

我们可以通过计算特定元素与 1<<i 的按位AND来检查数组中每个元素的第 i 位。AND运算符在两个位都为1时返回1，并且在至少一个位为0时返回0。

注意 ：<< 是左移操作符，它将特定数的位向左移动。如果我们将1左移i次，结果将是1*2^i。

在计算以第i位为0的数组元素的数量之后，我们可以使用公式\mathrm{2^{n-1}}，其中n为以第i位为0的数组元素的数量，得到我们可以使用这些元素形成的子集的数量。

所有子集的按位OR的和可以通过以下方法计算： \mathrm{sum=((2^{n-1})−2^{以第i位为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++方法中，实现上述算法的

1. 为计算给定数组的所有子集的按位OR的和，我们将创建一个函数。
2. 创建一个大小为32的数组，用于存储具有特定位为0的元素的数量。
3. 在一个for循环中从i=0到i<32迭代，检查数组中每个元素的第i位。使用嵌套的for循环迭代来检查每个元素的第i位，使用AND运算符。如果数组中任何元素的第i位为0，则将所创建数组的第i个索引值增加1，表示具有第i位为0的每个元素。
4. 一旦我们获得了具有第i位为0的元素数组的数量，我们将再次在for循环中从i=0到i<32进行迭代，以计算所有可能子集的按位OR的和。
5. 现在对于第i次迭代，我们将通过将数组的总子集数减去具有第i位为0的子集的数量，并将结果乘以2^i来计算具有第i位为1的子集数量的总和。我们可以使用2^n-1来获取具有第i位为0的子集数量，其中n是我们存储在数组中的具有第i位为0的元素数量。
6. 给定数组的所有子集按位OR的总和可以通过在每次迭代之后更新总和来检查每个位数的第i位来获得。

示例：

// 输入 int arr[] = {1, 2, 3}; 
// 输出 // sum = 10,

//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)。我们使用恒定的空间来解决问题。

结论

本文探讨了计算给定数组的所有可能子集的按位OR的问题。我们在文章中提出了一种有效的技术，并将该算法应用于我们的方法中，以在C++中以O(N)的运行时间和利用恒定空间的方式有效解决问题，而不是找到数组的所有子集并确定OR。

阅读完本文后，希望您对问题和用于在C++中解决问题的算法有了更好的理解。