当集合元素个数较少时，可以用二进制来表示。集合{0, 1, ..., n - 1}的子集S可以用如下方法编码成整数：
f(S)=∑i∈S2i 本质就是用每一个二进制位来表示某个元素是否出现。 空集 ϕ ：0只含有第i个元素的集合{i}：1 << i含有全部n个元素的集合{0, 1, ..., n - 1}：(1 << n) - 1判断第i个元素是否属于集合S：S >> i & 1，or S & (1 << i) 向集合中加入第i个元素S U {i}：S | 1 << i向集合中去除第i个元素S \ {i}：S & ~(1 << i)集合S和T的并集 S∪T ：S | T集合S和T的交集 S∩T ：S & T枚举全集S的所有子集：for(int s = 0; s < (1 << n); s++) {/* 处理子集 */}问题：给定一个含有若干元素的集合s(s是一个二进制数)，枚举该集合的所有子集，含有n个元素的集合共有 2n 个子集。
分析：找到s中1的个数和位置，然后通过删除若干个1来获得s的所有子集。为了获得所有的子集可能需要对之前删掉的1进行二次访问，可以通过和原始集合s进行与操作实现对之前删掉的1的二次访问。伪代码如下：
int subset = s; do{ // 处理子集 subset = (subset - 1) & s; }while(subset != s); // 当subset为-1的时候说明所有的子集已经遍历完问题：遍历一个集合的所有k元素子集。例如，含有4个元素的所有子集为：00001111->00010111->00011011->...->11110000 分析：分四步解决：以00010111 --> 00011011为例 1. 求出从最低位的1开始的连续的1的区间 (00010111 --> 00000111) 2. 将此区间全部变为0，并将区间左侧的那个0变为1 (00010111 --> 00011000) 3. 将第1步取出的区间右移，直到剩下的1的个数减少一个 (00000111 --> 00000011) 4. 将第2步和第3步的结果异或 (00011000 | 00000011 = 00011011) 伪代码描述：
int comb = (1 << k) - 1; // 最小的 k 元素子集 while(comb < (1 << n)){ // 处理子集 /* 得到下一个子集 */ int x = comb & -comb; // x 表示最低位1的位置 int y = comb + x; // y 表示第2步操作的结果 comb = (((comb & ~y) / x) >> 1) | y; }python代码
#!/usr/bin/python # -*- coding: utf-8 -*- def subset(k, n): comb = (1 << k) - 1 while comb < (1 << n): print("next set: ", comb, bin(comb)[2:]) x = comb & -comb y = comb + x comb = ((int((comb & ~y) * 1.0 / x)) >> 1) | y subset(4, 8)问题：给定一个集合，枚举所有可能的子集。 实现：
// 枚举子集 for(int s = 0; s < (1 << n); ++s){ // 输出子集S对应的各个元素 for(int i = 0; i < n; ++i){ if(s & (1 << i)) // or (s >> i) & 1 printf("%d ", i + 1); } printf("\n"); }