DGtal 1.3.0
Loading...
Searching...
No Matches
Static Public Member Functions | Static Public Attributes
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. More...
 
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 39 of file Bits.h.

Member Function Documentation

◆ bitString()

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

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

Todo:
Check that T is CInteger.

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 57 of file Bits.h.

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

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

◆ firstSetBit()

template<typename T >
static T DGtal::Bits::firstSetBit ( 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 109 of file Bits.h.

110 {
111 return ( (val & -val) | (val & (~val + 1)) );
112 }

◆ firstUnsetBit()

template<typename T >
static T DGtal::Bits::firstUnsetBit ( 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 120 of file Bits.h.

121 {
122 return ~val & (val + 1);
123 }

◆ getBit()

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

Returns the state of key's nthBit bit.

Definition at line 98 of file Bits.h.

99 {
100 return ( key & mask<T>(nthBit) );
101 }

◆ indexInSetBits() [1/4]

static 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 225 of file Bits.h.

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

References indexInSetBits(), and nbSetBits().

◆ indexInSetBits() [2/4]

static 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 251 of file Bits.h.

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

References indexInSetBits(), and nbSetBits().

◆ indexInSetBits() [3/4]

static 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 277 of file Bits.h.

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

References indexInSetBits(), and nbSetBits().

◆ indexInSetBits() [4/4]

static 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 207 of file Bits.h.

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

References myIndexInSetBits.

Referenced by indexInSetBits(), and main().

◆ leastSignificantBit() [1/4]

static 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 307 of file Bits.h.

308 {
309 return ( n & 0xff )
311 : 8 + leastSignificantBit( (DGtal::uint8_t) (n>>8) );
312 }
DGtal is the top-level namespace which contains all DGtal functions and types.
static unsigned int leastSignificantBit(DGtal::uint8_t n)
Definition: Bits.h:297

References leastSignificantBit().

◆ leastSignificantBit() [2/4]

static 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 319 of file Bits.h.

320 {
321 return ( n & 0xffff )
323 : 16 + leastSignificantBit( (DGtal::uint16_t) (n>>16) );
324 }

References leastSignificantBit().

◆ leastSignificantBit() [3/4]

static 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 331 of file Bits.h.

332 {
333 return ( n & 0xffffffffLL )
335 : 32 + leastSignificantBit( (DGtal::uint32_t) (n>>32) );
336 }

References leastSignificantBit().

◆ leastSignificantBit() [4/4]

static unsigned int DGtal::Bits::leastSignificantBit ( DGtal::uint8_t  n)
inlinestatic

◆ mask()

template<typename T >
static 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 89 of file Bits.h.

90 {
91 return static_cast<T>(static_cast<T>(1) << nthBit);
92 }

◆ mostSignificantBit() [1/4]

static 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 353 of file Bits.h.

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

References mostSignificantBit().

◆ mostSignificantBit() [2/4]

static 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 365 of file Bits.h.

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

References mostSignificantBit().

◆ mostSignificantBit() [3/4]

static 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 377 of file Bits.h.

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

References mostSignificantBit().

◆ mostSignificantBit() [4/4]

static 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 343 of file Bits.h.

344 {
345 return myMSB[ n ];
346 }
static const DGtal::uint8_t myMSB[256]
Definition: Bits.h:400

References myMSB.

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

◆ nbSetBits() [1/5]

static 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 158 of file Bits.h.

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

References nbSetBits().

◆ nbSetBits() [2/5]

static 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 172 of file Bits.h.

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

References nbSetBits().

◆ nbSetBits() [3/5]

static 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 186 of file Bits.h.

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

References nbSetBits().

◆ nbSetBits() [4/5]

static 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 145 of file Bits.h.

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

References myBitCount.

◆ nbSetBits() [5/5]

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

Returns the amount of set bits in val.

Definition at line 130 of file Bits.h.

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

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

Field Documentation

◆ myBitCount

const DGtal::uint8_t DGtal::Bits::myBitCount
static

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

Definition at line 390 of file Bits.h.

Referenced by nbSetBits().

◆ myIndexInSetBits

const DGtal::uint8_t DGtal::Bits::myIndexInSetBits
static

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 411 of file Bits.h.

Referenced by indexInSetBits().

◆ myLSB

const DGtal::uint8_t DGtal::Bits::myLSB
static

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 395 of file Bits.h.

Referenced by leastSignificantBit().

◆ myMSB

const DGtal::uint8_t DGtal::Bits::myMSB
static

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 400 of file Bits.h.

Referenced by mostSignificantBit().


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