本文主要是介绍从集合论到位运算,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言
本文将扫清位运算的迷雾,在集合论与位运算之间建立一座桥梁。
在高中,我们学了集合论(set theory)的相关知识。例如,包含若干整数的集合 S={0,2,3}。在编程中,通常用哈希表(hash table)表示集合。例如 Java 中的 HashSet,C++ 中的 std::unordered_set。
在集合论中,有交集 ∩、并集 ∪、包含于 ⊆等等概念。如果编程实现「求两个哈希表的交集」,需要一个一个地遍历哈希表中的元素。那么,有没有效率更高的做法呢?
该二进制登场了。
集合可以用二进制表示,二进制从低到高第 i 位为 1表示 i 在集合中,例如集合{0,2,3}可以用二进制1101表示;反过来,1101就对应集合{0,2,3}。正式地说,包含非负整数的集合S可以用以下方式压缩成一个数字:
例如集合{0,2,3}可以压缩成也就是二进制的1101。
利用位运算「并行计算」的特点,我们可以高效地做一些和集合有关的运算。按照常见的应用场景,可以分为以下四类:
- 集合与集合
- 集合与元素
- 遍历集合
- 枚举集合
一、集合与集合
其中 & 表示按位与,∣ 表示按位或,⊕ 表示按位异或,∼ 表示按位取反。
两个集合的「对称差」是只属于其中一个集合,而不属于另一个集合的元素组成的集合,也就是不在交集中的元素组成的集合。
术语 | 集合 | 位运算 | 集合示例 | 位运算示例 |
---|---|---|---|---|
交集 | A∩B | a&b | {0,2,3}∩{0,1,2} = {0,2} | 1101 & 0111 = 0101 |
并集 | A∪B | a ∣ b | {0,2,3}∪{0,1,2} = {0,1,2,3} | 1101 | 0111 = 1111 |
对称差 | A Δ B | a⊕b | {0,2,3}Δ{0,1,2} = {1,3} | 1101 ⊕ 0111 = 1010 |
差 | A\B | a&∼b | {0,2,3}\{1,2} = {0,3} | 1101 & 1001 = 1001 |
二、集合与元素
通常会用到移位运算。
其中 << 表示左移,>> 表示右移。
术语 | 集合 | 位运算 | 集合示例 | 位运算示例 |
---|---|---|---|---|
空集 | ∅ | 0 | ||
单元素集合 | {i} | 1<<i | {2} | 1<<2 |
全集 | U={0,1,2,⋯n−1} | (1<<n)-1 | {0,1,2,3} | (1<<4)-1 |
补集 | CuS=U\S | ((1<<n)-1)⊕s | U={0,1,2,3} Cu{1,2}={0,3} | 1111 ⊕ 0110 = 1001 |
属于 | (s >> i) & 1=1 | (1101 >> 2) & 1=1 | ||
不属于 | (s >> i) & 1=0 | (1101 >> 1) & 1=0 | ||
添加元素 | S∪{i} | s | (1<<i) | {0,3}∪{2} | 1001 ∣ (1 << 2) |
删除元素 | S \ {i} | s&∼(1 << i) | {0,2,3}\{2} | 1101&∼(1 << 2) |
特别地,如果 𝑠 是 2 的幂,那么 𝑠 &( 𝑠 − 1) =0。
此外,编程语言提供了一些和二进制有关的库函数,例如:
- 计算二进制中的 1 的个数,也就是集合大小;
- 计算二进制长度,减一后得到集合最大元素;
- 计算二进制尾零个数,也就是集合最小元素。
三、遍历集合
设元素范围从0到n-1,挨个判断每个元素是否在集合s中
for (int i = 0; i < n; i++) {if ((s >> i) & 1) { // i 在 s 中// 处理 i 的逻辑}
}
四、枚举集合
枚举所有集合
设元素范围从 0 到 n−1,从空集 ∅ 枚举到全集 U:
for (int s = 0; s < (1 << n); s++) {// 处理 s 的逻辑
}
枚举非空子集
设集合为 𝑠,从大到小枚举 𝑠 的所有非空子集 sub:
for (int sub = s; sub; sub = (sub - 1) & s) {// 处理 sub 的逻辑
}
为什么要写成 sub = (sub - 1) & s
呢?
暴力做法是从s开始,不断减一,直到0但这样做,中途会遇到很多不是s的子集的情况。例如s=10101时,减1得到10100,这是s的子集,但是再减1就得到10011了。这并不是s的子集。下一个子集应该是10001。
把所有的合法子集按顺序列出来,会发现我们做的相当于「压缩版」的二进制减法,例如
10101→10100→10001→10000→00101→⋯
如果忽略掉 10101 中的两个 0,数字的变化和二进制减法是一样的,即
111→110→101→100→011→⋯
如何快速跳到下一个子集呢?比如,怎么从 10100 跳到 10001?
- 普通的二进制减法,是10100-1=10011,也就是把最低位的1变成0,对于最低位的1右边的0都变成1。
- 压缩版的二进制减法也是类似的,对于10100->10001,也会把最低位的1变成0,对于最低位的1右边的0,并不是都变成1,只有在s=10101中的1才会变成1。怎么做到?减1后&10101就行,也就是(10100-1)&10101 = 10001
枚举子集(包含空集)
如果要从大到小枚举 𝑠 的所有子集 sub(从 𝑠 枚举到空集 ∅),可以这样写:
int sub = s;
do {// 处理 sub 的逻辑sub = (sub - 1) & s;
} while (sub != s);
原理是当sub=0时(空集),再减1就得到-1,对应的二进制位111...1,在&s就得到了s,所以循环到sub=s时,说明最后一次循环sub=0(空集),s的所有子集都枚举到了。退出循环。
这篇关于从集合论到位运算的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!