集合的整数表示

当元素较少时，可以使用二进制码来表示集合。集合${0， 1， 2， \ldots，n-1}$ 的子集可以用如下方式编码成整数。$$f(S) = \sum_{i \in S}2^i$$

像这样表示之后，一些集合运算可以对应地写成如下方式。

• 空集$\phi$——0
• 只含有第 $i$ 个元素的集合 ${i}$——$1<<i$
• 含有全部$n$个元素的集合——$(1<<n)-1$
• 判断第$i$个元素是否属于集合$S$—— if( S>>i&1 ) 或 if(S & (1<<i))
• 向集合$S$加入第$i$个元素——S |= 1<<i
• 从集合$S$中去除第$i$个元素——S&~(1<<i)
• 集合$S​$和集合$T​$的交集——S&T
• 集合$S$和集合$T$的并集——S|T
• 切换第i位——S ^= 1<<i
• 判断某状态是否有相邻的两者相同——if( S & S<<1 )
• 把一个数字二进制下最靠右的第一个1去掉——S = S&(S-1)

此外，想要将集合{0,1,….,n-1}所有子集枚举出来的话，可以像下面这样写

for(int S=0; S < 1<<n; S++)
{
	//对子集的操作    
}