DGtal  0.9.2
Bits.h
1 
17 #pragma once
18 
28 #ifndef BITS_HPP
29 #define BITS_HPP
30 
31 #include <string>
32 #include "DGtal/base/Common.h"
33 #include "DGtal/base/BasicFunctors.h"
34 #include "DGtal/base/ExpressionTemplates.h"
35 
36 namespace DGtal
37 {
38 
39  struct Bits
40  {
56  template <typename T>
57  static std::string bitString(T value, unsigned nbBits = 0)
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  }
79 
80 
81  // ---------------------------------------------------------------------
82  // Other functions
83  // ---------------------------------------------------------------------
84 
88  template<typename T>
89  static inline T mask(unsigned nthBit)
90  {
91  return static_cast<T>(static_cast<T>(1) << nthBit);
92  }
93 
97  template <typename T>
98  static inline bool getBit(T key, unsigned nthBit)
99  {
100  return ( key & mask<T>(nthBit) );
101  }
102 
103 
108  template <typename T>
109  static inline T firstSetBit(T val)
110  {
111  return ( (val & -val) | (val & (~val + 1)) );
112  }
113 
114 
119  template <typename T>
120  static inline T firstUnsetBit(T val)
121  {
122  return ~val & (val + 1);
123  }
124 
125 
129  template <typename T>
130  static inline unsigned int nbSetBits(T val)
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  }
139 
144  static inline
145  unsigned int nbSetBits( DGtal::uint8_t val )
146  {
147 #ifdef TRACE_BITS
148  std::cerr << "unsigned int nbSetBits( DGtal::uint8_t val )" << std::endl;
149 #endif
150  return myBitCount[ val ];
151  }
152 
157  static inline
158  unsigned int nbSetBits( DGtal::uint16_t val )
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  }
166 
171  static inline
172  unsigned int nbSetBits( DGtal::uint32_t val )
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  }
180 
185  static inline
186  unsigned int nbSetBits( DGtal::uint64_t val )
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  }
194 
206  static inline
207  unsigned int indexInSetBits( DGtal::uint8_t n, unsigned int b )
208  {
209  ASSERT( b < 8 );
210  return myIndexInSetBits[ b ][ n ];
211  }
212 
224  static inline
225  unsigned int indexInSetBits( DGtal::uint16_t n, unsigned int b )
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  }
238 
250  static inline
251  unsigned int indexInSetBits( DGtal::uint32_t n, unsigned int b )
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  }
264 
276  static inline
277  unsigned int indexInSetBits( DGtal::uint64_t n, unsigned int b )
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  }
290 
291 
296  static inline
298  {
299  return myLSB[ n ];
300  }
301 
306  static inline
308  {
309  return ( n & 0xff )
311  : 8 + leastSignificantBit( (DGtal::uint8_t) (n>>8) );
312  }
313 
318  static inline
320  {
321  return ( n & 0xffff )
323  : 16 + leastSignificantBit( (DGtal::uint16_t) (n>>16) );
324  }
325 
330  static inline
332  {
333  return ( n & 0xffffffffLL )
335  : 32 + leastSignificantBit( (DGtal::uint32_t) (n>>32) );
336  }
337 
342  static inline
344  {
345  return myMSB[ n ];
346  }
347 
352  static inline
354  {
355  return ( n & 0xff00 )
356  ? 8 + mostSignificantBit( (DGtal::uint8_t) (n>>8) )
358  }
359 
364  static inline
366  {
367  return ( n & 0xffff0000 )
368  ? 16 + mostSignificantBit( (DGtal::uint16_t) (n>>16) )
370  }
371 
376  static inline
378  {
379  return ( n & 0xffffffff00000000LL )
380  ? 32 + mostSignificantBit( (DGtal::uint32_t) (n>>32) )
382  }
383 
384 
385 
390  static const DGtal::uint8_t myBitCount[ 256 ];
391 
395  static const DGtal::uint8_t myLSB[ 256 ];
396 
400  static const DGtal::uint8_t myMSB[ 256 ];
401 
411  static const DGtal::uint8_t myIndexInSetBits[ 8 ][ 256 ];
412 
413 
414  };//struct
415 }
416 #endif
boost::uint32_t uint32_t
unsigned 32-bit integer.
Definition: BasicTypes.h:63
static unsigned int nbSetBits(T val)
Definition: Bits.h:130
static unsigned int nbSetBits(DGtal::uint16_t val)
Definition: Bits.h:158
static T firstSetBit(T val)
Definition: Bits.h:109
static unsigned int indexInSetBits(DGtal::uint16_t n, unsigned int b)
Definition: Bits.h:225
static unsigned int leastSignificantBit(DGtal::uint8_t n)
Definition: Bits.h:297
static T firstUnsetBit(T val)
Definition: Bits.h:120
static const DGtal::uint8_t myLSB[256]
Definition: Bits.h:395
static unsigned int mostSignificantBit(DGtal::uint16_t n)
Definition: Bits.h:353
static unsigned int leastSignificantBit(DGtal::uint64_t n)
Definition: Bits.h:331
static unsigned int nbSetBits(DGtal::uint64_t val)
Definition: Bits.h:186
static const DGtal::uint8_t myMSB[256]
Definition: Bits.h:400
static const DGtal::uint8_t myBitCount[256]
Definition: Bits.h:390
static T mask(unsigned nthBit)
Definition: Bits.h:89
static const DGtal::uint8_t myIndexInSetBits[8][256]
Definition: Bits.h:411
static unsigned int mostSignificantBit(DGtal::uint8_t n)
Definition: Bits.h:343
static unsigned int leastSignificantBit(DGtal::uint16_t n)
Definition: Bits.h:307
static unsigned int nbSetBits(DGtal::uint32_t val)
Definition: Bits.h:172
static unsigned int leastSignificantBit(DGtal::uint32_t n)
Definition: Bits.h:319
boost::uint16_t uint16_t
unsigned 16-bit integer.
Definition: BasicTypes.h:61
static unsigned int indexInSetBits(DGtal::uint32_t n, unsigned int b)
Definition: Bits.h:251
static unsigned int nbSetBits(DGtal::uint8_t val)
Definition: Bits.h:145
DGtal is the top-level namespace which contains all DGtal functions and types.
static unsigned int mostSignificantBit(DGtal::uint64_t n)
Definition: Bits.h:377
boost::uint8_t uint8_t
unsigned 8-bit integer.
Definition: BasicTypes.h:59
static std::string bitString(T value, unsigned nbBits=0)
Bits Structs grouping all the functions of this tiny library for bitwise calculation.
Definition: Bits.h:57
static bool getBit(T key, unsigned nthBit)
Definition: Bits.h:98
boost::uint64_t uint64_t
unsigned 64-bit integer.
Definition: BasicTypes.h:65
static unsigned int indexInSetBits(DGtal::uint8_t n, unsigned int b)
Definition: Bits.h:207
boost::int64_t int64_t
signed 94-bit integer.
Definition: BasicTypes.h:74
static unsigned int indexInSetBits(DGtal::uint64_t n, unsigned int b)
Definition: Bits.h:277
static unsigned int mostSignificantBit(DGtal::uint32_t n)
Definition: Bits.h:365