Skip to content

Bit Manipulation

集合论(set theory), 例如, 包含若干整数的集合\(S= {0, 2, 3}\). 在编程中, 通常用哈希表(hash table)表示集合. 例如 Java中的HashSet.

在集合轮中, 有个交集\(\cap\), 并集\(\cup\), 包含于\(\subseteq\)等等概念. 如果编程实现求两个哈希表的交集, 需要一个一个地遍历哈希表中的元素. 那么, 有没有效率更高的做法呢?

该二进制登场了.

集合可以用二进制表示, 二进制从低到高第\(i\)位为1表示\(i\)在集合中, 为\(0\)表示\(i\)不在集合中. 例如集合{0,2,3}可以用二进制\(1101_{2}\)表示; 反过来, 二进制数\(1101_{2}\)就对应着集合\({0,2,3}\).

正式地说, 包含非负整数的集合\(S\)可以用如下方式压缩成一个数字: $$ f(S) = \sum_{i\in S}2^i $$ 例如集合\({0,2,3}\)可以压缩成\(2^0 + 2^2 + 2^3 = 13\), 也就是二进制数\(1101_{2}\).

利用位运算并行计算的特点, 我们可以高效地做一些和集合有关的运算. 按照常见的应用场景, 可以分为以下四类:

  1. 集合与集合
  2. 集合与元素
  3. 遍历集合
  4. 枚举集合

一、集合月集合

其中&表示按位与, | 表示按位或, \(\oplus\) 表示按位异或, ~ 表示按位取反.

两个集合的对称差是只属于其中一个集合, 而不属于另一个集合的元素组成的集合, 也就是不在交集中的元素组成的集合.

术语 集合 位运算 集合示例 位运算示例
交集 \(A\cap B\) \(a\&b\) \(\{0,2,3\} \cap \{0,1,3\} = \{0, 2\}\) \(1101 \& 0111 = 0101\)
并集 \(A\cup B\) $a b$ \(\{0,2,3\} \cup \{0,1,2\} = \{0,1,2,3\}\)
对称差 \(A \Delta B\) \(a \oplus b\) \(\{0,2,3\} \Delta \{0,1,2\} = \{1,3\}\) \(1101 \oplus 0111 = 1010\)
差 \(A \setminus B\) \(a \& \sim b\) \(\{0,2,3\} \setminus \{1,2\} = \{0,3\}\) \(1101 \&\sim 1001 = 0100\)
差(子集) \(A \setminus B, B\subseteq A\) \(a\)
包含于 \(A \subseteq B\) $a \& b = a \ a b = b $ \(\{0, 2\} \subseteq \{0,2,3\}\)

~: ~1100 = 0011

&: 0110&1100 = 0100

|: 0110|1100 = 1110

^: 0110^1100 = 1010

二 集合与元素

通常会用到移位运算

<< 左移, 左移i位相当于乘以\(2^i\)

>> 右移, 右移i位相当于除以\(2^i\)

5 << 1 = 10
// Binary: 0101 << 1 = 1010

5 >> 1 = 2
// Binary: 0101 >> 1 = 0010

遍历集合

设元素范围从 0 到 n-1，枚举范围中的元素i，判断 i 是否在集合 s 中

for (int i = 0; i < n; i++){
  if ((s >> i) & 1 ) == 1){ // i在s中
    // 处理i的逻辑
  }
}

也可以直接遍历集合s 中的元素：不断地计算集合最小元素、去掉最小元素，直到集合为空。

for (int t = s; t > 0; t &= t - 1) {
    int i = Integer.numberOfTrailingZeros(t);
    // 处理 i 的逻辑
}

https://leetcode.cn/circle/discuss/CaOJ45/