Bitmasks as Tiny Sets
Represent subsets as integers.
Bitmasks as Tiny Sets is a free Coding Interview Prep lesson on CoddyKit. This is lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, and your progress syncs across the web and the CoddyKit app. The Coding Interview Prep course includes 4 lessons in total.
An Integer as a Set
A single integer can stand in for a whole set: bit i being 1 means element i is in. This packs subsets into one tiny, fast value. 🎒
The Empty and Full Sets
The number 0 is the empty set, while a value with the lowest n bits all on means every element is present.
empty = 0
full = (1 << 4) - 1 # 0b1111, four elementsAdd an Element
To add element i to the set, OR in its bit. This is exactly the set-a-bit move, now read as a union with one item.
s = 0
s |= (1 << 2) # add element 2Remove an Element
To remove element i, AND with the inverted bit. The element leaves the set and everyone else stays put. This is set difference by one item.
s &= ~(1 << 2) # remove element 2Test Membership
Check if element i belongs by ANDing with its bit. A nonzero result means it is a member of the set.
if s & (1 << 2):
print('2 is in the set')Union and Intersection
OR two masks for their union; AND them for their intersection. Whole set operations become one machine instruction each.
union = a | b
inter = a & bSet Size Is Popcount
The number of elements in a bitmask is just its set-bit count. Reach for bit_count to get the size instantly.
size = mask.bit_count()Loop Over All Subsets
For n elements, the integers from 0 to 2 to the n minus 1 enumerate every subset. One simple range loop covers them all.
for mask in range(1 << n):
pass # mask is one subsetIterate Submasks Fast
To visit only subsets of a given mask, use the classic submask loop. It steps through each subset in descending order.
sub = mask
while sub:
sub = (sub - 1) & maskBitmask DP Lives Here
Bitmasks are the state for many DP problems, like the traveling salesman, where the mask tracks which nodes you have visited.
Keep n Small
With 2 to the n subsets, this trick stays practical only for small n, usually up to about 20. Beyond that the count explodes. ⚠️
Quick Check
One last set-as-mask question.
Recap: Bitmask Sets
You can store a set in one integer, add and remove with masks, and loop over every subset. This unlocks fast bitmask DP. 🎉
Learn Coding Interview Prep with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 90
- Lessons
- 360
Frequently Asked Questions
Is the “Bitmasks as Tiny Sets” lesson free?
Yes — the full text of “Bitmasks as Tiny Sets” is free to read here on the web. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO. The Coding Interview Prep course includes 4 lessons in total.
What will I learn in “Bitmasks as Tiny Sets”?
Represent subsets as integers. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners, so you can start here or from the beginning and move at your own pace. This is lesson 4 of 4.
How long does the “Bitmasks as Tiny Sets” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- AND, OR, XOR & Shifts
- Set, Clear & Toggle a Bit
- Count Bits and Lowest Set Bit
- Bitmasks as Tiny Sets