SDSL 3.0.3
Succinct Data Structure Library
|
A helper class for bitwise tricks on 64 bit words. More...
#include <bits.hpp>
Public Member Functions | |
bits_impl ()=delete | |
Static Public Member Functions | |
static constexpr uint64_t | cnt (uint64_t x) |
Counts the number of set bits in x. | |
static constexpr uint32_t | hi (uint64_t x) |
Position of the most significant set bit the 64-bit word x. | |
static constexpr uint32_t | lo (uint64_t x) |
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists. | |
static constexpr uint32_t | cnt32 (uint32_t x) |
Counts the number of 1-bits in the 32bit integer x. | |
static constexpr uint32_t | cnt11 (uint64_t x, uint64_t &c) |
Count the number of consecutive and distinct 11 in the 64bit integer x. | |
static constexpr uint32_t | cnt11 (uint64_t x) |
Count the number of consecutive and distinct 11 in the 64bit integer x. | |
static constexpr uint32_t | cnt10 (uint64_t x, uint64_t &c) |
Count 10 bit pairs in the word x. | |
static constexpr uint32_t | cnt01 (uint64_t x, uint64_t &c) |
Count 01 bit pairs in the word x. | |
static constexpr uint64_t | map10 (uint64_t x, uint64_t c=0) |
Map all 10 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00. | |
static constexpr uint64_t | map01 (uint64_t x, uint64_t c=1) |
Map all 01 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00. | |
static constexpr uint32_t | sel (uint64_t x, uint32_t i) |
Calculate the position of the i-th rightmost 1 bit in the 64bit integer x. | |
static constexpr uint32_t | _sel (uint64_t x, uint32_t i) |
static constexpr uint32_t | sel11 (uint64_t x, uint32_t i, uint32_t c=0) |
Calculates the position of the i-th rightmost 11-bit-pattern which terminates a Fibonacci coded integer in x. | |
static constexpr uint32_t | hi11 (uint64_t x) |
Calculates the position of the leftmost 11-bit-pattern which terminates a Fibonacci coded integer in x. | |
static constexpr void | write_int (uint64_t *word, uint64_t x, const uint8_t offset=0, const uint8_t len=64) |
Writes value x to an bit position in an array. | |
static constexpr void | write_int_and_move (uint64_t *&word, uint64_t x, uint8_t &offset, const uint8_t len) |
Writes value x to an bit position in an array and moves the bit-pointer. | |
static constexpr uint64_t | read_int (uint64_t const *word, uint8_t offset=0, const uint8_t len=64) |
Reads a value from a bit position in an array. | |
static constexpr uint64_t | read_int_bounded (uint64_t const *word, uint8_t offset=0, const uint8_t len=64) |
static constexpr uint64_t | read_int_and_move (uint64_t const *&word, uint8_t &offset, const uint8_t len=64) |
Reads a value from a bit position in an array and moved the bit-pointer. | |
static constexpr uint64_t | read_unary (uint64_t const *word, uint8_t offset=0) |
Reads an unary decoded value from a bit position in an array. | |
static constexpr uint64_t | read_unary_bounded (uint64_t const *word, uint8_t offset=0) |
static constexpr uint64_t | read_unary_and_move (uint64_t const *&word, uint8_t &offset) |
Reads an unary decoded value from a bit position in an array and moves the bit-pointer. | |
static constexpr void | move_right (uint64_t const *&word, uint8_t &offset, const uint8_t len) |
Move the bit-pointer (=uint64_t word and offset) len to the right. | |
static constexpr void | move_left (uint64_t const *&word, uint8_t &offset, const uint8_t len) |
Move the bit-pointer (=uint64_t word and offset) len to the left. | |
static constexpr uint64_t | next (uint64_t const *word, uint64_t idx) |
Get the first one bit in the interval ![]() | |
static constexpr uint64_t | prev (uint64_t const *word, uint64_t idx) |
Get the one bit with the greatest position in the interval ![]() | |
static constexpr uint64_t | rev (uint64_t x) |
reverses a given 64 bit word | |
Static Public Attributes | |
static constexpr uint64_t | all_set {-1ULL} |
64bit mask with all bits set to 1. | |
static constexpr uint64_t | deBruijn64 {0x0218A392CD3D5DBFULL} |
This constant represents a de Bruijn sequence B(k,n) for k=2 and n=6. | |
static constexpr uint32_t | lt_deBruijn_to_idx [64] |
This table maps a 6-bit subsequence S[idx...idx+5] of constant deBruijn64 to idx. | |
static constexpr uint64_t | lt_fib [92] |
Array containing Fibonacci numbers less than ![]() | |
static constexpr uint8_t | lt_cnt [256] |
Lookup table for byte popcounts. | |
static constexpr uint32_t | lt_hi [256] |
Lookup table for most significant set bit in a byte. | |
static constexpr uint64_t | lo_set [65] |
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set. | |
static constexpr uint64_t | lo_unset [65] |
lo_unset[i] is a 64-bit word with the i least significant bits not set and the high bits set. | |
static constexpr uint8_t | lt_lo [256] |
Lookup table for least significant set bit in a byte. | |
static constexpr uint8_t | lt_sel [256 *8] |
Lookup table for select on bytes. | |
static constexpr uint64_t | ps_overflow [65] |
Use to help to decide if a prefix sum stored in a byte overflows. | |
A helper class for bitwise tricks on 64 bit words.
bits is a helper class for bitwise tricks and techniques. For the basic tricks and techiques we refer to Donald E. Knuth's "The Art of Computer Programming", Volume 4A, Chapter 7.1.3 and the informative website of Sean E. Anderson about the topic: http://www-graphics.stanford.edu/~seander/bithacks.html .
We have added new functions like: cnt11 and sel11.
All members of this class are static variables or methods. This class cannot be instantiated.
|
delete |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
Calculates the position of the leftmost 11-bit-pattern which terminates a Fibonacci coded integer in x.
x | 64 bit integer. |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
Move the bit-pointer (=uint64_t word and offset) len
to the left.
word | 64-bit word part of the bit pointer |
offset | Offset part of the bit pointer |
len | Move distance. ![]() |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
Calculates the position of the i-th rightmost 11-bit-pattern which terminates a Fibonacci coded integer in x.
x | 64 bit integer. |
i | Index of 11-bit-pattern. ![]() |
c | Carry bit from word before |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
This constant represents a de Bruijn sequence B(k,n) for k=2 and n=6.
Details for de Bruijn sequences see http://en.wikipedia.org/wiki/De_bruijn_sequence deBruijn64 is used in combination with the array lt_deBruijn_to_idx.
|
staticconstexpr |
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
lo_set[0] = 0ULL, lo_set[1]=1ULL, lo_set[2]=3ULL...
|
staticconstexpr |
lo_unset[i] is a 64-bit word with the i least significant bits not set and the high bits set.
lo_unset[0] = FFFFFFFFFFFFFFFFULL, lo_unset_set[1]=FFFFFFFFFFFFFFFEULL, ...
|
staticconstexpr |
Lookup table for byte popcounts.
|
staticconstexpr |
This table maps a 6-bit subsequence S[idx...idx+5] of constant deBruijn64 to idx.
|
staticconstexpr |
|
staticconstexpr |
Lookup table for most significant set bit in a byte.
|
staticconstexpr |
Lookup table for least significant set bit in a byte.
|
staticconstexpr |
|
staticconstexpr |
Use to help to decide if a prefix sum stored in a byte overflows.