二進制表示集合

• 空集：​

  ​0​

  ​
• 隻有第 i 個元素的集合：​

  ​1<<i​

  ​
• 含有全部 n 個元素的集合：​

  ​(1<<n)-1​

  ​
• 判斷第 i 個元素是否屬于集合 S：​

  ​if(S>>i&1)​

  ​
• 向集合中加入第 i 個元素：​

  ​S|1<<i​

  ​
• 從集合中去除第 i 個元素：​

  ​S&~(1<<i)​

  ​
• 集合 S 和 T 的并集：​

  ​S|T​

  ​
• 集合 S 和 T 的交集：​

  ​S&T​

  ​

枚舉\(\{0,1,...,n-1\}\)的所有子集：

for(int S=0;S<1<<n;S++){

//對子集的處理

}

枚舉 sup 的所有子集：

int sub=sup;

do{

//對子集的處理

sub=(sub-1)&sup;

}while(sub!=sup); //-1&sup=sup結束循環

枚舉\(\{0,1,...,n-1\}\)的所有子集大小為 k 的集合的方法：

int comb=(1<<k)-1;

while(comb<1<<n){

//對集合的處理

int x=comb&-comb,y=comb+x;

comb=((comb&~y)/x>>1)|y;

}

①​

​x&(-x)​

​的值就是将其最低位的1獨立出來後的值

②​

​y=comb+x​

​就是将 comb 從最低位的1開始的連續的1都置0了

③​

​z=comb&-y​

​得到了最低位1開始的連續區間

④​

​z/x​

​可以将 z 不斷右移，直到最低位為1