集合的整数表示

当元素较少时,可以使用二进制码来表示集合。集合${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++)
{
//对子集的操作
}
❤采之欲遗谁,所思在远道。❤
0%