集合的整数表示

摘要

整理一些集合的小操作

对于大小为 的集合,要求我们表示该集合的任意子集,借助于整数的二进制表示,可以按以下方式编码为整数

位运算

借助位运算来进行集合的运算。一系列例子:

意义 表示
空集 0
只有第i个元素的集合
含有 元素的集合
第i个元素是否选择
添加第i个元素 $s
删除第i个元素
集合的并集 $s
集合的交集

子集枚举

直接循环即可

FOR i from 0 to (1<<n)-1 :
do something

子子集枚举

对于全集U的一个子集S,如何枚举S的子集(相当于S是一个二进制数)。我们倒着循环,每次与 做与运算消除非S集合元素的影响:

int i=s
do :
do something
i=(i-1)&s
while(i!=s)

可以理解为,每次转移的时候,i的最低位1变成0,而这个1后面的0全部变成1。然后取了与s的交集,使得只有子集内的位变换。