集合的整数表示

发表于 更新于 分类于 ， 本文字数： 547 阅读时长 ≈ 1 分钟

当元素较少时，可以使用二进制码来表示集合。集合 ${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
2
3
4
for(int S=0; S < 1<<n; S++)
{
	//对子集的操作    
}