利用位运算求子集

位运算求子集

紫书第189页

给你一个集合，让你求集合的所有子集；

我们都知道长为n的集合子集个数为 2^n 个(包含了空集)；

一般都是递归求子集，没想到还可以运用位运算求；

具体思路就不展开了，总的来说就是每个元素在子集里都有两种情况（取或不取），可以用0和1来代表，这就跟位运算的性质所吻合；

代码：

#include<bits/stdc++.h>
#define LL long long
#define pa pair<int,int>
#define lson k<<1
#define rson k<<1|1
#define inf 0x3f3f3f3f
//ios::sync_with_stdio(false);
using namespace std;
const int N=200100;
const int M=1000100;
const LL mod=998244353;
int a[4]={1,2,3,4};
void print_subset(int n,int s){
	for(int i=0;i<n;i++){
		if(s&(1<<i)) cout<<a[i]<<" ";//这个判断就是求数s化为二进制后二进制位为1的位置 
	}
	cout<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	for(int i=1;i<(1<<4);i++){//总共有2^4种情况，这里排除了空集
		print_subset(4,i);
	}
	return 0;
}