SDSL  3.0.0
Succinct Data Structure Library
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 SDSL_CONSTEXPR uint64_t cnt (uint64_t x)
 Counts the number of set bits in x. More...
 
static SDSL_CONSTEXPR uint32_t hi (uint64_t x)
 Position of the most significant set bit the 64-bit word x. More...
 
static SDSL_CONSTEXPR uint32_t lo (uint64_t x)
 Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists. More...
 
static SDSL_CONSTEXPR uint32_t cnt32 (uint32_t x)
 Counts the number of 1-bits in the 32bit integer x. More...
 
static SDSL_CONSTEXPR uint32_t cnt11 (uint64_t x, uint64_t &c)
 Count the number of consecutive and distinct 11 in the 64bit integer x. More...
 
static SDSL_CONSTEXPR uint32_t cnt11 (uint64_t x)
 Count the number of consecutive and distinct 11 in the 64bit integer x. More...
 
static SDSL_CONSTEXPR uint32_t cnt10 (uint64_t x, uint64_t &c)
 Count 10 bit pairs in the word x. More...
 
static SDSL_CONSTEXPR uint32_t cnt01 (uint64_t x, uint64_t &c)
 Count 01 bit pairs in the word x. More...
 
static SDSL_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. More...
 
static SDSL_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. More...
 
static SDSL_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. More...
 
static SDSL_CONSTEXPR uint32_t _sel (uint64_t x, uint32_t i)
 
static SDSL_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. More...
 
static SDSL_CONSTEXPR uint32_t hi11 (uint64_t x)
 Calculates the position of the leftmost 11-bit-pattern which terminates a Fibonacci coded integer in x. More...
 
static SDSL_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. More...
 
static SDSL_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. More...
 
static SDSL_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. More...
 
static SDSL_CONSTEXPR uint64_t read_int_bounded (const uint64_t *word, uint8_t offset=0, const uint8_t len=64)
 
static SDSL_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. More...
 
static SDSL_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. More...
 
static SDSL_CONSTEXPR uint64_t read_unary_bounded (const uint64_t *word, uint8_t offset=0)
 
static SDSL_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. More...
 
static SDSL_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. More...
 
static SDSL_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. More...
 
static SDSL_CONSTEXPR uint64_t next (const uint64_t *word, uint64_t idx)
 Get the first one bit in the interval $[idx..\infty )$. More...
 
static SDSL_CONSTEXPR uint64_t prev (const uint64_t *word, uint64_t idx)
 Get the one bit with the greatest position in the interval $[0..idx]$. More...
 
static SDSL_CONSTEXPR uint64_t rev (uint64_t x)
 reverses a given 64 bit word More...
 

Static Public Attributes

constexpr static uint64_t all_set { -1ULL }
 64bit mask with all bits set to 1. More...
 
constexpr static uint64_t deBruijn64 { 0x0218A392CD3D5DBFULL }
 This constant represents a de Bruijn sequence B(k,n) for k=2 and n=6. More...
 
constexpr static uint32_t lt_deBruijn_to_idx [64]
 This table maps a 6-bit subsequence S[idx...idx+5] of constant deBruijn64 to idx. More...
 
constexpr static uint64_t lt_fib [92]
 Array containing Fibonacci numbers less than $2^64$. More...
 
constexpr static uint8_t lt_cnt [256]
 Lookup table for byte popcounts. More...
 
constexpr static uint32_t lt_hi [256]
 Lookup table for most significant set bit in a byte. More...
 
constexpr static 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. More...
 
constexpr static 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. More...
 
constexpr static uint8_t lt_lo [256]
 Lookup table for least significant set bit in a byte. More...
 
constexpr static uint8_t lt_sel [256 *8]
 Lookup table for select on bytes. More...
 
constexpr static uint64_t ps_overflow [65]
 Use to help to decide if a prefix sum stored in a byte overflows. More...
 

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 >
SDSL_CONSTEXPR uint32_t sdsl::bits_impl< T >::_sel ( uint64_t  x,
uint32_t  i 
)
inlinestatic

Definition at line 623 of file bits.hpp.

◆ cnt()

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

Counts the number of set bits in x.

Parameters
x64-bit word
Returns
Number of set bits.

Definition at line 494 of file bits.hpp.

◆ cnt01()

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

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 580 of file bits.hpp.

◆ cnt10()

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

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 566 of file bits.hpp.

◆ cnt11() [1/2]

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

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 560 of file bits.hpp.

◆ cnt11() [2/2]

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

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 551 of file bits.hpp.

◆ cnt32()

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

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 513 of file bits.hpp.

◆ hi()

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

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 661 of file bits.hpp.

◆ hi11()

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

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 715 of file bits.hpp.

◆ lo()

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

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 696 of file bits.hpp.

◆ map01()

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

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 588 of file bits.hpp.

◆ map10()

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

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 574 of file bits.hpp.

◆ move_left()

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

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 902 of file bits.hpp.

◆ move_right()

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

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 892 of file bits.hpp.

◆ next()

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

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

Definition at line 912 of file bits.hpp.

◆ prev()

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

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

Definition at line 927 of file bits.hpp.

◆ read_int()

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

Reads a value from a bit position in an array.

Definition at line 783 of file bits.hpp.

◆ read_int_and_move()

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

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

Definition at line 805 of file bits.hpp.

◆ read_int_bounded()

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

Definition at line 799 of file bits.hpp.

◆ read_unary()

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

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

Definition at line 831 of file bits.hpp.

◆ read_unary_and_move()

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

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 >
SDSL_CONSTEXPR uint64_t sdsl::bits_impl< T >::read_unary_bounded ( const uint64_t *  word,
uint8_t  offset = 0 
)
inlinestatic

Definition at line 846 of file bits.hpp.

◆ rev()

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

reverses a given 64 bit word

Definition at line 942 of file bits.hpp.

◆ sel()

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

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 594 of file bits.hpp.

◆ sel11()

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

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 721 of file bits.hpp.

◆ write_int()

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

Writes value x to an bit position in an array.

Definition at line 727 of file bits.hpp.

◆ write_int_and_move()

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

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

Definition at line 752 of file bits.hpp.

Member Data Documentation

◆ all_set

template<typename T = void>
constexpr static 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>
constexpr static 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 >
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 197 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 220 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 173 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 72 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 79 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 184 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 241 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 263 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 330 of file bits.hpp.


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