Bitvector Rank–Select Directory
Navigate packed bits by translating between prefix counts and positions of ones.
Free theory articleNavigate packed bits by translating between prefix counts and positions of ones.
Concept & interpretation
Rank and select operations allow querying the number of ones in a prefix of a bit vector and finding the position of the k-th one. A block directory structure precomputes these values for blocks of bits, enabling fast lookups without scanning the entire vector.
Experiment
Use the Interactive Bitvector Rank–Select Directory to explore rank and select calculations.
- Select Bits to be "Mixed".
- Select Prefix length to be 4. Observe that the exclusive prefix rank updates.
- Change One ordinal to 4. Notice the new select position calculated.