File failed to load: https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/config/TeX-MML-AM_CHTML/MathJax.js
DGtal 2.0.0
DGtal::Bits Struct Reference

#include <DGtal/base/Bits.h>

Static Public Member Functions

template<typename T>
static std::string bitString (T value, unsigned nbBits=0)
 Bits Structs grouping all the functions of this tiny library for bitwise calculation.
template<typename T>
static T mask (unsigned nthBit)
template<typename T>
static bool getBit (T key, unsigned nthBit)
template<typename T>
static T firstSetBit (T val)
template<typename T>
static T firstUnsetBit (T val)
template<typename T>
static unsigned int nbSetBits (T val)
static unsigned int nbSetBits (DGtal::uint8_t val)
static unsigned int nbSetBits (DGtal::uint16_t val)
static unsigned int nbSetBits (DGtal::uint32_t val)
static unsigned int nbSetBits (DGtal::uint64_t val)
static unsigned int indexInSetBits (DGtal::uint8_t n, unsigned int b)
static unsigned int indexInSetBits (DGtal::uint16_t n, unsigned int b)
static unsigned int indexInSetBits (DGtal::uint32_t n, unsigned int b)
static unsigned int indexInSetBits (DGtal::uint64_t n, unsigned int b)
static unsigned int leastSignificantBit (DGtal::uint8_t n)
static unsigned int leastSignificantBit (DGtal::uint16_t n)
static unsigned int leastSignificantBit (DGtal::uint32_t n)
static unsigned int leastSignificantBit (DGtal::uint64_t n)
static unsigned int mostSignificantBit (DGtal::uint8_t n)
static unsigned int mostSignificantBit (DGtal::uint16_t n)
static unsigned int mostSignificantBit (DGtal::uint32_t n)
static unsigned int mostSignificantBit (DGtal::uint64_t n)

Static Public Attributes

static const DGtal::uint8_t myBitCount [256]
static const DGtal::uint8_t myLSB [256]
static const DGtal::uint8_t myMSB [256]
static const DGtal::uint8_t myIndexInSetBits [8][256]

Detailed Description

Definition at line 38 of file Bits.h.

Member Function Documentation

◆ bitString()

template<typename T>
std::string DGtal::Bits::bitString ( T value,
unsigned nbBits = 0 )
inlinestatic

Bits Structs grouping all the functions of this tiny library for bitwise calculation.

Returns a string containing value's bits. Mainly designed for debugging purposes.

Parameters
valueThe value that you need to dipslay as a bit string.
nbBitsnumber of bits to be displayed. If equal to 0, the number of bits will correspond to the size of the type T.

Definition at line 56 of file Bits.h.

57 {
58 std::string bitStr;
59
60 // if the requested number of bit is 0, use the size of the data type instead
61 if(nbBits == 0) nbBits = sizeof(T)*8;
62 int i = (int)(std::min((DGtal::int64_t)sizeof(T)*8-1, (DGtal::int64_t)nbBits-1));
63
64 for(; i>=0; i--)
65 {
66 T mask = ((T)1) << i; // if you take these parenthesis out,
67 // a mountain of incredible runtime
68 // errors will jump on you.(I warned
69 // ya !)
70 if(value & mask)
71 bitStr += "1" ;
72 else
73 bitStr += "0" ;
74 }
75 return bitStr;
76 }
std::int64_t int64_t
signed 94-bit integer.
Definition BasicTypes.h:73
static T mask(unsigned nthBit)
Definition Bits.h:87

References mask().

Referenced by test_get(), test_setVal(), and testMorton().

◆ firstSetBit()

template<typename T>
T DGtal::Bits::firstSetBit ( T val)
inlinestatic

Returns a value such that only its bit corresponding to the first (least important) set bit of val, is set.

Definition at line 107 of file Bits.h.

108 {
109 return ( (val & -val) | (val & (~val + 1)) );
110 }

◆ firstUnsetBit()

template<typename T>
T DGtal::Bits::firstUnsetBit ( T val)
inlinestatic

Returns a value such that only its bit corresponding to the first (least important) unset bit of val, is set.

Definition at line 118 of file Bits.h.

119 {
120 return ~val & (val + 1);
121 }

◆ getBit()

template<typename T>
bool DGtal::Bits::getBit ( T key,
unsigned nthBit )
inlinestatic

Returns the state of key's nthBit bit.

Definition at line 96 of file Bits.h.

97 {
98 return ( key & mask<T>(nthBit) );
99 }

References mask().

◆ indexInSetBits() [1/4]

unsigned int DGtal::Bits::indexInSetBits ( DGtal::uint16_t n,
unsigned int b )
inlinestatic

Specialization for uint16_t.

Set bits are numbered from 1 to x when reading the word from the least significant to the most significant bit. This number is the index of bit b in the number n.

Parameters
ba bit index in 0..15
na number in 0..65535
Returns
this index or 0 if the bit is not set.

Definition at line 223 of file Bits.h.

224 {
225 ASSERT( b < 16 );
226 if ( b < 8 )
227 return indexInSetBits( static_cast<DGtal::uint8_t>( n & 0xff ), b );
228 else
229 {
230 unsigned int idx = indexInSetBits( static_cast<DGtal::uint8_t>( n >> 8 ), b - 8 );
231 return ( idx == 0 )
232 ? 0 // bit b is not set
233 : idx + nbSetBits( static_cast<DGtal::uint8_t>( n & 0xff ) );
234 }
235 }
std::uint8_t uint8_t
unsigned 8-bit integer.
Definition BasicTypes.h:57
static unsigned int indexInSetBits(DGtal::uint8_t n, unsigned int b)
Definition Bits.h:205
static unsigned int nbSetBits(T val)
Definition Bits.h:128

References indexInSetBits(), and nbSetBits().

◆ indexInSetBits() [2/4]

unsigned int DGtal::Bits::indexInSetBits ( DGtal::uint32_t n,
unsigned int b )
inlinestatic

Specialization for uint32_t.

Set bits are numbered from 1 to x when reading the word from the least significant to the most significant bit. This number is the index of bit b in the number n.

Parameters
ba bit index in 0..31
na number in 0..2^32-1
Returns
this index or 0 if the bit is not set.

Definition at line 249 of file Bits.h.

250 {
251 ASSERT( b < 32 );
252 if ( b < 16 )
253 return indexInSetBits( static_cast<DGtal::uint16_t>( n & 0xffff ), b );
254 else
255 {
256 unsigned int idx = indexInSetBits( static_cast<DGtal::uint16_t>( n >> 16 ), b - 16 );
257 return ( idx == 0 )
258 ? 0 // bit b is not set
259 : idx + nbSetBits( static_cast<DGtal::uint16_t>( n & 0xffff ) );
260 }
261 }
std::uint16_t uint16_t
unsigned 16-bit integer.
Definition BasicTypes.h:59

References indexInSetBits(), and nbSetBits().

◆ indexInSetBits() [3/4]

unsigned int DGtal::Bits::indexInSetBits ( DGtal::uint64_t n,
unsigned int b )
inlinestatic

Specialization for uint64_t.

Set bits are numbered from 1 to x when reading the word from the least significant to the most significant bit. This number is the index of bit b in the number n.

Parameters
ba bit index in 0..63
na number in 0..2^64-1
Returns
this index or 0 if the bit is not set.

Definition at line 275 of file Bits.h.

276 {
277 ASSERT( b < 64 );
278 if ( b < 32 )
279 return indexInSetBits( static_cast<DGtal::uint32_t>( n & 0xffffffffLL ), b );
280 else
281 {
282 unsigned int idx = indexInSetBits( static_cast<DGtal::uint32_t>( n >> 32 ), b - 32 );
283 return ( idx == 0 )
284 ? 0 // bit b is not set
285 : idx + nbSetBits( static_cast<DGtal::uint32_t>( n & 0xffffffffLL ) );
286 }
287 }
std::uint32_t uint32_t
unsigned 32-bit integer.
Definition BasicTypes.h:62

References indexInSetBits(), and nbSetBits().

◆ indexInSetBits() [4/4]

unsigned int DGtal::Bits::indexInSetBits ( DGtal::uint8_t n,
unsigned int b )
inlinestatic

Specialization for uint8_t.

Set bits are numbered from 1 to x when reading the word from the least significant to the most significant bit. This number is the index of bit b in the number n.

Parameters
ba bit index in 0..7
na number in 0..255
Returns
this index or 0 if the bit is not set.

Definition at line 205 of file Bits.h.

206 {
207 ASSERT( b < 8 );
208 return myIndexInSetBits[ b ][ n ];
209 }
static const DGtal::uint8_t myIndexInSetBits[8][256]
Definition Bits.h:409

References myIndexInSetBits.

Referenced by indexInSetBits(), indexInSetBits(), indexInSetBits(), and main().

◆ leastSignificantBit() [1/4]

unsigned int DGtal::Bits::leastSignificantBit ( DGtal::uint16_t n)
inlinestatic
Parameters
nany number
Returns
the index (0..) of the least significant bit.

Definition at line 305 of file Bits.h.

306 {
307 return ( n & 0xff )
309 : 8 + leastSignificantBit( (DGtal::uint8_t) (n>>8) );
310 }
static unsigned int leastSignificantBit(DGtal::uint8_t n)
Definition Bits.h:295

References leastSignificantBit().

◆ leastSignificantBit() [2/4]

unsigned int DGtal::Bits::leastSignificantBit ( DGtal::uint32_t n)
inlinestatic
Parameters
nany number
Returns
the index (0..) of the least significant bit.

Definition at line 317 of file Bits.h.

318 {
319 return ( n & 0xffff )
321 : 16 + leastSignificantBit( (DGtal::uint16_t) (n>>16) );
322 }

References leastSignificantBit().

◆ leastSignificantBit() [3/4]

unsigned int DGtal::Bits::leastSignificantBit ( DGtal::uint64_t n)
inlinestatic
Parameters
nany number
Returns
the index (0..) of the least significant bit.

Definition at line 329 of file Bits.h.

330 {
331 return ( n & 0xffffffffLL )
333 : 32 + leastSignificantBit( (DGtal::uint32_t) (n>>32) );
334 }

References leastSignificantBit().

◆ leastSignificantBit() [4/4]

unsigned int DGtal::Bits::leastSignificantBit ( DGtal::uint8_t n)
inlinestatic
Parameters
nany number
Returns
the index (0..) of the least significant bit.

Definition at line 295 of file Bits.h.

296 {
297 return myLSB[ n ];
298 }
static const DGtal::uint8_t myLSB[256]
Definition Bits.h:393

References myLSB.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::const_iterator::increment(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::iterator::increment(), leastSignificantBit(), leastSignificantBit(), and leastSignificantBit().

◆ mask()

template<typename T>
T DGtal::Bits::mask ( unsigned nthBit)
inlinestatic

Returns an value which bits are of the form 0..010..0 with the nthBit equal to 1.

Definition at line 87 of file Bits.h.

88 {
89 return static_cast<T>(static_cast<T>(1) << nthBit);
90 }

Referenced by bitString(), and getBit().

◆ mostSignificantBit() [1/4]

unsigned int DGtal::Bits::mostSignificantBit ( DGtal::uint16_t n)
inlinestatic
Parameters
nany number
Returns
the index (..0) of the mot significant bit.

Definition at line 351 of file Bits.h.

352 {
353 return ( n & 0xff00 )
354 ? 8 + mostSignificantBit( (DGtal::uint8_t) (n>>8) )
355 : mostSignificantBit((DGtal::uint8_t) (n) );
356 }
static unsigned int mostSignificantBit(DGtal::uint8_t n)
Definition Bits.h:341

References mostSignificantBit().

◆ mostSignificantBit() [2/4]

unsigned int DGtal::Bits::mostSignificantBit ( DGtal::uint32_t n)
inlinestatic
Parameters
nany number
Returns
the index (..0) of the most significant bit.

Definition at line 363 of file Bits.h.

364 {
365 return ( n & 0xffff0000 )
366 ? 16 + mostSignificantBit( (DGtal::uint16_t) (n>>16) )
367 : mostSignificantBit((DGtal::uint16_t) (n) );
368 }

References mostSignificantBit().

◆ mostSignificantBit() [3/4]

unsigned int DGtal::Bits::mostSignificantBit ( DGtal::uint64_t n)
inlinestatic
Parameters
nany number
Returns
the index (..0) of the most significant bit.

Definition at line 375 of file Bits.h.

376 {
377 return ( n & 0xffffffff00000000LL )
378 ? 32 + mostSignificantBit( (DGtal::uint32_t) (n>>32) )
379 : mostSignificantBit((DGtal::uint32_t) (n) );
380 }

References mostSignificantBit().

◆ mostSignificantBit() [4/4]

unsigned int DGtal::Bits::mostSignificantBit ( DGtal::uint8_t n)
inlinestatic
Parameters
nany number
Returns
the index (..0) of the most significant bit.

Definition at line 341 of file Bits.h.

342 {
343 return myMSB[ n ];
344 }
static const DGtal::uint8_t myMSB[256]
Definition Bits.h:398

References myMSB.

Referenced by mostSignificantBit(), mostSignificantBit(), mostSignificantBit(), and DGtal::functions::roundToUpperPowerOfTwo().

◆ nbSetBits() [1/5]

unsigned int DGtal::Bits::nbSetBits ( DGtal::uint16_t val)
inlinestatic

Overloading for type uint16_t Returns the amount of set bits in val.

Definition at line 156 of file Bits.h.

157 {
158#ifdef TRACE_BITS
159 std::cerr << "unsigned int nbSetBits( DGtal::uint16_t val )" << std::endl;
160#endif
161 return nbSetBits( static_cast<DGtal::uint8_t>( val & 0xff ) )
162 + nbSetBits( static_cast<DGtal::uint8_t>( val >> 8 ) );
163 }

References nbSetBits().

◆ nbSetBits() [2/5]

unsigned int DGtal::Bits::nbSetBits ( DGtal::uint32_t val)
inlinestatic

Overloading for type uint32_t Returns the amount of set bits in val.

Definition at line 170 of file Bits.h.

171 {
172#ifdef TRACE_BITS
173 std::cerr << "unsigned int nbSetBits( DGtal::uint32_t val )" << std::endl;
174#endif
175 return nbSetBits( static_cast<DGtal::uint16_t>( val & 0xffff ) )
176 + nbSetBits( static_cast<DGtal::uint16_t>( val >> 16 ) );
177 }

References nbSetBits().

◆ nbSetBits() [3/5]

unsigned int DGtal::Bits::nbSetBits ( DGtal::uint64_t val)
inlinestatic

Overloading for type uint64_t Returns the amount of set bits in val.

Definition at line 184 of file Bits.h.

185 {
186#ifdef TRACE_BITS
187 std::cerr << "unsigned int nbSetBits( DGtal::uint64_t val )" << std::endl;
188#endif
189 return nbSetBits( static_cast<DGtal::uint32_t>( val & 0xffffffffLL ) )
190 + nbSetBits( static_cast<DGtal::uint32_t>( val >> 32 ) );
191 }

References nbSetBits().

◆ nbSetBits() [4/5]

unsigned int DGtal::Bits::nbSetBits ( DGtal::uint8_t val)
inlinestatic

Overloading for type uint8_t Returns the amount of set bits in val.

Definition at line 143 of file Bits.h.

144 {
145#ifdef TRACE_BITS
146 std::cerr << "unsigned int nbSetBits( DGtal::uint8_t val )" << std::endl;
147#endif
148 return myBitCount[ val ];
149 }
static const DGtal::uint8_t myBitCount[256]
Definition Bits.h:388

References myBitCount.

◆ nbSetBits() [5/5]

template<typename T>
unsigned int DGtal::Bits::nbSetBits ( T val)
inlinestatic

Returns the amount of set bits in val.

Definition at line 128 of file Bits.h.

129 {
130#ifdef TRACE_BITS
131 std::cerr << "unsigned int nbSetBits(T val)" << std::endl;
132#endif
133 unsigned int i = 0;
134 for ( ; val; ++i) {val ^= val & -val; }
135 return i;
136 }

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual >::erase(), indexInSetBits(), indexInSetBits(), indexInSetBits(), main(), nbSetBits(), nbSetBits(), and nbSetBits().

Field Documentation

◆ myBitCount

DGtal::uint8_t DGtal::Bits::myBitCount
inlinestaticconstexpr

Lookup table for counting the number of bits set to 1 in a byte. ( Taken from STL <bitset> )

Definition at line 388 of file Bits.h.

Referenced by nbSetBits().

◆ myIndexInSetBits

DGtal::uint8_t DGtal::Bits::myIndexInSetBits
inlinestaticconstexpr

Usage: myIndexInSetBits[ b ][ n ]

  • b in 0..7
  • n in 0..255 Set bits are numbered from 1 to x when reading the word from the least significant to the most significant bit. This number is the index of bit b in the number n. return this index or 0 if the bit is not set.

Definition at line 409 of file Bits.h.

Referenced by indexInSetBits().

◆ myLSB

DGtal::uint8_t DGtal::Bits::myLSB
inlinestaticconstexpr

Lookup table for finding the least significant bit.

Lookup table for finding the least significant bit.

NB: Can also be obtained with:

 

Definition at line 393 of file Bits.h.

Referenced by leastSignificantBit().

◆ myMSB

DGtal::uint8_t DGtal::Bits::myMSB
inlinestaticconstexpr

Lookup table for finding the least significant bit.

Lookup table for finding the least significant bit.

NB: Can also be obtained with:

 

Definition at line 398 of file Bits.h.

Referenced by mostSignificantBit().


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