Bitmask Enumeration — Loop All Submasks

For a universe mask U, iterate s = U; s = (s - 1) & U to visit all non-empty submasks of U.

Try this in Python

U = 0b1011
s = U
while s:
    print(bin(s))
    s = (s - 1) & U

Key takeaways

• Classic trick for subset DP over a fixed universe.
• Empty subset needs separate handling if required.
• Complexity is O(3^n) over all masks in worst analyses—know context.