C++ 给定集合的所有可能子集的按位与的和

问题“给定集合的所有可能子集的按位与的和”是什么意思？让我们来破解一下。

这个问题要求找出给定集合的所有可能子集的按位与的和。

让我们通过一个例子来理解这个问题。假设我们有一个集合{1, 2, 3}。这个集合有哪些可能的子集呢？

可能的子集包括{1}，{2}，{3}，{1, 2}，{1, 3}，{2, 3}和{1, 2, 3}。现在让我们计算每个子集的按位与。

这些子集的按位与可以按以下方式计算：

子集	位与	注解
{1}	1
{2}	2
{3}	3
{1,2}	0	1的二进制表示为001，2的二进制表示为010，所以两个的位与结果是000
{1,3}	1	1的二进制表示为001，3的二进制表示为011，所以两个的位与结果是001
{2,3}	2	2的二进制表示为010，3的二进制表示为011，所以两个的位与结果是010
{1,2,3}	00	1的二进制表示为001，2的二进制表示为010，3的二进制表示为011，所以全部三个的位与结果是000

这些按位与的和为1+2+3+0+1+2+0 = 9。这个值9是集合{1,2,3}的所有可能子集的按位与的和。

解决方法

现在，我们已经理解了问题要求我们做什么。让我们看一下我们将用来解决这个问题的方法。

获取集合的大小和元素作为用户输入
运行循环，遍历集合直到集合中的最大值
对于每次迭代，再运行一个循环，遍历集合的所有元素，计算具有设定位并且在第1个位置，然后是第2个位置等的整数的数量。
在这个循环中，我们还使用公式subsets = (1LL << numbersWithBitSet) – 1计算可能子集的数量
现在结束循环，对于内层循环的每次迭代，使用公式total += bit * subsets来计算变量中的和，其中subsets是可能子集的数量，bits是外层循环中使用的迭代器，递增为bit = bit << 1

还是听起来困惑吗？让我们用一个例子来理解

假设我们有一个集合={1,2,3} = {001,010,011}

现在我们创建一个循环来遍历所有集合元素。

对于迭代1，bit=1 = 001
- 现在我们有一个内层循环来计算具有第一个位设定的元素数量。
- 使用bit & i（其中i是集合的元素）来计算这个
  - 001 & 001 = 1
  - 001 & 010 = 0
  - 001 & 011= 1
- 因此，我们得到2个第一个位设定为1的数字。
- 可以使用第一个位设定的数字计算可以形成的子集的总数= 1 << 2 – 1 = 3，其中2是第一个位设定为1的数字的数量
- 我们可以将所有按位与的和存储到一个变量总和 = 总和 + bits * subsets（010 * 3 = 6）
对于第二次迭代，我们将得到值3，第三次迭代不会发生，因为位值超过了集合中的最大值。
总计= 6 + 3 = 9

C++代码实现

太多理论？现在，让我们直接进入代码。

下面是计算给定集合的所有可能子集的按位与之和的C++代码实现。

例子

#include <iostream>
#include <vector>

using namespace std;

void print_and_Subsets(const vector<int>& set) {
    long long total = 0; // Use "long long" instead of "long" for 64-bit integers

    for (int bit = 1; bit != 0; bit <<= 1) {
        int numbersWithBitSet = 0;
        for (int i : set) {
            if ((i & bit) != 0) numbersWithBitSet++;
        }

        long long subsets = (1LL << numbersWithBitSet) - 1; // Use "1LL" instead of "1L" for 64-bit integers
        total += bit * subsets;
    }

    cout << "Result: " << total << endl;
}

int main() {
    int n = 5;

    vector<int> set = {1, 2, 3, 4, 5};

    print_and_Subsets(set);
    return 0;
}