集合論與位運算

# 集合論與位運算集合的概念在高中數學就接觸過，大學則學到了位元的四則運算(AND、OR、NOT、XOR等等)。集合論與位元運算，兩者看似毫不相關的東西，卻有著奇妙的數學關係聯繫著。 ## 集合轉換成位元表示集合由元素組成，例如 S = {1, 2, 3}。在程式領域遇到有關集合的題目，通常使用 hash table 紀錄一個集合裡面出現的元素。在集合論中，我們學到了聯集(∪)、交集(∩)以及其他等概念。若我們要找到兩個集合的交集，就要走遍每個 hash table 的元素。換個思維思考，若我們使用位元 0 代表數字沒有在集合中，位元 1 代表數字有在集合裡，那就可以使用位元表達一個集合。二進位由右至左第 i 個 bit 代表 i 是否在集合中。例如 S = {1, 2, 3} 就可用 1110 表示，反之亦然。另一個很有意思的點是，將上面集合 S 中的每個數字 i 視為 2 的 i 次方，則合為 $2^1 + 2^2 + 2^3$ = 13, 正好就是二進 1110 轉換為十進位的數字。 ## 集合運算在一些特定的情況下，若輸入的變數範圍較少，我們可以使用位元表達一個元素是否存在於集合中，將一個集合表達成一個二進位數字，就可使用位元運算取代集合運算。由於位元運算就是 CPU 內部最基本的四則運算，在特定場合下可以提升程式執行效率。我們可以將其應用場景分為以下四類: * 集合與集合 * 集合與元素 * 走訪整個集合 * 列出所有集合依據每個類別進行介紹 ## 集合-集合下表為集合與集合之間的位元運算關係，其中 ^ 代表 XOR、& 代表 AND、| 為 OR 而 ~ 為 NOT 運算。 | 術語 | 集合 | 位元運算 | 集合範例 | 位元運算範例 | |----------|-----------------|-----------|---------------------------------------------------|----------------------------| | 交集 | $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 \oplus b$ | {0, 2, 3} △ {0, 1, 2} = {1, 3} | 1101 ^ 0111 = 1010 | | 差集 | $A \setminus B$ | $a\ \& \ (∼b)$ | {0, 2, 3} \ {1, 2} = {0, 3} | 1101 & 1001 = 1001 | | | 包含於 | $A ⊆ B$ | $a\ \&\ b = a, a\ \|\ b = b$ | {0, 2} ⊆ {0, 2, 3} | 0101 & 1101 = 0101, 0101 \| 1101 = 1101 | 針對以上運算進行推理如下， A = {0, 2, 3}，二進表示法為 1101 B = {0, 2}，二進位表示法為 0101 ### 交集 A & B = 0101，根據第 i 個 bit 的值，判斷數字 i 是否有出現在集合中，得 0、2 為集合 A ∩ B。轉換為集合表示法為 A ∩ B = {0, 2} ### 聯集 A | B = 1101，聯集代表有出現在集合 A 或出現在集合 B 中。採用 OR 位元運算，只要有一個 bit 為 1，OR 運算後該 bit 的結果絕對為 1。得 A ∪ B = {0, 2, 3}。 ### 對稱差數學上，兩個集合的對稱差是只屬於其中一個集合，而不屬於另一個集合的元素組成的集合。以繁體中文公式表達為: 對稱差 = 聯集 − 交集以位元運算思考，上述中文意思在 a 與 b 的二進位中，同一個位置的 bit 不能有兩個 1，因此使用 XOR 運算就可處理，得: $a \oplus b$ ### 差集 A ∖ B 表示所有屬於集合 A 但不屬於集合 B 的元素組成的集合，也就是 A 與非 B 集合的交集。用公式可表達 A ∖ B = A - B，以位元運算來說，若 a 為 1101，b 為 0101，預期結果應為 1000。為了達到這個結果，需要將 b 中 bit 為 1 的地方轉為 0(移除屬於 B)，而 0 轉為 1(加入不屬於 B)，再將兩者取交集。轉換為位元運算，先對 b 做 NOT 運算(取反)，再進行 AND 運算(取交集)，得 A \ B = a & (~b) ### 包含於 A⊆B 代表 A 是 B 的一個子集合，任何出現在 A 的元素必出現在 B。A 與 B 的交集為 A 集合本身，A 與 B 的聯集為 B 集合。以二進位來看，第 i 個 bit 在 a 與 b 中皆為 1。由上述推論可得: a & b = a 且 a | b = b ## 集合-元素類別屬於一個集合中對單一元素的操作，常使用 << (左移) 與 >> (右移) 運算子 | 術語 | 集合 | 位元運算 | 集合範例 | 位元運算範例 | |--------------|---------------------------------|---------------------------|-----------------------------------|----------------------------------| | 空集合 | $∅$ | 0 | {} | 0 | | 單元素集合 | ${i}$ | $1 << i$ | {2} | $1 << 2$ | | 全集 | $$ U = \{ 0, 1, 2, \dots, n-1 \} $$ | $(1 << n) - 1$ |$\{ 0, 1, 2, 3 \}$ | $(1 << 4) - 1$ | 補集 | $$ A^C = U \setminus A $$ | $((1 << n) - 1) ⊕ s$ | $$ U = \{0, 1, 2, 3\} $, $ $A^C$\{1, 2\} = \{0, 3\} $$ | $1111 ⊕ 0110 = 1001$ | | 屬於 | $$ i \in S $$ | (s >> i) & 1 = 1 | 2 ∈ {0, 2, 3} | (1101 >> 2) & 1 = 1 | | 不屬於 | $$ i \notin S $$ | (s >> i) & 1 = 0 | 1 ∉ {0, 2, 3} | (1101 >> 1) & 1 = 0 | | 新增元素 | $$ S \cup \{i\} $$ | $s \ \|\ (1 << i)$ | $\{0, 3\} ∪ \{2\} = \{0, 2, 3\}$ | 1001 | (1 << 2) = 1101 | | 刪除元素 | $$ S \setminus \{ i \} $$ | $ s \& \sim (1 << i) $ | $ \{ 0, 2, 3 \} \setminus \{ 2 \} $ | $ 1101 \& \sim (1 << 2) $ | | 刪除元素 (一定在集合中) | $$ S \setminus \{ i \}, \ i \in S $$ | $ s \oplus (1 << i) $ | $ \{ 0, 2, 3 \} \setminus \{ 2 \} $ | $ 1101 \oplus (1 << 2) $ | | 刪除最小元素 | | $$ s \ \&\ (s - 1) $$ | | | ### 單元素集合集合只有單一元素，方法類似 set bit。 1 << i ### 全集合給定的範圍內所有數字皆位於集合內，所以 bits 皆為 1，得 (1 << (n + 1)) - 1 ### 補集 ### 是否屬於集合若數字 i 數於集合，則第 i 個 bit 為 1，反之為 0，得: (1 << i) & 1 = 1(屬於) (1 << i) & 1 = 0(不屬於) ### 新增元素新增數字 i 到集合中，等價於將二進位的第 i 個 bit 設為 1，也就是 set bits。 s | (1 << i) ### 移除元素將數字 i 從集合移除，等價於將二進位的第 i 個 bit 設為 0，也就是 clear bits。 s & ~(1 << i) ### 移除最小元素最小元素，代表二進位由低到高位元數來第一個非 0 bit，將其設為 0，得 s = 101100 s - 1 = 101011 s & (s - 1) = 101000 ## 走訪整個集合元素範圍從 0 到 n - 1，判斷 i 是否在集合 s 中。 ```cpp! for(int i = 0; i < n;i ++){ if((1 << i) & 1){ // i 在 s 中 } } ``` 也可以 ## 列出所有集合元素範圍從 0 到 n - 1，列出所有集合，從空集合到全集 U ```cpp! for(int s = 0; s | (1 << n); s++){ // 處理 } ``` ### ## Ref 本文資訊來自以下文章的理解 [從集合論到位運算，常見位元運算技巧分類總結!](https://leetcode.cn/circle/discuss/CaOJ45/)