Bitwise Set Operations

Prerequisites: bitwise operations and integers and bit sequences.

The binary representation of a number can be viewed as a set, where $0$ means that an element is absent from the set and $1$ means that it is present. For example, the set $\{1,3,4,8\}$ can be represented as $(100011010)_2$. The corresponding bitwise operations can then be viewed as operations on sets.

Before introducing operations for enumerating subsets of a set, let us first look at some applications of bitwise operations.

Powers of 2 modulo

Taking a number modulo a nonnegative power of $2$ is equivalent to taking its last several bits in binary, and is equivalent to applying AND with $mod-1$.

C++

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

Python

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

It follows that taking a nonnegative power of $2$ modulo itself gives $0$; in other words, if $n$ is a nonnegative power of $2$, the result of ANDing $n$ with $n-1$ is $0$.

In fact, for a positive integer $n$, $n-1$ clears the lowest position of $n$ that contains $1$, and changes all following bits to $1$. Therefore, ANDing $n$ with $n-1$ is equivalent to removing the lowest position of $n$ that contains $1$.

This can be used to determine whether a number is a nonnegative power of $2$. If a number $n$ has exactly one $1$ in its binary representation, then $n$ is a nonnegative power of $2$.

C++

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

Python

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

Subset enumeration

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

A mask is a string of binary digits used in an AND operation with a source operand to obtain a new operand after masking out some input bits of the source.

A $1$ bit in the mask means that the corresponding bit of the source is retained, while a $0$ bit means that the corresponding bit of the source is set to $0$. Changing some of the mask's $1$ bits to $0$ gives a submask of the mask; the mask itself is also its own submask.

Given a mask $m$, to iterate efficiently over all submasks of $m$, denoted $s$, one can use the following bitwise technique:

// enumerate the 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 use the more compact for statement:

// enumerate the 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

Neither of these code snippets processes the submask equal to $0$. To process the submask equal to $0$, another method can be used, for example:

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

We next prove that the code above visits every submask of $m$ without repetition and in descending order.

Suppose the current bitmask is $s$ and we want to visit the next bitmask. In mask $s$, subtracting $1$ is equivalent to removing the rightmost set bit of $s$ and changing all bits to its right to $1$.

For $s-1$ to become a new submask, all extra bits not contained in mask $m$ must be removed. These extra $1$ bits can be removed with the bitwise operation (s - 1) & m.

These two operations are equivalent to cutting down $s-1$ to determine the largest value available in arithmetic order, namely the next submask after $s$ in descending order.

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

The special case is $s=0$. After executing $s-1$, we obtain $-1$, whose bits are all $1$. After the operation (s - 1) & m, the new $s$ is equal to $m$. Therefore, if the loop does not terminate at $s=0$, it cannot terminate at all.

Using $\text{popcount}(m)$ to denote $m$'s binary count of $1$ bits, this method enumerates the subsets in $O(2^{\text{popcount}(m)})$ time over $m$.

Enumerating submasks of all masks

In problems using subset DP, it is sometimes useful to enumerate all submasks of every mask:

for (int m = 0; m < (1 << n); ++m)
  // enumerate the 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 enumerates every subset of every subset of a set of size $n$.

We next prove that this operation has time complexity $O(3^n)$, where $n$ is the total number of bits in the mask, or equivalently the number of elements in the set.

Consider bit $i$, the $i$-th element of the set. There are three possibilities:

• In mask $m$ it is $0$, and therefore in submask $s$ it is $0$; the element is in neither the larger nor the smaller subset.
• In $m$ it is $1$, but in $s$ it is $0$; the element is only in the larger subset and not in the smaller subset.
• In both $m$ and $s$ it is $1$; the element is in both subsets.

There are $n$ bits in total, so there are $3^n$ different combinations.

Another proof is as follows.

If mask $m$ has $k$ $1$s, then it has $2^k$ submasks. For a given $k$, there are $\dbinom{n}{k}$ possible masks $m$, so the total number of masks is

$$\sum_{k=0}^n \dbinom{n}{k} 2^k$$

The sum above is the expansion of $(1+2)^n$ by the binomial theorem, so there are $3^n$ different 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.

Problems

• Atcoder - Close Group
• Codeforces - Nuclear Fusion
• Codeforces - Sandy and Nuts
• UVa 1439 - Exclusive Access 2
• UVa 11825 - Hackers' Crackdown