SDSL 3.0.1
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 (const uint64_t *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 (const uint64_t *word, uint8_t offset=0, const uint8_t len=64)
 
static constexpr uint64_t read_int_and_move (const uint64_t *&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 (const uint64_t *word, uint8_t offset=0)
 Reads an unary decoded value from a bit position in an array.
 
static constexpr uint64_t read_unary_bounded (const uint64_t *word, uint8_t offset=0)
 
static constexpr uint64_t read_unary_and_move (const uint64_t *&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 (const uint64_t *&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 (const uint64_t *&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 (const uint64_t *word, uint64_t idx)
 Get the first one bit in the interval $[idx..\infty )$.
 
static constexpr uint64_t prev (const uint64_t *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 45 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 >
constexpr uint32_t sdsl::bits_impl< T >::_sel ( uint64_t  x,
uint32_t  i 
)
staticconstexpr

Definition at line 613 of file bits.hpp.

◆ cnt()

template<typename T >
constexpr 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 484 of file bits.hpp.

◆ cnt01()

template<typename T >
constexpr 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 570 of file bits.hpp.

◆ cnt10()

template<typename T >
constexpr 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 556 of file bits.hpp.

◆ cnt11() [1/2]

template<typename T >
constexpr 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 550 of file bits.hpp.

◆ cnt11() [2/2]

template<typename T >
constexpr 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 541 of file bits.hpp.

◆ cnt32()

template<typename T >
constexpr 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 503 of file bits.hpp.

◆ hi()

template<typename T >
constexpr 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 651 of file bits.hpp.

◆ hi11()

template<typename T >
constexpr 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 705 of file bits.hpp.

◆ lo()

template<typename T >
constexpr 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 686 of file bits.hpp.

◆ map01()

template<typename T >
constexpr 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 578 of file bits.hpp.

◆ map10()

template<typename T >
constexpr 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 564 of file bits.hpp.

◆ move_left()

template<typename T >
constexpr void sdsl::bits_impl< T >::move_left ( const uint64_t *&  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 887 of file bits.hpp.

◆ move_right()

template<typename T >
constexpr void sdsl::bits_impl< T >::move_right ( const uint64_t *&  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 877 of file bits.hpp.

◆ next()

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

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

Definition at line 897 of file bits.hpp.

◆ prev()

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

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

Definition at line 912 of file bits.hpp.

◆ read_int()

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

Reads a value from a bit position in an array.

Definition at line 770 of file bits.hpp.

◆ read_int_and_move()

template<typename T >
constexpr uint64_t sdsl::bits_impl< T >::read_int_and_move ( const uint64_t *&  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 792 of file bits.hpp.

◆ read_int_bounded()

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

Definition at line 786 of file bits.hpp.

◆ read_unary()

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

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

Definition at line 816 of file bits.hpp.

◆ read_unary_and_move()

template<typename T >
constexpr uint64_t sdsl::bits_impl< T >::read_unary_and_move ( const uint64_t *&  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 842 of file bits.hpp.

◆ read_unary_bounded()

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

Definition at line 831 of file bits.hpp.

◆ rev()

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

reverses a given 64 bit word

Definition at line 927 of file bits.hpp.

◆ sel()

template<typename T >
constexpr 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 584 of file bits.hpp.

◆ sel11()

template<typename T >
constexpr 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 711 of file bits.hpp.

◆ write_int()

template<typename T >
constexpr 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 717 of file bits.hpp.

◆ write_int_and_move()

template<typename T >
constexpr 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 742 of file bits.hpp.

Member Data Documentation

◆ all_set

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

64bit mask with all bits set to 1.

Definition at line 49 of file bits.hpp.

◆ deBruijn64

template<typename T = void>
constexpr 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 57 of file bits.hpp.

◆ lo_set

template<typename T >
constexpr uint64_t sdsl::bits_impl< T >::lo_set
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 187 of file bits.hpp.

◆ lo_unset

template<typename T >
constexpr uint64_t sdsl::bits_impl< T >::lo_unset
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 210 of file bits.hpp.

◆ lt_cnt

template<typename T >
constexpr uint8_t sdsl::bits_impl< T >::lt_cnt
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 163 of file bits.hpp.

◆ lt_deBruijn_to_idx

template<typename T >
constexpr uint32_t sdsl::bits_impl< T >::lt_deBruijn_to_idx
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 62 of file bits.hpp.

◆ lt_fib

template<typename T >
constexpr uint64_t sdsl::bits_impl< T >::lt_fib
staticconstexpr

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

Definition at line 69 of file bits.hpp.

◆ lt_hi

template<typename T >
constexpr uint32_t sdsl::bits_impl< T >::lt_hi
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 174 of file bits.hpp.

◆ lt_lo

template<typename T >
constexpr uint8_t sdsl::bits_impl< T >::lt_lo
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 231 of file bits.hpp.

◆ lt_sel

template<typename T >
constexpr uint8_t sdsl::bits_impl< T >::lt_sel
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 253 of file bits.hpp.

◆ ps_overflow

template<typename T >
constexpr uint64_t sdsl::bits_impl< T >::ps_overflow
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 320 of file bits.hpp.


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