Bitmask vs HashSet
Use a bitmask when the universe is small and fixed, up to about 64 items, because then a whole set fits in one long and set operations become single instructions. Use a HashSet for anything larger or unbounded.
A set of items drawn from a small known universe does not need a data structure at all. Number the items, and one integer holds the set: bit i is 1 when item i is present. Union becomes a bitwise or, intersection an and, and membership a shift and a test, all in one instruction each.
Side by side
| Dimension | Bitmask | HashSet |
|---|---|---|
| Universe size | Up to 32 with int, 64 with long | Unbounded |
| Memory per set | 4 or 8 bytes total | Tens of bytes per element |
| Membership test | One shift and one and | Hash, bucket, equals |
| Union and intersection | One instruction each | A loop over one of the sets |
| As a map key | Free, it is an int | Needs a stable hashCode and equals |
| Readability | Poor without named helpers | Says what it means |
When to pick each
Bitmask
- Dynamic programming over subsets, where the mask is the state: travelling salesman, assignment, and anything phrased as visit every item once.
- Enumerating all subsets of a small collection, where counting from 0 to 2^n - 1 generates them with no recursion.
- Compact flags and visited sets inside a hot loop, where one long replaces an object graph.
HashSet
- Anything over 64 possible elements, or a universe you cannot enumerate up front.
- Keys that are strings or objects rather than small integers.
- Code other people will read, where the intent matters more than the instruction count.
Shifting by more than the width of the type. In Java 1 << 35 does not overflow into zero, it silently shifts by 35 mod 32, so bit 3 gets set and the bug looks like a logic error somewhere else entirely. The fix is 1L << 35 whenever the universe can exceed 32, and the habit worth forming is writing 1L in mask code by default.
Questions people ask
How do I enumerate the subsets of a mask?
Walk sub = (sub - 1) & mask starting from sub = mask, and stop after handling zero. That visits every submask of the given mask exactly once, which is the inner loop of several subset dynamic programming problems, and over all masks it totals 3^n rather than 4^n.
Is a bitmask faster than a boolean array?
For whole-set operations, substantially: one or against a 64-element boolean array is one instruction against a loop of 64. For single-element access the difference is small, and the array is clearer. The real wins are using the mask as a map key or a dp index, which a boolean array cannot do.
Which bit tricks are worth memorising?
Four. n & (n - 1) clears the lowest set bit, which gives you Kernighan's loop for counting them. n & -n isolates the lowest set bit. n & (n - 1) being zero tests for a power of two, after ruling out zero. And Integer.bitCount is a single CPU instruction on any modern machine, so there is no reason to hand-roll the count in production code.