当元素较少时,可以使用二进制码来表示集合。集合${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}所有子集枚举出来的话,可以像下面这样写
1 | for(int S=0; S < 1<<n; S++) |