What is Submask Bitwise Iteration?

Submask Bitwise Iteration is an advanced bit manipulation hack that allows us to iterate through all submasks of a given bitmask $M$ in $O(1)$ time per submask. When applied to all masks of size $N$, this reduces the complexity of subset-iteration algorithms from a naive $O(4^N)$ to an optimized $O(3^N)$.

Explanation

The Problem

• Given a bitmask $M$, we want to find all submasks $S$ such that $S$ is a subset of $M$.
• Mathematically, $S$ is a submask of $M$ if and only if:
• $(S\&M)==S$
• This means $S$ can only have set bits ($1$s) at positions where $M$ also has set bits.

The Naive Way

• To find all submasks of $M$, we could loop an integer $s$ from $M$ down to $0$, checking the subset condition for each one:

for (int s = M; s >= 0; s--) {
    if ((s & M) == s) {
        // s is a valid submask
    }
}

• If we do this for all masks from $0$ to $2^N-1$, the total iterations would be $2^N\times 2^N=O(4^N)$, which is highly inefficient for $N>15$.

The Hacky Way

• We can skip all invalid masks directly in $O(1)$ using the following bitwise decrement and mask formula:

for (int s = M; s > 0; s = (s - 1) & M) {
    // s is a valid submask (excluding 0)
}

• Subtracting $1$ from $s$ flips the rightmost set bit to $0$ and turns all trailing zeros to $1$s.
• Performing a bitwise AND with $M$ (& M) then instantly discards any bits that were not set in the original mask $M$, snapping $s$ to the next valid submask.

Mathematical Proof of $O(3^N)$ Complexity

• Why does this optimization reduce the total complexity of iterating submasks of all masks from $O(4^N)$ to $O(3^N)$?
• Let $N$ be the number of bits.
• 1. A mask with exactly $k$ set bits has $2^k$ submasks.
• 2. The number of masks of length $N$ with exactly $k$ set bits is given by the binomial coefficient: $\left(\genfrac{}{}{0ex}{}{N}{k}\right)$
• 3. To find the total number of submask iterations across all possible masks, we sum this product over all $k$ from $0$ to $N$: $\text{Total Iterations}={\sum }_{k=0}^N\left(\genfrac{}{}{0ex}{}{N}{k}\right)2^k$
• 4. Applying the Binomial Theorem: $(x+y{)}^N={\sum }_{k=0}^N(\genfrac{}{}{0ex}{}{N}{k})x^k{y}^{N-k}$
• 5. Substituting $x=2$ and $y=1$: $(2+1{)}^N={\sum }_{k=0}^N(\genfrac{}{}{0ex}{}{N}{k})2^k(1{)}^{N-k}={\sum }_{k=0}^N\left(\genfrac{}{}{0ex}{}{N}{k}\right)2^k$
• 6. Therefore: $\text{Total Iterations}=3^N$
• This is a massive improvement. For $N=20$:
  • $4^{20}\approx 1.1\times 10^{12}$ operations (takes several minutes, TLE).
  • $3^{20}\approx 3.48\times 10^9$ operations (takes a few seconds).

Step-by-Step Trace ($M=13$)

• Let $M=13$ ($1101_2$ in binary). Let’s trace the values generated by $s\leftarrow (s-1)\&M$:

• Submasks found: 13 ($1101_2$), 12 ($1100_2$), 9 ($1001_2$), 8 ($1000_2$), 5 ($0101_2$), 4 ($0100_2$), 1 ($0001_2$), and implicitly 0 ($0000_2$).

Application: Subset Dynamic Programming

• Consider the problem of partitioning $N$ items into groups, where each subset $S$ has a known cost $cost[S]$, and we want to find the minimum cost to cover all items.
• Let $dp[mask]$ be the minimum cost to cover the subset represented by $mask$.
• The recurrence relation is:
• $dp[mask]={\min }_{submask\subset mask}(dp[submask]+cost[mask\setminus submask])$
• Using the submask iteration trick, we can solve this in $O(3^N)$ time.

Implementation

• Below are the implementations showing how to iterate submasks of a given mask, and how to execute the $O(3^N)$ subset DP transition. Languages: Python · Cpp · Java Script · Java

​

# 1. Iterate submasks of a single mask
def get_submasks(mask):
    submasks = []
    s = mask
    while s > 0:
        submasks.append(s)
        s = (s - 1) & mask
    submasks.append(0)  # Add the empty set
    return submasks
 
# 2. Iterate all submasks for all masks up to N (O(3^N))
def iterate_all(n):
    total_iterations = 0
    for mask in range(1 << n):
        s = mask
        while s > 0:
            total_iterations += 1
            s = (s - 1) & mask
        total_iterations += 1  # For s = 0
    return total_iterations
 
# Example
print("Submasks of 13:", get_submasks(13))
print("Total iterations for N=5 (3^5 = 243):", iterate_all(5))

#include <iostream>
#include <vector>
 
// 1. Iterate submasks of a single mask
std::vector<int> get_submasks(int mask) {
    std::vector<int> submasks;
    for (int s = mask; s > 0; s = (s - 1) & mask) {
        submasks.push_back(s);
    }
    submasks.push_back(0); // Empty set
    return submasks;
}
 
// 2. Sample O(3^N) DP skeleton
void subset_dp(int n, const std::vector<int>& cost) {
    std::vector<int> dp(1 << n, 1e9);
    dp[0] = 0;
 
    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int s = mask; s > 0; s = (s - 1) & mask) {
            dp[mask] = std::min(dp[mask], dp[s] + cost[mask ^ s]);
        }
    }
}
 
int main() {
    auto subs = get_submasks(13);
    std::cout << "Submasks of 13:\n";
    for (int x : subs) std::cout << x << " ";
    std::cout << "\n";
    return 0;
}

// 1. Iterate submasks of a single mask
function getSubmasks(mask) {
    const submasks = [];
    let s = mask;
    while (s > 0) {
        submasks.push(s);
        s = (s - 1) & mask;
    }
    submasks.push(0);
    return submasks;
}
 
// Example
console.log("Submasks of 13:", getSubmasks(13));

import java.util.*;
 
public class SubmaskIteration {
    
    // 1. Get all submasks of a single mask
    public static List<Integer> getSubmasks(int mask) {
        List<Integer> submasks = new ArrayList<>();
        for (int s = mask; s > 0; s = (s - 1) & mask) {
            submasks.add(s);
        }
        submasks.add(0);
        return submasks;
    }
 
    public static void main(String[] args) {
        System.out.println("Submasks of 13: " + getSubmasks(13));
    }
}

​

Key Takeaways

• Decrement-AND Operation — The bitwise formula s = (s - 1) & mask decrements the current submask and crops it to the mask, jumping to the next valid submask in $O(1)$.
• O(3^N) Bound — Proven by the binomial theorem, this optimization enables subset-based DP solutions to scale to $N\le 22$ (compared to $N\le 15$ for $O(4^N)$).

More Learn

Resources

• CP-Algorithms – Submask Iteration

Related Pages

• Bitwise Hacks – General bitwise manipulation shortcuts
• Gospers Hack – Generating combinations of fixed bits
• Linear Basis Algorithm – XOR vector basis algorithms
• DSA Algo & System Design – Master DSA list