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.
Least you need to know
- Bit
ibeing 1 means itemiis 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
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 it
- 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.