BitsAlgorithmaka bitmask, bitset, flags

Bit Masks

Represent a set of up to 64 booleans as one integer so that set operations become single bitwise instructions.

▶ Visualize Pattern: Bit Manipulation Practice (3)

Progress

Overview

A bit mask is an integer whose bits are read as membership flags: bit i set means "element i is in the set". With this encoding, union is a | b, intersection is a & b, difference is a & ~b, symmetric difference is a ^ b, membership is (a >> i) & 1, and the empty set is 0. All are constant-time.

Masks are also used to select fields: x & 0xFF keeps the low byte, (x >> 8) & 0xF extracts a 4-bit field at offset 8, and x & ~0xFF clears the low byte. Network protocols, file permissions (rwx = 7) and CPU flags all work this way.

In algorithm design, masks compress a state such as "which cities have been visited" into a single array index. That is the basis of Bitmask DP (traveling salesman in O(2^n · n^2)) and of BFS over states in problems like shortest path visiting all nodes.

bitmaskset representationflagsO(1) unionstate compression

Intuition

A mental model before the formal terms.

Think of a row of n light switches on a wall panel. Instead of listing which switches are on, photograph the panel: the photo *is* the set. Combining two panels with OR turns on every switch that is on in either photo; AND keeps only the switches on in both. Because the panel has at most 64 switches it fits in one machine word, and the CPU compares whole panels in one step.

How it works

Choose an index 0..n-1 for each element. The mask for {0, 2, 3} is 1<<0 | 1<<2 | 1<<3 = 0b1101 = 13.
Build masks with 1 << i; combine with |; test with mask & (1 << i); remove with mask & ~(1 << i).
The full set is (1 << n) - 1, all n low bits on. Complement within the universe is full ^ mask.
Cardinality is the number of set bits — see Count Set Bits (Popcount). Iterating the members means iterating set bits, cheapest via low = mask & -mask then mask ^= low.
To use a mask as a DP state, index a table of size 2^n by the mask; transitions add one element with mask | (1 << i).

Why it works

Because each bit is independent, each bitwise operator applied to two masks performs the corresponding boolean operation on every element simultaneously. | is "or" per element, so it is set union; & is "and", so it is intersection.

A fixed-width word holds w bits, so any set over a universe of size ≤ w is one word. Operations that would take O(n) on a boolean array take O(1) — or O(n / w) for bitsets larger than a word.

Recognition

How to tell a problem wants this.

A universe of at most ~20 elements combined with "every subset", "visited set", or "assignment" — an exponential state space that a mask can index.
Words like "flags", "permissions", "toggle features", or "which of these k conditions hold".
A problem that asks whether two words share a letter, or which letters appear in a string over a 26-letter alphabet.

“parity/odd occurrences” → Bit Manipulation

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Set, Clear, Toggle & Test a Bit visualization.

n | k — Integer 0..255, then a pipe, then the bit index 0..7 — e.g. "44 | 1"

= 44

1/7n = 44 (00101100). We want to manipulate bit k=1, which currently is 0.

Bit kBit set to 1Bit cleared to 0

PseudocodeLearn Set, Clear, Toggle & Test a Bit →

1mask = 1 << k
2set    = n | mask
3clear  = n & ~mask
4toggle = n ^ mask
5test   = (n >> k) & 1

Variables

n44

Complexity

best O(1)

avg O(1)

worst O(1)

space O(1)

Speed

Pseudocode

1EMPTY = 0, FULL = (1 << n) - 1
2add(S, i):      S | (1 << i)
3remove(S, i):   S & ~(1 << i)
4has(S, i):      (S >> i) & 1
5union(A, B):    A | B
6intersect(A,B): A & B
7diff(A, B):     A & ~B
8size(S):        popcount(S)

Implementations

11 · Bitset over {0..n-1} in one integer
2class BitSet:
3    """Set over the universe {0, ..., n-1} stored in one int (unbounded in Python)."""
4 
5    def __init__(self, n: int, mask: int = 0) -> None:
6        self.n = n
7        self.mask = mask
8 
92 · Single-element operations
10    def add(self, i: int) -> None:
11        self.mask |= 1 << i
12 
13    def remove(self, i: int) -> None:
14        self.mask &= ~(1 << i)
15 
16    def has(self, i: int) -> bool:
17        return (self.mask >> i) & 1 == 1
18 
193 · Set algebra
20    def union(self, other: "BitSet") -> "BitSet":
21        return BitSet(self.n, self.mask | other.mask)
22 
23    def intersect(self, other: "BitSet") -> "BitSet":
24        return BitSet(self.n, self.mask & other.mask)
25 
26    def difference(self, other: "BitSet") -> "BitSet":
27        return BitSet(self.n, self.mask & ~other.mask)
28 
29    def __len__(self) -> int:
30        return self.mask.bit_count()  # 3.10+; bin(self.mask).count("1") otherwise
31 
324 · Enumerate members via the lowest set bit
33    def members(self) -> list[int]:
34        out, m = [], self.mask
35        while m:
36            low = m & -m
37            out.append(low.bit_length() - 1)
38            m ^= low
39        return out
40 
41 
425 · Application: which letters occur in a word
43def letters_mask(word: str) -> int:
44    m = 0
45    for ch in word:
46        m |= 1 << (ord(ch) - ord("a"))
47    return m
48 
49 
50def share_letter(a: str, b: str) -> bool:
51    return letters_mask(a) & letters_mask(b) != 0

Walkthrough

A Python int has unlimited width, so the same class handles 26 letters or 10,000 flags without change.
__len__ uses int.bit_count() (3.10+); bin(mask).count("1") is the portable fallback.
m & -m isolates the lowest set bit; low.bit_length() - 1 turns it into an index; m ^= low removes it.
ord(ch) - ord("a") maps letters to bit positions.

Complexity (this implementation)

time O(1) per set op · space O(1)

For masks wider than ~60 bits each operation costs O(width / 30) digit operations, still tiny.

Language notes

int.bit_length(), int.bit_count() and bin() are the whole toolkit; there is no bitset type in the stdlib.
Negative masks from ~ are fine internally, but always & full before printing or comparing.
A frozenset is often clearer than a mask in application code; masks win when they are dict keys in DP.

Common mistakes in this language

Using bin(mask).count("1") in a hot loop on 3.10+ when bit_count() is much faster.
Relying on ~mask as the complement without masking with (1 << n) - 1 — it has infinitely many leading ones.
Passing self.mask to functions expecting a set.

Language differences that matter here

Mask width: C++ uint64_t gives 64 flags (std::bitset<N> for more); JS/TS number masks are limited to 31 usable bits, then BigInt; Python ints are unbounded.
Popcount: C++ std::popcount / __builtin_popcountll; Python int.bit_count() (3.10+) or bin(n).count("1"); JS/TS have no intrinsic — Kernighan's loop or a lookup table.
Lowest-bit index: C++ std::countr_zero; JS/TS 31 - Math.clz32(m & -m); Python (m & -m).bit_length() - 1.
Complement: C++ unsigned ~m wraps to a positive value; JS ~m and Python ~m are negative — mask with (1 << n) - 1 when the value is printed or compared.

Complexity

Best

O(1)

Average

O(1)

Worst

O(1)

Space

O(1)

Per set operation on a universe that fits in one word. Bitsets over N elements cost O(N / 64) per operation. Enumerating all masks costs O(2^n).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Universe size n ≤ ~20 and the algorithm must index or enumerate subsets (TSP, assignment DP, "visit all nodes").
Many set unions/intersections on small universes, e.g. comparing letter sets of thousands of words in O(1) each.
Packing several small integer fields into one number for hashing or memory savings.

Avoid it when

Universe larger than the word size with no fixed bound — use a Hash Set or a boolean array.
When elements are not small non-negative integers and mapping them to indices adds more complexity than it removes.
When 2^n states do not fit in memory: n = 25 already needs 33 million entries per DP dimension.

Alternatives

Hash Set Array Bitmask DP

Common mistakes

Writing 1 << i with a 32-bit literal when i ≥ 31 — use 1L << i in Java, 1ULL << i in C++, and BigInt in JavaScript.
Testing membership with mask & (1 << i) == 1 instead of != 0; the AND result is 1 << i, not 1.
Forgetting the ~ in removal (mask & (1 << i) keeps only that bit instead of dropping it).
Using a signed shift on the top bit: in JavaScript 1 << 31 is negative and mask >> 31 sign-extends; use >>>.

Interview patterns

Maximum product of word lengths where words share no letters: 26-bit letter masks, pairwise AND.
Traveling-salesman-style DP dp[mask][last] — see Bitmask DP.
BFS over (node, visitedMask) states for shortest path visiting all nodes.
Counting subsets with a given property by iterating masks 0..2^n - 1 — see Subset Generation with Bitmasks.

Example problems

Shortest Path Visiting All Nodeshard Subsetsmedium Bit Counting Trickseasy

Overview

Intuition

How it works

Why it works

Recognition

Interactive visualization

Pseudocode

Implementations

Complexity

When to use — and when not to

Alternatives

Common mistakes

Interview patterns

Example problems

Related