A bitmask uses the individual bits of an integer to represent a set of true-or-false flags, one bit per flag. Instead of an array of booleans, you get a single number, and instead of looping to check or combine flags, you get one bitwise instruction. It looks like a micro-optimization the first time you see it, but it is really a different way of representing a set entirely.
What changed in 2026
- Bitmask DP remains a standard competitive-programming and interview tool for small-n subset problems (roughly n ≤ 20-22), and that has not changed — the state space is still 2^n either way.
- Feature-flag systems still use bitmasks under the hood in performance-sensitive paths, even as most application-level flag tooling has moved to config services for anything user-facing.
- Linters and static analysis catch more bitmask misuse than before, flagging fixed-width overflow and unparenthesized combinations of bitwise and comparison operators automatically.
The core idea: one integer, many flags
Each bit position is an independent flag. Bit 0 might mean read, bit 1 write, bit 2 execute — and any combination of them is just one integer.
FLAG_READ = 1 << 0 # 0b0001
FLAG_WRITE = 1 << 1 # 0b0010
FLAG_EXEC = 1 << 2 # 0b0100
perms = FLAG_READ | FLAG_WRITE # set: turn on READ and WRITE
perms |= FLAG_EXEC # set: turn on EXEC too
perms &= ~FLAG_WRITE # clear: turn off WRITE
perms ^= FLAG_EXEC # toggle: flip EXEC
has_read = bool(perms & FLAG_READ) # check: is READ on?
Where bitmasks show up
| Use case |
What each bit means |
| File permissions |
Read, write, execute for owner, group, other |
| Feature flags |
One bit per toggle, packed into a single config integer |
| Subset DP (routing, assignment problems) |
Bit i = whether item or location i has been used |
| Visited-state in graph search |
Bit i = whether node i has been visited on this path |
| Game boards (bitboards) |
One bit per square, one integer per piece type |
Combined with a sliding window or a two-pointer scan, a bitmask can track which characters currently sit inside a window using O(1) set operations instead of a hash set — a common trick behind "longest substring without repeating characters" style problems over a small, fixed alphabet.
Bitmask DP, briefly
A classic use: shortest-path-visiting-every-city problems, where dp[mask][i] means the shortest path visiting exactly the cities in mask, ending at city i.
n = len(cities)
dp = [[float("inf")] * n for _ in range(1 << n)]
dp[1][0] = 0 # start at city 0
for mask in range(1 << n):
for i in range(n):
if mask & (1 << i) == 0 or dp[mask][i] == float("inf"):
continue
for j in range(n):
if mask & (1 << j):
continue # already visited
new_mask = mask | (1 << j)
dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + dist[i][j])
Common pitfalls
Exceeding native integer width. Python integers grow automatically; C, Java, and Go do not — past 32 or 64 bits, values silently overflow unless the code switches to a bitset or an arbitrary-precision type.
Combining bitwise and comparison operators without parentheses. Bitwise operators bind tighter than comparisons in most languages, so a == 1 & b == 2 does not mean what it looks like. Always write (a == 1) & (b == 2).
Forgetting to unset a bit when backtracking. In DFS or backtracking over a mask, leaving a bit set after a branch finishes pollutes sibling branches with a phantom visited flag.
Reaching for a bitmask when the universe of items is large or unbounded. Past roughly 64 flags on a fixed-width integer, a hash set or a proper bitset type is the correct tool.
FAQ
Is bitmask the same as bit mask, written as two words?
Yes — same concept, just a spelling preference. Both mean using the bits of an integer to represent a set of flags.
Why not just use a boolean array instead?
For small, fixed-size sets, a bitmask is smaller and turns union, intersection, and membership checks into single instructions instead of loops.
What happens if more than 64 flags are needed?
Use a language arbitrary-precision integer type (Python handles this automatically) or an explicit bitset class — native fixed-width integers overflow or truncate silently.
Is bitmask DP always the right approach for subset problems?
Only when the number of items is small, roughly up to 20-22, since the state space is 2^n. Beyond that, the memory and time requirements stop being practical.
Where to go next