Bitset
An array of bits packed into machine words — set/clear/toggle/test a single bit in O(1), and whole-set operations (union, intersection) run a word at a time instead of a bit at a time.
A bitset represents a set of small non-negative integers (or n boolean flags) as a packed sequence of bits, typically grouped into 32- or 64-bit words. Testing or flipping bit i is one word lookup (i ÷ word size) plus a mask operation (i mod word size) — O(1) and extremely cache-friendly.
The real win is bulk operations: union, intersection, and difference between two bitsets of the same size are a single bitwise OR/AND/XOR per word, so an operation over n elements costs O(n / word size) instead of O(n) — a 32x or 64x constant-factor speedup over a boolean array.
The trade-off is that a bitset only represents small dense integer ranges efficiently — a bitset for "which of the numbers 0..999" is a tight 125 bytes, but a bitset for "which of these 10 arbitrary large IDs" wastes enormous space unless the IDs are first compressed to a dense range.
Operations
| Operation | Complexity |
|---|---|
| test bit | O(1) |
| set / clear / toggle bit | O(1) |
| union / intersection (n bits) | O(n / word size) |
| count set bits | O(n / word size) with popcount |
Where it's used
Bloom filters, compact visited-sets in graph algorithms, feature flags, permission masks, the Sieve of Eratosthenes at scale.