Binary Set Operations

The binary representation of a number can be viewed as a set (where \(0\) indicates absence from the set, and \(1\) indicates presence). For example, the set \(\{1,3,4,8\}\) can be represented as \((100011010)_2\). Correspondingly, bitwise operations can be seen as operations on sets.

Operation	Set Notation	Bitwise Operation
Intersection	\(a \cap b\)	`a & b`
Union	\(a \cup b\)	`a \| b`
Complement	\(\bar{a}\)	`~a` (where the universal set is all bits 1)
Difference	\(a \setminus b\)	`a & (~b)`
Symmetric Difference	\(a\triangle b\)	`a ^ b`

Before further introducing subset traversal operations for sets, let's first look at some application examples of bitwise operations.

Modulo Power of Two

Taking a number modulo a non-negative integer power of \(2\) is equivalent to taking the lower bits of its binary representation, which is equivalent to performing an AND operation with \(mod-1\).

C++Python

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

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

Thus, we know that a non-negative integer power of \(2\) modulo itself yields \(0\), i.e., if \(n\) is a non-negative integer power of \(2\), the AND operation of \(n\) and \(n-1\) results in \(0\).

In fact, for a positive integer \(n\), \(n-1\) will clear the lowest set bit of \(n\) and set all lower bits to \(1\). Therefore, the AND operation of \(n\) and \(n-1\) is equivalent to removing the lowest set bit of \(n\).

This can be used to determine whether a number is a non-negative integer power of \(2\). \(n\) is a non-negative integer power of \(2\) if and only if its binary representation contains exactly one \(1\).

C++Python

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

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

Subset Traversal

Traversing all subsets of a set represented by a binary number is equivalent to enumerating all submasks of the corresponding mask.

A mask is a binary string used in an AND operation with a source code to obtain a new operand that masks certain input bits of the source.

A mask acts as a cover for the source code: a \(1\) bit in the mask means the corresponding bit in the source is retained, while a \(0\) bit means the corresponding bit in the source is set to \(0\). Changing some \(1\) bits in the mask to \(0\) yields a submask of the mask; the mask itself is also its own submask.

Given a mask \(m\), to efficiently iterate over all its submasks \(s\), consider an implementation based on bit manipulation techniques.

// Traverse non-empty subsets of m in descending order
int s = m;
while (s > 0) {
  // s is a non-empty subset of m
  s = (s - 1) & m;
}

Or using a more compact for statement:

// Traverse non-empty subsets of m in descending order
for (int s = m; s; s = (s - 1) & m)
// s is a non-empty subset of m

These two code snippets do not handle the submask equal to \(0\). To handle the \(0\) submask, other methods can be used, for example:

// Traverse subsets of m in descending order
for (int s = m;; s = (s - 1) & m) {
  // s is a subset of m
  if (s == 0) break;
}

Next, we prove that the above code visits all submasks of \(m\), without repetition, and in descending order.

Assume we have a current mask \(s\) and want to visit the next mask. Subtracting \(1\) from mask \(s\) is equivalent to removing the rightmost set bit in \(s\) and setting all bits to its right to \(1\).

To turn \(s-1\) into a new submask, we need to remove all extra \(1\) bits not included in mask \(m\). This can be done using the bitwise operation \((s-1)\&m\).

These two steps are equivalent to truncating the mask \(s-1\) to determine the maximum value arithmetically possible, i.e., the next submask after \(s\) in descending order.

Therefore, this algorithm generates all submasks of the mask in descending order, performing only two operations per iteration.

A special case is \(s=0\). After performing \(s-1\), we get \(-1\), where all bits are \(1\). After the operation \((s-1)\&m\), we obtain a new \(s\) equal to \(m\). Thus, if the loop does not terminate at \(s=0\), the algorithm would loop indefinitely.

Let \(\text{popcount}(m)\) denote the number of \(1\) bits in the binary representation of \(m\). Using this method, we can traverse all subsets of set \(m\) in \(O(2^{\text{popcount}(m)})\) time complexity.

Traversing All Submasks for Every Mask

In problems using DP over subsets (bitmask DP), sometimes we want to traverse all submasks for each mask:

for (int m = 0; m < (1 << n); ++m)
  // Traverse non-empty subsets of m in descending order
  for (int s = m; s; s = (s - 1) & m)
// s is a non-empty subset of m

This traverses every subset of each subset of a set of size \(n\).

Next, we prove that the time complexity of this operation is \(O(3^n)\), where \(n\) is the total number of bits in the mask, i.e., the total number of elements in the set.

Consider the \(i\)-th bit, i.e., the \(i\)-th element of the set. There are three possibilities:

It is \(0\) in mask \(m\), hence \(0\) in submask \(s\), meaning the element is in neither the larger nor the smaller subset.
It is \(1\) in \(m\) but \(0\) in \(s\), meaning the element is only in the larger subset, not in the smaller one.
It is \(1\) in both \(m\) and \(s\), meaning the element is in both the larger and smaller subsets.

There are \(n\) bits in total, so there are \(3^n\) distinct combinations.

Another proof method is:

If mask \(m\) has \(k\) ones, then it has \(2^k\) submasks. For a given \(k\), there are \(\dbinom{n}{k}\) masks \(m\). Thus, the total number of all masks is:

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

The above sum equals the expansion of \((1+2)^n\) using the binomial theorem, resulting in \(3^n\) distinct combinations.

References

This page is mainly translated from the blog post Перебор всех подмасок данной маски and its English translation Submask Enumeration. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.

Exercises

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