C++之暴力算法突破二进制枚举子集（实例）
程序员文章站
2022-03-23 20:02:01
问题描述
给定一个集合，枚举所有可能的子集。枚举子集的方法有很多，这里介绍一种非常方便的枚举子集方法——二进制法。
我们可以用二进制的一位表示集合对应的...
问题描述
给定一个集合，枚举所有可能的子集。枚举子集的方法有很多，这里介绍一种非常方便的枚举子集方法——二进制法。
我们可以用二进制的一位表示集合对应的某一元素的选取状态，1表示选取，0表示未选取。
举个栗子呢，我们拥有一个集合 {0,1,2,3,4,6} 。那么二进制 0101101 就代表集合 {0,2,3,5} ，具体如下：
| 2进制位数 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|
| 二进制数值 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 选取的元素 | - | 5 | - | 3 | 2 | - | 1 |
位运算
代码中对于二进制的处理可以用位运算来实现。位运算是对二进制的每一位进行计算，所以每一位只有 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 | 0 | 1 | 0 | 0 | 0 |
| A或B | 1 | 1 | 1 | 1 | 1 |
| A异或B | 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（2*2^2=8）。