本文档主要是对算法刷题中使用到的位运算知识的整理。
1、位运算基础
在二进制的世界中,数字只有“0”和“1”,由“0”和“1”形成的指令也就是计算机可以直接执行的指令。在大学中学到的数电、模电中的与、或、非、异或等操作就是今天将要讲的二进制的基本位运算。
1.1 与运算
与运算的表示符号是“&”,两个二进制数之间进行与运算(与操作)是指对应位之间进行与运算,比如“0010&1011=0010”,对应位之间的与操作分别为 “0&1=0”、“0&0=0”、“1&1=1”、“0&1=0”。
还记得在数电这门课程中关于二进制的与运算是这样讲的,二进制数的“0”和“1”就像是电路中开关的“开”与“闭”,与操作就像是一个电路中有两个串联的开关,只有开关都“闭合”即表示开关“闭合”的两个二进制数都为“1”时,电路才会导通,其余任何情况电路都不会导通。
因此,与运算有这样的计算规则:“全1为1,有0则0”。
1.2 或运算
或运算的表示符号是“|”,或操作就像是一个由两个开关并联组成的电路,只要有一个开关“闭合”,这个电路就会导通。因此,或运算有这样的计算规则:“有1为1,全0则0”。
0或上任意一个数仍是这个数本身。
1.3 非运算
非运算的表示符号是“~”,非操作非常简单,主要把“0”变成“1”,“1”变成“0”即可。若a表示一个一位二进制数(要么是0,要是1),则a的非运算结果为“1-a”,并且有 "a & (1-a) = 0"、"a | (1-a) = 1"。
1.4 异或运算
异或运算的表示符号为 "^",计算规则是“相同为0,相异为1”。
两个相同的数异或值为0。
1.5 移位运算
左移i位相当于乘以2的i次幂,右移i位相当于除以2的i次幂。
2、位运算应用
2.1 状态压缩
如果遇到字符串的题目,字符串中没有重复的字符,并且都是大写或者都是小写字母,就可以优先考虑状态压缩,然后采用位运算进行后续求解。
怎么将字母表示为二进制状态?
1、切入点:字符串的长度不超过26,任一字符串中,每个字母至多出现一次;
2、每个字符对应到二进制压缩的位上, 'a' 对应到 0 位, 'b' 对应到 1 位,以此类推 'z' 对应 25 位;
3、所有的字符串都可以用二进制数来唯一表示,比如’abd‘可以用二进制数 1011 唯一表示;
具体有如下的实现代码:
int mask = 0; for (int i = 0; i < str.size(); ++i) { mask |= 1 << (str[i] - 'a'); }
2.2 集合表示
参考内容
集合可以使用二进制来进行表示:二进制从低到高的第i位为1表示i在集合中,为0表示i不在集合中。比如集合 {0,2,3}可以用二进制 “1101”,相应的二进制 “1101” 就可以表示集合{0,2,3}。正式的公式如下所示,其中S表示每个集合。
对于{0, 2, 3}这样的一个集合,有,其对应的二进制数为“1101”。
借助于二进制的位运算和集合表示法可以将集合与集合之间的关系,集合与元素之间的关系进行如下总结。
2.2.1 集合与集合之间的关系
注:
数学上,两个集合的对称差是只属于其中一个集合,而不属于另一个集合的元素组成的集合,去掉两个集合的交集,集合各自剩下的元素组成的新集合即为答案。
注意区分差和对称差,比如A-B表示在集合A中但是不在集合B中的元素组成的集合。
如果B⊆A即B是A的子集,则A-B等价于AΔB,即位运算a&~b等价于a⊕b。
2.2.2 元素与集合之间的关系
注:
补集,一般指绝对补集,指全集中不属于某一子集的所有元素组成的集合。
对于删除元素可以有两种方法,如果确定某一元素就在集合中,可以使用位运算进行删除;如果不确定某一元素是否在集合中,则使用 &~ 的方法。
还有一些问题可以借助相应程序语言提供的库函数来解决:
注:
二进制的长度指的是二进制数中最高位的1位于二进制数从低位往高位数的第几位+1(因为二进制数位是从0位开始数的),__builtin_clz() 计算的是32位二进制数从高位往低位数的连续0的个数。二进制的长度普通计算方法是这样的:
int getLength(uint32_t n) {int res = 0;while (n) {++res;n >>= 1;}return res;}
集合 {0,2,3} 用二进制数表示为 “1101”,该集合中的最小元素是 0,__builtin_ctz() 表示的是32位二进制数中从低位往高位数连续0的个数。
只包含最小元素的子集可以用 s & -s 来表示,-s在计算机中是用s的补码来表示的,即反码+1 (~s + 1)。
例如一个集合用二进制数表示为 s = 1010,-s = ~s + 1 = 0101 + 1 = 0110, s & -s = 0010, 于是集合中最小元素表示的二进制数为0010。
因为集合可以用二进制数来表示了,所以求集合中的元素个数可以通过计算对应的二进制数中“1”的个数来完成。这样也就可以通过一些简单的方法得到:
int hammingWeight(uint32_t n){int ans = 0;while(n){if(n & 1){++ans;}n >>= 1;}return ans;}int hammingWeight(uint32_t n){int ans = 0;while(n){n &= (n - 1);++ans;}return ans;}
代码中提到的汉明重量表示的是字符串相对于同样长度的0字符串的汉明距离(两个相同长度的字符串,对应位置字符不同的数目),因此汉明重量就是统计字符串中非0字符的个数,对于二进制串来说就是统计1的个数,如1011的汉明重量就是3。
2.2.3 遍历集合
设元素范围从 0 到 n-1,枚举判断每个元素是否在集合 s 中:
for (int i = 0; i < n; ++i) {if ((s >> i) & 1) { // 如果元素 i 是否在集合 s 中// 代码块}}
2.2.4 枚举集合
设集合内元素范围为 0 到 n-1,枚举该集合的所有子集(包括空集和全集)为:
for (int s = 0; s < (1 << n); ++s) {// 每一个s表示的就是该集合的一个子集}
设集合为s,从大到小枚举s的所有非空子集sub:
for (int sub = s; sub; sub = (sub - 1) & s) {// 枚举的每一个sub都是符合题意的非空子集sub}
需要注意的是这里的集合S已经不是从 0 到 n-1 的 n 个元素的集合了。普通的二进制减法会把最低位的1变成0,同时1右侧的0变为1。这里压缩版的二进制减法是类似的,最低位的1依然变为0对应sub-1操作,而1右侧的0只保留s中的1对应的是 &s 操作。
例如某一个集合的二进制数表示为 101010,普通的二进制减法的下一位是 101001,而压缩版的二进制减法也就是我们需要的下一位是 101000,通过 101010 & (101010-1) 计算得到。