DGtal 1.3.0
Loading...
Searching...
No Matches
Bits.h
1
17#pragma once
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
36namespace 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
DGtal is the top-level namespace which contains all DGtal functions and types.
boost::int64_t int64_t
signed 94-bit integer.
Definition: BasicTypes.h:74
boost::uint32_t uint32_t
unsigned 32-bit integer.
Definition: BasicTypes.h:63
boost::uint16_t uint16_t
unsigned 16-bit integer.
Definition: BasicTypes.h:61
boost::uint8_t uint8_t
unsigned 8-bit integer.
Definition: BasicTypes.h:59
boost::uint64_t uint64_t
unsigned 64-bit integer.
Definition: BasicTypes.h:65
static T firstUnsetBit(T val)
Definition: Bits.h:120
static unsigned int indexInSetBits(DGtal::uint8_t n, unsigned int b)
Definition: Bits.h:207
static unsigned int indexInSetBits(DGtal::uint32_t n, unsigned int b)
Definition: Bits.h:251
static unsigned int mostSignificantBit(DGtal::uint8_t n)
Definition: Bits.h:343
static unsigned int leastSignificantBit(DGtal::uint64_t n)
Definition: Bits.h:331
static unsigned int leastSignificantBit(DGtal::uint16_t n)
Definition: Bits.h:307
static unsigned int mostSignificantBit(DGtal::uint64_t n)
Definition: Bits.h:377
static const DGtal::uint8_t myIndexInSetBits[8][256]
Definition: Bits.h:411
static unsigned int leastSignificantBit(DGtal::uint32_t n)
Definition: Bits.h:319
static unsigned int nbSetBits(T val)
Definition: Bits.h:130
static unsigned int leastSignificantBit(DGtal::uint8_t n)
Definition: Bits.h:297
static unsigned int mostSignificantBit(DGtal::uint32_t n)
Definition: Bits.h:365
static T firstSetBit(T val)
Definition: Bits.h:109
static unsigned int indexInSetBits(DGtal::uint64_t n, unsigned int b)
Definition: Bits.h:277
static unsigned int nbSetBits(DGtal::uint64_t val)
Definition: Bits.h:186
static T mask(unsigned nthBit)
Definition: Bits.h:89
static unsigned int nbSetBits(DGtal::uint8_t val)
Definition: Bits.h:145
static unsigned int mostSignificantBit(DGtal::uint16_t n)
Definition: Bits.h:353
static const DGtal::uint8_t myMSB[256]
Definition: Bits.h:400
static unsigned int nbSetBits(DGtal::uint16_t val)
Definition: Bits.h:158
static unsigned int indexInSetBits(DGtal::uint16_t n, unsigned int b)
Definition: Bits.h:225
static unsigned int nbSetBits(DGtal::uint32_t val)
Definition: Bits.h:172
static bool getBit(T key, unsigned nthBit)
Definition: Bits.h:98
static const DGtal::uint8_t myBitCount[256]
Definition: Bits.h:390
static const DGtal::uint8_t myLSB[256]
Definition: Bits.h:395
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