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
- Bitmask DP — dynamic programming over bitmask states.
- Bitwise Operations — core bit primitives.