欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++之暴力算法突破二进制枚举子集(实例)

程序员文章站 2022-07-05 22:31:27
问题描述 给定一个集合,枚举所有可能的子集。枚举子集的方法有很多,这里介绍一种非常方便的枚举子集方法——二进制法。 我们可以用二进制的一位表示集合对应的...

问题描述

给定一个集合,枚举所有可能的子集。枚举子集的方法有很多,这里介绍一种非常方便的枚举子集方法——二进制法。

我们可以用二进制的一位表示集合对应的某一元素的选取状态,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)。