Algorithms / Bitmask Set
Least You Need to Know: Bitmasks as Sets, Flags, and Small-State Compression
A bitmask can represent membership in a small universe using one integer. This lets interviews compress sets, feature flags, visited states, and eligibility rules into fast bitwise operations.
The least you need to know
- Bit `i` being 1 means item `i` is present or enabled.
- OR is set union and AND is set intersection when masks represent sets.
- Membership checks use a shifted bit mask at the relevant position.
- A compact bitmask state often replaces a slower array of booleans.
- A mask is best when the universe is small and fixed enough to fit in available bits.
Key notation
mask
integer whose bits encode membership
1 << i
mask containing only item i
A & B
items present in both masks
Tiny worked example
- Suppose bits 0 through 4 represent required skills.
- A candidate mask stores which skills are present.
- To test for skill 3, compute `mask & (1 << 3)`.
- To add skills from another source, OR the masks together.
Common mistakes
- Students often mix up bit position with numeric value.
- Students often forget that masks only work cleanly when the universe can be indexed into bits.
- Students often confuse subset checks with equality checks.
How to recognize this kind of problem
- The prompt uses a small set of yes/no features or visited categories.
- State can be compressed into a single integer.
- Union, intersection, and membership appear frequently.
Next recommended lesson
Continue through this topic with Least You Need to Know: AND, OR, XOR, and Single-Bit Updates.
Least You Need to Know: AND, OR, XOR, and Single-Bit UpdatesRelated lessons
Keep going with nearby lessons in the same topic.