select.hpp File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
uint64_t	pasta::select (uint64_t x, uint64_t k)
	Select set bit in 64-bit word and return its position starting from the LSB (starting from the left).

Variables
constexpr uint8_t	pasta::kSelectInByte [2048]
	Required lookup table by select64 in case version without intrinsics is used.

Function Documentation

select()

uint64_t pasta::select ( uint64_t x, uint64_t k )

nodiscard

Select set bit in 64-bit word and return its position starting from the LSB (starting from the left).

Uses the broadword selection algorithm by Vigna [1], improved by Gog and Petri [2] and Vigna [3]. Facebook's Folly implementation [4].

[1] Sebastiano Vigna. Broadword Implementation of Rank/Select Queries. WEA, 2008

[2] Simon Gog, Matthias Petri. Optimized succinct data structures for massive data. Softw. Pract. Exper., 2014

[3] Sebastiano Vigna. MG4J 5.2.1. http://mg4j.di.unimi.it/

[4] Facebook Folly library: https://github.com/facebook/folly

Parameters

x	64-bit word the bit is selected in.
k	Rank of the bit that is selected, i.e., 1st to 64-th set bit.

Returns

Position of the rank-th bit starting from the LSB (starting from the left).