数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学给定集合所有可能子集的按位与之和
你如何理解问题“给定集合所有可能子集的按位与之和”？让我们来解读一下。
这个问题要求找到给定集合所有可能子集的按位与之和。
让我们用一个例子来理解这个问题。假设我们有一个集合 {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} 所有可能子集的按位与之和。
方法
现在，我们已经理解了问题要求我们做什么。让我们看看我们将用来解决这个问题的方法。
获取集合的大小和元素作为用户输入
运行一个循环，该循环遍历集合直到集合中的最大值
对于每次迭代，运行另一个循环，该循环遍历集合的所有元素以计算具有设置位的整数个数和第一位置、第二位置等。
在这个循环中，我们还使用公式 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 的数字的计数
我们可以将所有按位与的和存储在一个变量中 total = total + bits * subsets (010 * 3 = 6)
类似地，对于第二次迭代，我们将有值 3，而第三次迭代不会发生，因为位值超过集合中的最大值。
Total = 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;
}
输出
Result: 25
空间复杂度：O(N)
时间复杂度：O(N * log M)
结论
在本文中，我们介绍了如何使用位掩码计算给定集合所有可能子集的按位与之和。希望您能够更好地掌握这个概念。继续学习！
126 次浏览
