集合的整数表示

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

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

• 空集 $\varphi$——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++)
{
	//对子集的操作    
}