DGtal  1.5.beta
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(), and test_setVal().

◆ 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]

◆ 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) )
357  : mostSignificantBit((DGtal::uint8_t) (n) );
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) )
369  : mostSignificantBit((DGtal::uint16_t) (n) );
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) )
381  : mostSignificantBit((DGtal::uint32_t) (n) );
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: