SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::bits_impl< T > Struct Template Reference

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 $[idx..\infty )$.
 
static constexpr uint64_t prev (uint64_t const *word, uint64_t idx)
 Get the one bit with the greatest position in the interval $[0..idx]$.
 
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 $2^64$.
 
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.
 

Detailed Description

template<typename T = void>
struct sdsl::bits_impl< T >

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.

Author
Simon Gog

Definition at line 55 of file bits.hpp.

Constructor & Destructor Documentation

◆ bits_impl()

template<typename T = void>
sdsl::bits_impl< T >::bits_impl ( )
delete

Member Function Documentation

◆ _sel()

template<typename T>
uint32_t sdsl::bits_impl< T >::_sel ( uint64_t x,
uint32_t i )
staticconstexpr

Definition at line 615 of file bits.hpp.

◆ cnt()

template<typename T>
uint64_t sdsl::bits_impl< T >::cnt ( uint64_t x)
staticconstexpr

Counts the number of set bits in x.

Parameters
x64-bit word
Returns
Number of set bits.

Definition at line 486 of file bits.hpp.

◆ cnt01()

template<typename T>
uint32_t sdsl::bits_impl< T >::cnt01 ( uint64_t x,
uint64_t & c )
staticconstexpr

Count 01 bit pairs in the word x.

Parameters
x64bit integer to count the 01 bit pairs.
cCarry equals msb of the previous 64bit integer.

Definition at line 572 of file bits.hpp.

◆ cnt10()

template<typename T>
uint32_t sdsl::bits_impl< T >::cnt10 ( uint64_t x,
uint64_t & c )
staticconstexpr

Count 10 bit pairs in the word x.

Parameters
x64bit integer to count the 10 bit pairs.
cCarry equals msb of the previous 64bit integer.

Definition at line 558 of file bits.hpp.

◆ cnt11() [1/2]

template<typename T>
uint32_t sdsl::bits_impl< T >::cnt11 ( uint64_t x)
staticconstexpr

Count the number of consecutive and distinct 11 in the 64bit integer x.

Parameters
x64bit integer to count the terminating sequence 11 of a Fibonacci code.

Definition at line 552 of file bits.hpp.

◆ cnt11() [2/2]

template<typename T>
uint32_t sdsl::bits_impl< T >::cnt11 ( uint64_t x,
uint64_t & c )
staticconstexpr

Count the number of consecutive and distinct 11 in the 64bit integer x.

Parameters
x64bit integer to count the terminating sequence 11 of a Fibonacci code.
cCarry equals msb of the previous 64bit integer.

Definition at line 543 of file bits.hpp.

◆ cnt32()

template<typename T>
uint32_t sdsl::bits_impl< T >::cnt32 ( uint32_t x)
staticconstexpr

Counts the number of 1-bits in the 32bit integer x.

This function is a variant of the method cnt. If 32bit multiplication is fast, this method beats the cnt. for 32bit integers.

Parameters
x64bit integer to count the bits.
Returns
The number of 1-bits in x.

Definition at line 505 of file bits.hpp.

◆ hi()

template<typename T>
uint32_t sdsl::bits_impl< T >::hi ( uint64_t x)
staticconstexpr

Position of the most significant set bit the 64-bit word x.

Parameters
x64-bit word
Returns
The position (in 0..63) of the most significant set bit in x or 0 if x equals 0.
See also
sel, lo

Definition at line 653 of file bits.hpp.

◆ hi11()

template<typename T>
uint32_t sdsl::bits_impl< T >::hi11 ( uint64_t x)
staticconstexpr

Calculates the position of the leftmost 11-bit-pattern which terminates a Fibonacci coded integer in x.

Parameters
x64 bit integer.
Returns
The position (in 1..63) of the leftmost 1 of the leftmost 11-bit-pattern which terminates a Fibonacci coded integer in x if x contains a 11-bit-pattern and 0 otherwise.
See also
cnt11, sel11

Definition at line 712 of file bits.hpp.

◆ lo()

template<typename T>
uint32_t sdsl::bits_impl< T >::lo ( uint64_t x)
staticconstexpr

Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.

Parameters
x64 bit integer.
Returns
The position (in 0..63) of the rightmost 1-bit in the 64bit integer x if x>0 and 0 if x equals 0.
See also
sel, hi

Definition at line 689 of file bits.hpp.

◆ map01()

template<typename T>
uint64_t sdsl::bits_impl< T >::map01 ( uint64_t x,
uint64_t c = 1 )
staticconstexpr

Map all 01 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.

Definition at line 580 of file bits.hpp.

◆ map10()

template<typename T>
uint64_t sdsl::bits_impl< T >::map10 ( uint64_t x,
uint64_t c = 0 )
staticconstexpr

Map all 10 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.

Definition at line 566 of file bits.hpp.

◆ move_left()

template<typename T>
void sdsl::bits_impl< T >::move_left ( uint64_t const *& word,
uint8_t & offset,
const uint8_t len )
staticconstexpr

Move the bit-pointer (=uint64_t word and offset) len to the left.

Parameters
word64-bit word part of the bit pointer
offsetOffset part of the bit pointer
lenMove distance. $ len \in [0..64] $
See also
move_right

Definition at line 903 of file bits.hpp.

◆ move_right()

template<typename T>
void sdsl::bits_impl< T >::move_right ( uint64_t const *& word,
uint8_t & offset,
const uint8_t len )
staticconstexpr

Move the bit-pointer (=uint64_t word and offset) len to the right.

Parameters
word64-bit word part of the bit pointer
offsetOffset part of the bit pointer
lenMove distance. $ len \in [0..64] $
See also
move_left

Definition at line 893 of file bits.hpp.

◆ next()

template<typename T>
uint64_t sdsl::bits_impl< T >::next ( uint64_t const * word,
uint64_t idx )
staticconstexpr

Get the first one bit in the interval $[idx..\infty )$.

Definition at line 913 of file bits.hpp.

◆ prev()

template<typename T>
uint64_t sdsl::bits_impl< T >::prev ( uint64_t const * word,
uint64_t idx )
staticconstexpr

Get the one bit with the greatest position in the interval $[0..idx]$.

Definition at line 931 of file bits.hpp.

◆ read_int()

template<typename T>
uint64_t sdsl::bits_impl< T >::read_int ( uint64_t const * word,
uint8_t offset = 0,
const uint8_t len = 64 )
staticconstexpr

Reads a value from a bit position in an array.

Definition at line 777 of file bits.hpp.

◆ read_int_and_move()

template<typename T>
uint64_t sdsl::bits_impl< T >::read_int_and_move ( uint64_t const *& word,
uint8_t & offset,
const uint8_t len = 64 )
staticconstexpr

Reads a value from a bit position in an array and moved the bit-pointer.

Definition at line 799 of file bits.hpp.

◆ read_int_bounded()

template<typename T>
uint64_t sdsl::bits_impl< T >::read_int_bounded ( uint64_t const * word,
uint8_t offset = 0,
const uint8_t len = 64 )
staticconstexpr

Definition at line 793 of file bits.hpp.

◆ read_unary()

template<typename T>
uint64_t sdsl::bits_impl< T >::read_unary ( uint64_t const * word,
uint8_t offset = 0 )
staticconstexpr

Reads an unary decoded value from a bit position in an array.

Definition at line 823 of file bits.hpp.

◆ read_unary_and_move()

template<typename T>
uint64_t sdsl::bits_impl< T >::read_unary_and_move ( uint64_t const *& word,
uint8_t & offset )
staticconstexpr

Reads an unary decoded value from a bit position in an array and moves the bit-pointer.

Definition at line 857 of file bits.hpp.

◆ read_unary_bounded()

template<typename T>
uint64_t sdsl::bits_impl< T >::read_unary_bounded ( uint64_t const * word,
uint8_t offset = 0 )
staticconstexpr

Definition at line 843 of file bits.hpp.

◆ rev()

template<typename T>
uint64_t sdsl::bits_impl< T >::rev ( uint64_t x)
staticconstexpr

reverses a given 64 bit word

Definition at line 949 of file bits.hpp.

◆ sel()

template<typename T>
uint32_t sdsl::bits_impl< T >::sel ( uint64_t x,
uint32_t i )
staticconstexpr

Calculate the position of the i-th rightmost 1 bit in the 64bit integer x.

Parameters
x64bit integer.
iArgument i must be in the range $[1..cnt(x)]$.
Precondition
Argument i must be in the range $[1..cnt(x)]$.
See also
hi, lo

Definition at line 586 of file bits.hpp.

◆ sel11()

template<typename T>
uint32_t sdsl::bits_impl< T >::sel11 ( uint64_t x,
uint32_t i,
uint32_t c = 0 )
staticconstexpr

Calculates the position of the i-th rightmost 11-bit-pattern which terminates a Fibonacci coded integer in x.

Parameters
x64 bit integer.
iIndex of 11-bit-pattern. $i \in [1..cnt11(x)]$
cCarry bit from word before
Returns
The position (in 1..63) of the i-th 11-bit-pattern which terminates a Fibonacci coded integer in x if x contains at least i 11-bit-patterns and a undefined value otherwise.
See also
cnt11, hi11, sel

Definition at line 718 of file bits.hpp.

◆ write_int()

template<typename T>
void sdsl::bits_impl< T >::write_int ( uint64_t * word,
uint64_t x,
const uint8_t offset = 0,
const uint8_t len = 64 )
staticconstexpr

Writes value x to an bit position in an array.

Definition at line 724 of file bits.hpp.

◆ write_int_and_move()

template<typename T>
void sdsl::bits_impl< T >::write_int_and_move ( uint64_t *& word,
uint64_t x,
uint8_t & offset,
const uint8_t len )
staticconstexpr

Writes value x to an bit position in an array and moves the bit-pointer.

Definition at line 749 of file bits.hpp.

Member Data Documentation

◆ all_set

template<typename T = void>
uint64_t sdsl::bits_impl< T >::all_set {-1ULL}
staticconstexpr

64bit mask with all bits set to 1.

Definition at line 59 of file bits.hpp.

◆ deBruijn64

template<typename T = void>
uint64_t sdsl::bits_impl< T >::deBruijn64 {0x0218A392CD3D5DBFULL}
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.

Definition at line 67 of file bits.hpp.

◆ lo_set

template<typename T = void>
uint64_t sdsl::bits_impl< T >::lo_set[65]
staticconstexpr
Initial value:
= {
0x0000000000000000ULL, 0x0000000000000001ULL, 0x0000000000000003ULL, 0x0000000000000007ULL,
0x000000000000000FULL, 0x000000000000001FULL, 0x000000000000003FULL, 0x000000000000007FULL,
0x00000000000000FFULL, 0x00000000000001FFULL, 0x00000000000003FFULL, 0x00000000000007FFULL,
0x0000000000000FFFULL, 0x0000000000001FFFULL, 0x0000000000003FFFULL, 0x0000000000007FFFULL,
0x000000000000FFFFULL, 0x000000000001FFFFULL, 0x000000000003FFFFULL, 0x000000000007FFFFULL,
0x00000000000FFFFFULL, 0x00000000001FFFFFULL, 0x00000000003FFFFFULL, 0x00000000007FFFFFULL,
0x0000000000FFFFFFULL, 0x0000000001FFFFFFULL, 0x0000000003FFFFFFULL, 0x0000000007FFFFFFULL,
0x000000000FFFFFFFULL, 0x000000001FFFFFFFULL, 0x000000003FFFFFFFULL, 0x000000007FFFFFFFULL,
0x00000000FFFFFFFFULL, 0x00000001FFFFFFFFULL, 0x00000003FFFFFFFFULL, 0x00000007FFFFFFFFULL,
0x0000000FFFFFFFFFULL, 0x0000001FFFFFFFFFULL, 0x0000003FFFFFFFFFULL, 0x0000007FFFFFFFFFULL,
0x000000FFFFFFFFFFULL, 0x000001FFFFFFFFFFULL, 0x000003FFFFFFFFFFULL, 0x000007FFFFFFFFFFULL,
0x00000FFFFFFFFFFFULL, 0x00001FFFFFFFFFFFULL, 0x00003FFFFFFFFFFFULL, 0x00007FFFFFFFFFFFULL,
0x0000FFFFFFFFFFFFULL, 0x0001FFFFFFFFFFFFULL, 0x0003FFFFFFFFFFFFULL, 0x0007FFFFFFFFFFFFULL,
0x000FFFFFFFFFFFFFULL, 0x001FFFFFFFFFFFFFULL, 0x003FFFFFFFFFFFFFULL, 0x007FFFFFFFFFFFFFULL,
0x00FFFFFFFFFFFFFFULL, 0x01FFFFFFFFFFFFFFULL, 0x03FFFFFFFFFFFFFFULL, 0x07FFFFFFFFFFFFFFULL,
0x0FFFFFFFFFFFFFFFULL, 0x1FFFFFFFFFFFFFFFULL, 0x3FFFFFFFFFFFFFFFULL, 0x7FFFFFFFFFFFFFFFULL,
0xFFFFFFFFFFFFFFFFULL}

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...

Definition at line 194 of file bits.hpp.

◆ lo_unset

template<typename T = void>
uint64_t sdsl::bits_impl< T >::lo_unset[65]
staticconstexpr
Initial value:
= {
0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFF8ULL,
0xFFFFFFFFFFFFFFF0ULL, 0xFFFFFFFFFFFFFFE0ULL, 0xFFFFFFFFFFFFFFC0ULL, 0xFFFFFFFFFFFFFF80ULL,
0xFFFFFFFFFFFFFF00ULL, 0xFFFFFFFFFFFFFE00ULL, 0xFFFFFFFFFFFFFC00ULL, 0xFFFFFFFFFFFFF800ULL,
0xFFFFFFFFFFFFF000ULL, 0xFFFFFFFFFFFFE000ULL, 0xFFFFFFFFFFFFC000ULL, 0xFFFFFFFFFFFF8000ULL,
0xFFFFFFFFFFFF0000ULL, 0xFFFFFFFFFFFE0000ULL, 0xFFFFFFFFFFFC0000ULL, 0xFFFFFFFFFFF80000ULL,
0xFFFFFFFFFFF00000ULL, 0xFFFFFFFFFFE00000ULL, 0xFFFFFFFFFFC00000ULL, 0xFFFFFFFFFF800000ULL,
0xFFFFFFFFFF000000ULL, 0xFFFFFFFFFE000000ULL, 0xFFFFFFFFFC000000ULL, 0xFFFFFFFFF8000000ULL,
0xFFFFFFFFF0000000ULL, 0xFFFFFFFFE0000000ULL, 0xFFFFFFFFC0000000ULL, 0xFFFFFFFF80000000ULL,
0xFFFFFFFF00000000ULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFC00000000ULL, 0xFFFFFFF800000000ULL,
0xFFFFFFF000000000ULL, 0xFFFFFFE000000000ULL, 0xFFFFFFC000000000ULL, 0xFFFFFF8000000000ULL,
0xFFFFFF0000000000ULL, 0xFFFFFE0000000000ULL, 0xFFFFFC0000000000ULL, 0xFFFFF80000000000ULL,
0xFFFFF00000000000ULL, 0xFFFFE00000000000ULL, 0xFFFFC00000000000ULL, 0xFFFF800000000000ULL,
0xFFFF000000000000ULL, 0xFFFE000000000000ULL, 0xFFFC000000000000ULL, 0xFFF8000000000000ULL,
0xFFF0000000000000ULL, 0xFFE0000000000000ULL, 0xFFC0000000000000ULL, 0xFF80000000000000ULL,
0xFF00000000000000ULL, 0xFE00000000000000ULL, 0xFC00000000000000ULL, 0xF800000000000000ULL,
0xF000000000000000ULL, 0xE000000000000000ULL, 0xC000000000000000ULL, 0x8000000000000000ULL,
0x0000000000000000ULL}

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, ...

Definition at line 216 of file bits.hpp.

◆ lt_cnt

template<typename T = void>
uint8_t sdsl::bits_impl< T >::lt_cnt[256]
staticconstexpr
Initial value:
= {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2,
3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,
3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4,
5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}

Lookup table for byte popcounts.

Definition at line 172 of file bits.hpp.

◆ lt_deBruijn_to_idx

template<typename T = void>
uint32_t sdsl::bits_impl< T >::lt_deBruijn_to_idx[64]
staticconstexpr
Initial value:
= {0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40,
5, 17, 26, 38, 15, 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57,
63, 6, 12, 18, 24, 27, 33, 39, 16, 37, 45, 47, 30, 53, 49, 56,
62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58}

This table maps a 6-bit subsequence S[idx...idx+5] of constant deBruijn64 to idx.

See also
deBruijn64

Definition at line 72 of file bits.hpp.

◆ lt_fib

template<typename T = void>
uint64_t sdsl::bits_impl< T >::lt_fib[92]
staticconstexpr

Array containing Fibonacci numbers less than $2^64$.

Definition at line 78 of file bits.hpp.

◆ lt_hi

template<typename T = void>
uint32_t sdsl::bits_impl< T >::lt_hi[256]
staticconstexpr
Initial value:
= {
0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7}

Lookup table for most significant set bit in a byte.

Definition at line 182 of file bits.hpp.

◆ lt_lo

template<typename T = void>
uint8_t sdsl::bits_impl< T >::lt_lo[256]
staticconstexpr
Initial value:
= {
0x00, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00,
0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00, 0x01, 0x00,
0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00,
0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x06, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00,
0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00,
0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00,
0x01, 0x00, 0x07, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00,
0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00,
0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x06, 0x00, 0x01, 0x00, 0x02, 0x00,
0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00,
0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00,
0x02, 0x00, 0x01, 0x00}

Lookup table for least significant set bit in a byte.

Definition at line 236 of file bits.hpp.

◆ lt_sel

template<typename T = void>
uint8_t sdsl::bits_impl< T >::lt_sel[256 *8]
staticconstexpr

Lookup table for select on bytes.

Entry at idx = 256*j + i equals the position of the (j+1)-th set bit in byte i. Positions lie in the range $[0..7]$.

Definition at line 257 of file bits.hpp.

◆ ps_overflow

template<typename T = void>
uint64_t sdsl::bits_impl< T >::ps_overflow[65]
staticconstexpr
Initial value:
= {
0x8080808080808080ULL, 0x7f7f7f7f7f7f7f7fULL, 0x7e7e7e7e7e7e7e7eULL, 0x7d7d7d7d7d7d7d7dULL,
0x7c7c7c7c7c7c7c7cULL, 0x7b7b7b7b7b7b7b7bULL, 0x7a7a7a7a7a7a7a7aULL, 0x7979797979797979ULL,
0x7878787878787878ULL, 0x7777777777777777ULL, 0x7676767676767676ULL, 0x7575757575757575ULL,
0x7474747474747474ULL, 0x7373737373737373ULL, 0x7272727272727272ULL, 0x7171717171717171ULL,
0x7070707070707070ULL, 0x6f6f6f6f6f6f6f6fULL, 0x6e6e6e6e6e6e6e6eULL, 0x6d6d6d6d6d6d6d6dULL,
0x6c6c6c6c6c6c6c6cULL, 0x6b6b6b6b6b6b6b6bULL, 0x6a6a6a6a6a6a6a6aULL, 0x6969696969696969ULL,
0x6868686868686868ULL, 0x6767676767676767ULL, 0x6666666666666666ULL, 0x6565656565656565ULL,
0x6464646464646464ULL, 0x6363636363636363ULL, 0x6262626262626262ULL, 0x6161616161616161ULL,
0x6060606060606060ULL, 0x5f5f5f5f5f5f5f5fULL, 0x5e5e5e5e5e5e5e5eULL, 0x5d5d5d5d5d5d5d5dULL,
0x5c5c5c5c5c5c5c5cULL, 0x5b5b5b5b5b5b5b5bULL, 0x5a5a5a5a5a5a5a5aULL, 0x5959595959595959ULL,
0x5858585858585858ULL, 0x5757575757575757ULL, 0x5656565656565656ULL, 0x5555555555555555ULL,
0x5454545454545454ULL, 0x5353535353535353ULL, 0x5252525252525252ULL, 0x5151515151515151ULL,
0x5050505050505050ULL, 0x4f4f4f4f4f4f4f4fULL, 0x4e4e4e4e4e4e4e4eULL, 0x4d4d4d4d4d4d4d4dULL,
0x4c4c4c4c4c4c4c4cULL, 0x4b4b4b4b4b4b4b4bULL, 0x4a4a4a4a4a4a4a4aULL, 0x4949494949494949ULL,
0x4848484848484848ULL, 0x4747474747474747ULL, 0x4646464646464646ULL, 0x4545454545454545ULL,
0x4444444444444444ULL, 0x4343434343434343ULL, 0x4242424242424242ULL, 0x4141414141414141ULL,
0x4040404040404040ULL}

Use to help to decide if a prefix sum stored in a byte overflows.

Definition at line 323 of file bits.hpp.


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