Overview
Bitset operations store Boolean membership in bits rather than separate objects. Logical word operations such as AND, OR, XOR, and shifts then update or compare many elements at once.
CoreSource checked
Bitset Operations
Represents dense sets as machine-word bits so membership and set operations run in word-sized chunks.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Set Data Structures
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
dense set operationsset data structuresbit masksdata structures
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(n / w)
Worst
O(n / w)
Space
O(n / w)
When to Use
- Use when the universe can be mapped to compact integer positions.
- Use when word-level parallelism can replace many scalar Boolean operations.
When Not to Use
- Avoid when the universe is sparse and the bit array would waste memory.
- Avoid when insert/delete semantics need richer per-item metadata.
What It Does
- Computes set data structures within Set Data Structures workloads (O(n / w) time, O(n / w) space).
- Works by Logical word operations such as AND, OR, XOR, and shifts then update or compare many elements at once.
- Maintains key invariants across dense set operations, set data structures, bit masks.
Use Cases
- Dense small-universe sets
- Fast subset, intersection, and union checks
- Dynamic-programming states stored as bit masks
Inputs
- Keys, values, items, or graph records
- Operations such as insert, delete, or query
Outputs
- Stored structure state
- Query result or updated collection
Pseudocode
- 1.Map each universe item to a bit index
- 2.Store bits in fixed-width words
- 3.For union, OR corresponding words
- 4.For intersection, AND corresponding words
- 5.Mask unused high bits in the final word
Canonical Example
- Input
- A = {0, 2}, B = {1, 2} over universe 0..3
- Output
- A OR B = bits 1110, representing {0, 1, 2}
- Explanation
- Each set is a bit mask, and bitwise OR combines memberships position by position.
Implementation Notes
- Define bit numbering and word size at the API boundary.
- Use masks for partial words at the end of the universe.
- Test empty sets, full words, and boundary bits around word-size multiples.
Common Pitfalls
- Forgetting the universe-to-bit mapping creates incorrect membership answers.
- Shifts across word boundaries need explicit carry handling.
- Signed integer shifts can behave differently across languages.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow representing membership as machine-word bits for parallel logical operations on a small dense set operations example.
Step 1 of 5: Map each universe item to a bit index
data-structures-mechanismNotes
Bitsets are fastest when the universe is stable, compact, and small enough to keep masks cache-friendly.
Sources (1)
What each reference supports for this entry.
Hacker's Delight
BookReference for packed-bit operations, masks, shifts, and word-level set manipulation.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toHash Table
Data Structures · Foundation
Bitsets trade sparse key flexibility for compact constant-time membership over a fixed universe.
Compare with thisUsed byBitmask Subset Enumeration
Procedural Generation · Extended
Bitmask Subset Enumeration uses bit operations to represent membership and advance through subsets or submasks.
Compare with thisRelationships
View full relationship pageAlternative toHash Table
Bitsets trade sparse key flexibility for compact constant-time membership over a fixed universe.
Often paired withBloom Filter
Bloom filters also use bit arrays, but allow probabilistic membership over hashed positions.
Often paired withCount-Min Sketch
Sketch structures commonly use compact arrays and hash-derived positions like bitset-style representations.
Related Algorithms
Tags
Data Structure