集合的整数表示

当集合的元素数比较少的时候，我们可以使用整数来表示集合（用到整数的二进制）

一些集合运算可以这么写：

• 空集：0
• 只含有第i个元素的集合{i}: 1<<i
• 含有全部n个元素的集合{0, 1, …, n-1}: (1<<n)-1
• 判断第i个元素是否属于集合S： if(S>>i&1)
• 向集合中加入第i个元素：S|(1<<i)
• 从集合中去除第i个元素：S&~(1<<i)
• 集合S和T的并集：S|T
• 集合S和T的交集：S&T

枚举集合S的所有子集

for( int S = 0; S < (1<<n); ++S)
{
     //对于集合的处理
}

枚举{0, 1, …, n-1}所包含的所有大小为k的子集

下面的代码根据字典序升序，枚举出所有满足条件的二进制码

int comb = (1<<k) - 1;
while(comb < (1<<n) )
{
    //这里进行针对组合的处理

    int x = comb & -comb;
    int y = comb + x;
    comb = (((comb & ~y) / x) >>1 ) | y;
}

转载请注明来源：https://www.longjin666.top/?p=1194