testBits.cpp

//#define TRACE_BITS

#include <cstdio>
#include <cmath>
#include <iostream>
#include "DGtal/base/Common.h"
#include "DGtal/base/Bits.h"

using namespace DGtal;
using namespace std;

// 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 \a b in the number \a n.
// return 0 if the bit is not set.
unsigned int index( DGtal::uint32_t n, unsigned int b )
{
  int i = 0;
  for ( ; b != 0; --b )
    {
      if ( n & 1 ) ++i;
      n >>= 1;
    }
  return ( n & 1 ) ? i + 1 : 0; 
}


int main()
{
  unsigned int nb = 0;
  unsigned int nbok = 0;
  ++nb, nbok += Bits::nbSetBits( (uint8_t)-1) == 8 ? 1 : 0;
  ++nb, nbok += Bits::nbSetBits( (uint16_t)-1) == 16 ? 1 : 0;
  ++nb, nbok += Bits::nbSetBits( (uint32_t)-1) == 32 ? 1 : 0;
  ++nb, nbok += Bits::nbSetBits( (uint64_t)-1) == 64 ? 1 : 0;
  ++nb, nbok += Bits::nbSetBits( (uint8_t)1) == 1 ? 1 : 0;
  ++nb, nbok += Bits::nbSetBits( (uint16_t)1) == 1 ? 1 : 0;
  ++nb, nbok += Bits::nbSetBits( (uint32_t)1) == 1 ? 1 : 0;
  ++nb, nbok += Bits::nbSetBits( (uint64_t)1) == 1 ? 1 : 0;
  ++nb, nbok += Bits::nbSetBits( (uint8_t)-2) == 7 ? 1 : 0;
  ++nb, nbok += Bits::nbSetBits( (uint16_t)-2) == 15 ? 1 : 0;
  ++nb, nbok += Bits::nbSetBits( (uint32_t)-2) == 31 ? 1 : 0;
  ++nb, nbok += Bits::nbSetBits( (uint64_t)-2) == 63 ? 1 : 0;

  for ( unsigned int i = 0; i < 100; ++i )
    {
      uint16_t n = (uint16_t) ( random() % 65536 ); 
      for ( unsigned int b = 0; b < 16; ++b )
        ++nb, nbok += Bits::indexInSetBits( n, b ) == index( n, b ) ? 1 : 0;
    }

  std::cerr << "(" << nbok << "/" << nb << ")" << " tests." << std::endl;

  trace.beginBlock ( "Testing speed of loop version of indexInSetBits" );
  srandom( 0 );
  unsigned int val = 0;
  for ( unsigned int i = 0; i < 100000; ++i )
    {
      uint32_t n = (uint32_t) random();
      for ( unsigned int b = 0; b < 32; ++b )
        val += index( n, b );
    }
  trace.info() << "- checksum = " << val << std::endl;
  trace.endBlock();

  trace.beginBlock ( "Testing speed of look-up table version of indexInSetBits" );
  srandom( 0 );
  unsigned int val2 = 0;
  for ( unsigned int i = 0; i < 100000; ++i )
    {
      uint32_t n = (uint32_t) random();
      for ( unsigned int b = 0; b < 32; ++b )
        val2 += Bits::indexInSetBits( n, b );
    }
  trace.info() << "- checksum = " << val2 << std::endl;
  trace.endBlock();
  ++nb, nbok += val == val2 ? 1 : 0;
  return ( nb == nbok ) ? 0 : 1;
}