二進制集合操作

一個數的二進制表示可以看作是一個集合（\(0\) 表示不在集合中，\(1\) 表示在集合中）。比如集合 \(\{1,3,4,8\}\)，可以表示成 \((100011010)_2\)。而對應的位運算也就可以看作是對集合進行的操作。

在進一步介紹集合的子集遍歷操作之前，先看位運算的有關應用例子。

一個數對 \(2\) 的非負整數次冪取模，等價於取二進制下一個數的後若干位，等價於和 \(mod-1\) 進行與操作。

C++Python

int modPowerOfTwo(int x, int mod) { return x & (mod - 1); }

def modPowerOfTwo(x, mod):
    return x & (mod - 1)

於是可以知道，\(2\) 的非負整數次冪對它本身取模，結果為 \(0\)，即如果 \(n\) 是 \(2\) 的非負整數次冪，\(n\) 和 \(n-1\) 的與操作結果為 \(0\)。

事實上，對於一個正整數 \(n\)，\(n-1\) 會將 \(n\) 的最低 \(1\) 位置零，並將後續位數全部置 \(1\)。因此，\(n\) 和 \(n-1\) 的與操作等價於刪掉 \(n\) 的最低 \(1\) 位。

藉此可以判斷一個數是不是 \(2\) 的非負整數次冪。當且僅當 \(n\) 的二進制表示只有一個 \(1\) 時，\(n\) 為 \(2\) 的非負整數次冪。

C++Python

bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }

def isPowerOfTwo(n):
    return n > 0 and (n & (n - 1)) == 0

遍歷一個二進制數表示的集合的全部子集，等價於枚舉二進制數對應掩碼的所有子掩碼。

掩碼是一串二進制碼，用於和源碼進行與運算，得到屏蔽源碼的若干輸入位後的新操作數。

掩碼對於源碼可以起到遮罩的作用，掩碼中的 \(1\) 位意味着源碼的相應位得到保留，掩碼中的 \(0\) 位意味着源碼的相應位進行置 \(0\) 操作。將掩碼的若干 \(1\) 位改為 \(0\) 位可以得到掩碼的子掩碼，掩碼本身也是自己的子掩碼。

給定一個掩碼 \(m\)，希望有效迭代 \(m\) 的所有子掩碼 \(s\)，可以考慮基於位運算技巧的實現。

// 降序遍歷 m 的非空子集
int s = m;
while (s > 0) {
  // s 是 m 的一個非空子集
  s = (s - 1) & m;
}

或者使用更緊湊的 for 語句：

// 降序遍歷 m 的非空子集
for (int s = m; s; s = (s - 1) & m)
// s 是 m 的一個非空子集

這兩段代碼都不會處理等於 \(0\) 的子掩碼，要想處理等於 \(0\) 的子掩碼可以使用其他辦法，例如：

// 降序遍歷 m 的子集
for (int s = m;; s = (s - 1) & m) {
  // s 是 m 的一個子集
  if (s == 0) break;
}

接下來證明，上面的代碼訪問了所有 \(m\) 的子掩碼，沒有重複，並且按降序排列。

假設有一個當前位掩碼 \(s\)，並且想繼續訪問下一個位掩碼。在掩碼 \(s\) 中減去 \(1\)，等價於刪除掩碼 \(s\) 中最右邊的設置位，並將其右邊的所有位變為 \(1\)。

為了使 \(s-1\) 變為新的子掩碼，需要刪除掩碼 \(m\) 中未包含的所有額外的 \(1\) 位，可以使用位運算 \((s-1)\&m\) 來進行此移除。

這兩步操作等價於切割掩碼 \(s-1\)，以確定算術上可以取到的最大值，即按降序排列的 \(s\) 之後的下一個子掩碼。

因此，該算法按降序生成該掩碼的所有子掩碼，每次迭代僅執行兩個操作。

特殊情況是 \(s=0\)。在執行 \(s-1\) 之後得到 \(-1\)，其中所有位都為 \(1\)。在 \((s-1)\&m\) 操作之後將得到新的 \(s\) 等於 \(m\)。因此，如果循環不以 \(s=0\) 結束，算法的循環將無法終止。

使用 \(\text{popcount}(m)\) 表示 \(m\) 二進制中 \(1\) 的個數，用這種方法可以在 \(O(2^{\text{popcount}(m)})\) 的時間複雜度內遍歷集合 \(m\) 的子集。

在使用掩碼動態編程的問題中，有時會希望對於每個掩碼，遍歷掩碼的所有子掩碼：

for (int m = 0; m < (1 << n); ++m)
  // 降序遍歷 m 的非空子集
  for (int s = m; s; s = (s - 1) & m)
// s 是 m 的一個非空子集

這樣做可以遍歷大小為 \(n\) 的集合的每個子集的子集。

接下來證明，該操作的時間複雜度為 \(O(3^n)\)，\(n\) 為掩碼總共的位數，即集合中元素的總數。

考慮第 \(i\) 位，即集合中第 \(i\) 個元素，有三種情況：

總共有 \(n\) 位，因此有 \(3^n\) 個不同的組合。

還有一種證明方法是：

如果掩碼 \(m\) 具有 \(k\) 個 \(1\)，那麼它有 \(2^k\) 個子掩碼。對於給定的 \(k\)，對應有 \(\dbinom{n}{k}\) 個掩碼 \(m\)，那麼所有掩碼的總數為：

\[ \sum_{k=0}^n \dbinom{n}{k} 2^n \]

上面的和等於使用二項式定理對 \((1+2)^n\) 的展開，因此有 \(3^n\) 個不同的組合。

本頁面主要譯自博文 Перебор всех подмасок данной маски 與其英文翻譯版 Submask Enumeration。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用