用二进制法枚举子集
给定一个集合，枚举所有的子集。其中枚举子集的方法很多，在这里我们介绍一种用代码编写非常方便的枚举子集的方法——二进制法。
二进制（binary）在数学和数字电路中指以2为基数的记数系统，以2为基数代表系统是二进位制的。这一系统中，通常用两个不同的符号0（代表零）和1（代表一）来表示 。数字电子电路中，逻辑门的实现直接应用了二进制，因此现代的计算机和依赖计算机的设备里都用到二进制。每个数字称为一个比特（Bit，Binary digit的缩写）。
我们可以用二进制的一位表示集合对应某一元素的选取状态，1 表示选取，0 表示未选取。
例如，我们拥有一个集合 ${0,1,2,3,4,5,6}$。那么二进制的 0101101 就代表了子集合 ${0,2,3,5}$。如下所示：
| 2进制数位 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|
| 二进制数值 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 读取的元素 | - | 5 | - | 3 | 2 | - | 0 |
位运算
代码中对于二进制的处理可以用位运算来实现。位运算是对二进制的每一位进行计算，所以每一位只有 0 或 1 两种可能。先介绍三种常用的位运算符：与 &、或 |、异或 ^，运算规则如下表所示。
| A | B | A&B | A|B | A^B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
- 与运算：两者都为 1 时，结果即为 1，否则为 0。
- 或运算：两者都为 0 时，结果即为 0，否则为 1。
- 异或运算：是两者同为 0 或 1 时，结果即为 0，否则为 1。
两个十进制整数进行位运算结果是多少呢？
举个例子：A = 25 与 B = 14 做位运算，A 转化为二进制是 11001，B 转化为二进制是 01110，那么如下表。
| A=25 | 1 | 1 | 0 | 0 | 1 |
| B=14 | 0 | 1 | 1 | 1 | 0 |
| A&B=8 | 0 | 1 | 0 | 0 | 0 |
| A|B=31 | 1 | 1 | 1 | 1 | 1 |
| A^B=23 | 1 | 0 | 1 | 1 | 1 |
一定要注意，不要把 A^B 当成了 A 的 B 次方。
位运算符中有两种操作，左移 << 和右移 >>。右移具体还分为带符号右移与无符号右移，这里我们提到的右移指的是带符号右移，无符号右移使用较少，在这里不做解释。
对于 A << B，表示把 A 转化为二进制后向左移动 B 位（在末尾添加 B 个 0）。
对于 A >> B，表示把 A 转化为二进制后向右移动 B 位（删除末尾的 B 位）。
比如 2 << 2，2 转化为二进制则是 10，那么就是 10 左移动 2 位，就变成了二进制 1000，转化为十进制是 8，所以 2 << 2 = 8。
上面可能有点绕，我们来看一个可以用二进制枚举来解决的问题：
话说大诗人李白，一生好饮。幸好那个时候没有交规，他也不开车。
一天，他提着酒壶，从家里出来。酒壶中有酒两斗，他边走边唱：“无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。”
这一路上，他一共遇到店 5 次，遇到花 10 次，已知最后一次遇到的是花，他正好把酒喝完了。请你计算李白遇到店和花的次序，总共有多少种可能的方法。
这个题目的解法有很多，二进制枚举是一种写起来非常简洁的解法。我们已经知道他遇到了 5 次店，遇到了 10 次花，并且最后一次遇到花的时候，刚好把酒喝完了。那么我们可以把店作为二进制中的 1，把花作为二进制中的 0，因为已经确定最后一次遇到的是花，所以我们需要判断枚举的结果是否刚好包含 5 个 1 和 9 个 0。那么我们就枚举的 14 位二进制的所有可能并加以判断即可，判断思路为判断二进制是否有 9 个 0，5 个 1，并且最终酒刚好剩 1 斗。
根据这个思路，可以写出如下代码：
#include <iostream>
using namespace std;
int main()
{
int value = 0; // 合法方案数
for(int i = 0; i < (1<<14); i++){
int var1 = 0;
int var0 = 0;
int num = 2;
for(int j = 0; j < 14; j++){
if(i&(1 << j)){
// 此处的 if 判断二进制的 i 从右数第 j + 1 位是否为 i
var1++;
num = num * 2;
}else{
var0++;
num = num - 1;
}
}
if(var1 == 5 && var0 == 0 && num == 1){
value++;
}
}
cout << value << endl;
return 0;
}