pub fn select64(n: u64, rank: u8) -> u8Expand description
Returns the position of the rank-th (counting from 0) one in the bit representation of n,
i.e. the index of the one with the given rank.
On x86-64 CPU with the BMI2 instruction set, it uses the method described in:
- Prashant Pandey, Michael A. Bender, Rob Johnson, and Rob Patro, “A General-Purpose Counting Filter: Making Every Bit Count”, In Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD ’17). Association for Computing Machinery, New York, NY, USA, 775–787. https://doi.org/10.1145/3035918.3035963
- Prashant Pandey, Michael A. Bender, Rob Johnson, “A Fast x86 Implementation of Select”, arXiv:1706.00990
If BMI2 is not available, the implementation uses the broadword selection algorithm by Vigna, improved by Gog and Petri, and Vigna:
- Sebastiano Vigna, “Broadword Implementation of Rank/Select Queries”, WEA, 2008
- Simon Gog, Matthias Petri, “Optimized succinct data structures for massive data”. Software: Practice and Experience 44, 2014
- Sebastiano Vigna, The selection problem https://sux4j.di.unimi.it/select.php
The implementation is based on the one contained in folly library by Meta.