2012-01-28-bitwise-operation-set-operation.md

layout	title	date	tags
post	位元運算 - 集合操作	2012-01-28	bitwise operation | 位元運算 C/C++

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

空集合 ∅

0

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

第 i 個元素

1 << i

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

宇集合 U

(1 << n) - 1

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

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

(1 << i) & S

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

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

S | (1 << i)

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

從集合 S 中取出 i 元素

S & ~(1 << i)

or

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

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

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

T & S == T

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

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

S | T

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

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

S & T

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

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

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

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

列舉集合 S 的所有子集合

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 的子集合

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 運算結果即為下一個排列