AntInLoop

Bitmasking & Submask Enumeration

Bitmasking packs subsets of up to 64 elements into a single integer so set union, intersection, difference, and submask enumeration run in O(1) bitwise instructions.

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

Bitmasking & Submask Enumeration

Bitmasking encodes a subset $S \subseteq \{0, 1, \dots, n-1\}$ as a single integer where bit i is 1 iff $i \in S$. Set union (a | b), intersection (a & b), difference (a & ~b), and symmetric difference (a ^ b) all run in $O(1)$ CPU time—and iterating over all submasks of all masks runs in exact $O(3^n)$ total time!

At a Glance

| Set Operation | Bitmask Expression |

| :--- | :--- |

| Union $A \cup B$ | a \| b |

| Intersection $A \cap B$ | a & b |

| Difference $A \setminus B$ | a & ~b |

| Subset test $A \subseteq B$ | (a & b) == a |

| Iterate all non-empty submasks of m | for (int s = m; s > 0; s = (s - 1) & m) |

---

Practice Problems

Intermediate

1. Enumerate All Submasks of a Mask (s = (s - 1) & mask)

Visit every non-empty submask of a bitmask in decreasing order without checking invalid bits.

Approach: (s - 1) & mask jumps directly to the next valid submask in $O(1)$ per submask! Across all $2^n$ masks, total iterations equal $\sum \binom{n}{k} 2^k = 3^n$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <vector>

std::vector<int> listSubmasks(int mask) {
    std::vector<int> subs;
    for (int s = mask; s > 0; s = (s - 1) & mask) subs.push_back(s);
    return subs;
}

int main() {
    // mask = 0b1011 (11) -> 11, 10, 9, 8, 3, 2, 1 (7 non-empty submasks)
    for (int s : listSubmasks(0b1011)) std::cout << s << " ";
    std::cout << "\n";
    return 0;
}

</details>

---

Related Algorithms