DGtal  0.9.3
testBits.cpp
Go to the documentation of this file.
1 
29 //#define TRACE_BITS
30 
31 #include <cstdio>
32 #include <cmath>
33 #include <iostream>
34 #include "DGtal/base/Common.h"
35 #include "DGtal/base/Bits.h"
36 
37 using namespace DGtal;
38 
39 
40 // Set bits are numbered from 1 to x when reading the word from the
41 // least significant to the most significant bit. This number is the
42 // index of bit \a b in the number \a n.
43 // return 0 if the bit is not set.
44 unsigned int index( DGtal::uint32_t n, unsigned int b )
45 {
46  int i = 0;
47  for ( ; b != 0; --b )
48  {
49  if ( n & 1 ) ++i;
50  n >>= 1;
51  }
52  return ( n & 1 ) ? i + 1 : 0;
53 }
54 
55 
56 int main()
57 {
58  unsigned int nb = 0;
59  unsigned int nbok = 0;
60  ++nb, nbok += Bits::nbSetBits( (DGtal::uint8_t)-1) == 8 ? 1 : 0;
61  ++nb, nbok += Bits::nbSetBits( (DGtal::uint16_t)-1) == 16 ? 1 : 0;
62  ++nb, nbok += Bits::nbSetBits( (DGtal::uint32_t)-1) == 32 ? 1 : 0;
63  ++nb, nbok += Bits::nbSetBits( (DGtal::uint64_t)-1) == 64 ? 1 : 0;
64  ++nb, nbok += Bits::nbSetBits( (DGtal::uint8_t)1) == 1 ? 1 : 0;
65  ++nb, nbok += Bits::nbSetBits( (DGtal::uint16_t)1) == 1 ? 1 : 0;
66  ++nb, nbok += Bits::nbSetBits( (DGtal::uint32_t)1) == 1 ? 1 : 0;
67  ++nb, nbok += Bits::nbSetBits( (DGtal::uint64_t)1) == 1 ? 1 : 0;
68  ++nb, nbok += Bits::nbSetBits( (DGtal::uint8_t)-2) == 7 ? 1 : 0;
69  ++nb, nbok += Bits::nbSetBits( (DGtal::uint16_t)-2) == 15 ? 1 : 0;
70  ++nb, nbok += Bits::nbSetBits( (DGtal::uint32_t)-2) == 31 ? 1 : 0;
71  ++nb, nbok += Bits::nbSetBits( (DGtal::uint64_t)-2) == 63 ? 1 : 0;
72 
73  for ( unsigned int i = 0; i < 100; ++i )
74  {
75  DGtal::uint16_t n = (DGtal::uint16_t) ( rand() % 65536 );
76  for ( unsigned int b = 0; b < 16; ++b )
77  ++nb, nbok += Bits::indexInSetBits( n, b ) == index( n, b ) ? 1 : 0;
78  }
79 
80  std::cerr << "(" << nbok << "/" << nb << ")" << " tests." << std::endl;
81 
82  trace.beginBlock ( "Testing speed of loop version of indexInSetBits" );
83  srand( 0 );
84  unsigned int val = 0;
85  for ( unsigned int i = 0; i < 100000; ++i )
86  {
87  DGtal::uint32_t n = (DGtal::uint32_t) rand();
88  for ( unsigned int b = 0; b < 32; ++b )
89  val += index( n, b );
90  }
91  trace.info() << "- checksum = " << val << std::endl;
92  trace.endBlock();
93 
94  trace.beginBlock ( "Testing speed of look-up table version of indexInSetBits" );
95  srand( 0 );
96  unsigned int val2 = 0;
97  for ( unsigned int i = 0; i < 100000; ++i )
98  {
99  DGtal::uint32_t n = (DGtal::uint32_t) rand();
100  for ( unsigned int b = 0; b < 32; ++b )
101  val2 += Bits::indexInSetBits( n, b );
102  }
103  trace.info() << "- checksum = " << val2 << std::endl;
104  trace.endBlock();
105  ++nb, nbok += val == val2 ? 1 : 0;
106  return ( nb == nbok ) ? 0 : 1;
107 }
void beginBlock(const std::string &keyword="")
boost::uint32_t uint32_t
unsigned 32-bit integer.
Definition: BasicTypes.h:63
unsigned int index(DGtal::uint32_t n, unsigned int b)
Definition: testBits.cpp:44
static unsigned int nbSetBits(T val)
Definition: Bits.h:130
Trace trace
Definition: Common.h:137
srand(0)
double endBlock()
boost::uint16_t uint16_t
unsigned 16-bit integer.
Definition: BasicTypes.h:61
DGtal is the top-level namespace which contains all DGtal functions and types.
boost::uint8_t uint8_t
unsigned 8-bit integer.
Definition: BasicTypes.h:59
int main()
Definition: testBits.cpp:56
std::ostream & info()
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