pixie::BitVector Class Reference

Non-interleaved, non-owning bit vector with rank and select. More...

#include <bitvector.h>

Public Member Functions
	BitVector (std::span< const uint64_t > bit_vector, size_t num_bits)
	Construct from an external array of 64-bit words.
size_t	size () const
	Returns the number of valid bits.
int	operator[] (size_t pos) const
	Returns the bit at the given position.
uint64_t	rank (size_t pos) const
	Rank of 1s up to position pos (exclusive).
uint64_t	rank0 (size_t pos) const
	Rank of 0s up to position pos (exclusive).
uint64_t	select (size_t rank) const
	Select the position of the rank-th 1-bit (1-indexed).
uint64_t	select0 (size_t rank0) const
	Select the position of the rank0-th 0-bit (1-indexed).
std::string	to_string () const
	Convert to a binary string (debug helper).

Detailed Description

Non-interleaved, non-owning bit vector with rank and select.

This is a two-level rank/select index for a bit vector stored externally as 64-bit words. The layout follows ideas from:

{1} "SPIDER: Improved Succinct Rank and Select Performance" Matthew D. Laws, Jocelyn Bliven, Kit Conklin, Elyes Laalai, Samuel McCauley, Zach S. Sturdevant https://github.com/williams-cs/spider

{2} "Engineering compact data structures for rank and select queries on bit vectors" Kurpicz F. https://github.com/pasta-toolbox/bit_vector

Structure overview:

• Super blocks of 2^16 bits with 64-bit ranks (~0.98% overhead).
• Basic blocks of 512 bits with 16-bit ranks (~3.125% overhead).
• Select samples every 16384 bits (~0.39% overhead).

Rank: 2 table lookups plus SIMD popcount in the 512-bit block.

Select:

• - Start from a sampled super block.
• SIMD linear scan to find the super block.
• SIMD linear scan to find the basic block.

This variant does not interleave data and index, favoring simpler scans.

Constructor & Destructor Documentation

BitVector()

pixie::BitVector::BitVector ( std::span< const uint64_t > bit_vector, size_t num_bits )

inlineexplicit

Construct from an external array of 64-bit words.

Parameters

bit_vector	Backing data, not owned.
num_bits	Number of valid bits in the vector.

Member Function Documentation

operator[]()

int pixie::BitVector::operator[] ( size_t pos ) const

inline

Returns the bit at the given position.

Parameters

pos	Bit index in [0, size()).

rank()

uint64_t pixie::BitVector::rank ( size_t pos ) const

inline

Rank of 1s up to position pos (exclusive).

Parameters

pos	Bit index in [0, size()].

Returns

Number of 1s in [0, pos).

rank0()

uint64_t pixie::BitVector::rank0 ( size_t pos ) const

inline

Rank of 0s up to position pos (exclusive).

Parameters

pos	Bit index in [0, size()].

Returns

Number of 0s in [0, pos).

select()

uint64_t pixie::BitVector::select ( size_t rank ) const

inline

Select the position of the rank-th 1-bit (1-indexed).

Parameters

rank	1-based rank of the 1-bit to select.

Returns

Bit index, or size() if rank is out of range.

select0()

uint64_t pixie::BitVector::select0 ( size_t rank0 ) const

inline

Select the position of the rank0-th 0-bit (1-indexed).

Parameters

rank0

1-based rank of the 0-bit to select.

Returns

Bit index, or size() if rank0 is out of range.

---

The documentation for this class was generated from the following file:

• include/pixie/bitvector.h