【位运算】集合的整数表示

语言基础

为了学习状压等等要用到二进制的东西，先来介绍（鬼扯）一下位运算的几个知识

1
2
3
4
5
x<<n		//x在二进制中左移n位
x>>n		//x在二进制中右移n位
x&y			//x与y按位“与”
x|y			//x与y按位“或”
~x			//x按位取反

于是有了这些基础就可以推出（虾搞）许多状态

在此用一个整数表示一个集合中是否有第i（i>0）个元素（有则二进制第i位为1，反之为0）:

1
2
3
4
5
6
7
8
0					//空集
1<<(i-1)			//只含有第i个元素
(1<<i)-1			//含有第1~i个元素
if (S>>(i-1)&1)		//判断第i个元素是否属于S
S|1<<(i-1)			//向S中加入第i个元素
S&~(1<<(i-1))		//从S中删除第i个元素
S|T					//S与T的并集
S&T					//S与T的交集

基本就这些