集合的狀態非常單純,非無即有,非有即無。因此就像位元的 0 與 1 一樣,僅有兩種狀態。不僅僅是集合,只要狀態僅有兩種時,皆可考慮使用位元來做資料結構。以位元來做資料結構,不僅狀態可以很明確的以 0 與 1 表示外,在操作時也可提昇程式的效率。

空集合 ∅

1
0

空集合以位元表示即為 000…00,因此使用整數 0 即可用來作為空集合。

第 i 個元素

1
1 << i

第 i 個元素即為 00100…0,該位元 1 為右邊數過去第 i 個位元。因此可以使用 1 << i 來表示第 i 個元素。

宇集合 U

1
(1 << n) - 1

一個所有元素都存在的集合其位元表示即為 111…11 共 n 個位元 1。利用之前的文章提過取 n 個位元 1 的方法即可。

判斷第 i 個元素是否存在於集合 S 中

1
(1 << i) & S

前面提過第 i 個元素的為 1 << i,因此透過 and 運算即可判斷第 i 個元素是否存在於 S 中。

在集合 S 內加入第 i 個元素

1
S | (1 << i)

如同將第 i 個位元設定為位元 1 一般,因此採用之前的文章中將指定位元設定為位元 1 的方法即可。

從集合 S 中取出 i 元素

1
S & ~(1 << i)

or

1
~((~S) | (1 << i)

如同將第 i 個位元設定為位元 0 一般,因此採用之前的文章中將指定位元設定為位元 0 的方法即可。

判斷集合 T 是否為集合 S 之子集合

1
T & S == T

若集合 T 為集合 S 的子集合,在經過 and 運算後,將不會少去任何 1 位元。因此經過 and 運算後,T 將不會有任何變動。但若集合 T 不為集合 S 的子集合,經過 and 運算後,T 將會少去部份的 1 位元,由於 S 並沒有該元素,其該位元將會為 0,所以經過 and 運算後,T 的該位元將會為 0,使其不再等於 T。

集合 S 與集合 T 的聯集 S ∪ T

1
S | T

利用 or 運算,即可很容易將兩集合共有的元素保留,並加入兩集合的差集。

集合 S 與集合 T 的交集 S ∩ T

1
S & T

利用 and 運算,將可保有兩集合共有的元素。

列舉有 n 個元素的宇集合 U 所有子集合

1
2
3
for (int i = 0; i < (1 << n); ++i) {
    // proccess
}

U 以位元儲存為 111…11 共 n 個 1,其子集合即為 1 ~ 2n-1 之間的所有整數的位元表示。因此使用迴圈從 0 開始枚舉至 2n-1 即可列舉出所有狀態。

列舉集合 S 的所有子集合

1
2
3
4
5
int temp = S;
do {
    // proccess
    temp = (temp - 1) & S;
} while (temp != S);

一樣可以從 0 開始枚舉所有宇集的所有子集,再利用判斷子集合的方式確定,但該方法可能會枚舉過多次的非子集合。因此採用另一個方法,從 S 開始減去 1 並將得到的數字與 S 在做一次 and 運算,即可保證每次產生的結果都為 S 的子集合。該方法即可省去許多冤枉的枚舉,但要注意的是,可能會出現重複的子集合

值得注意的是退出的條件,最後一個子集合必為 0,也就是空集合。0 減去 1 將會變成 -1,-1 的位元表示為所有位元都為 1,因此與 S 進行 and 運算後會等於 S。所以當 temp 等於 S 時,就是枚舉結束的時候,也是採用 do-while 的原因。

列舉有 n 個元素的宇集合 U 中所有大小為 k 的子集合

1
2
3
4
5
6
7
8
9
int temp = (1 << k) - 1;
while (temp < (1 << n)) {
    // proccess
    int last_1 = temp & -temp;
    int carry = temp + last_1;
    int cont_bits = temp & (~carry);
    int trail = (cont_bit / last_1) >> 1;
    temp = carry | trail;
}

(1 « k) - 1 為所有子集合中最小的,因此將其設定為初始值,以升冪的順序來枚舉。枚舉下一個排列的方法是,將最低位連續 k 個 1 位元加上 1 使其進位。再使最後的 k - 1 位元設定為 1,如此集合內的數量也不會改變,並得到下一個排列方式。

以下為枚舉下一個排列的方法:

  1. 找出當前值 temp 的最低 1 位元
  2. 令 carry 等於 temp 加上最低 1 位元,此時最低位連續 1 位元將會進位
  3. 透過 temp 與 carry 取 not 後的值進行 and 運算,則可以得到最低位連續 1 位元
  4. 再將該最低位連續 1 位元除以最低位 1 位元,此時該連續 k 個 1 位元會置右,再將其進行右移運算,則可得到置右的 k - 1 個連續 1 位元 trail
  5. 最後,carry 與 trail 的 or 運算結果即為下一個排列