Bits.h

#pragma once

#ifndef BITS_HPP
#define BITS_HPP

#include <string>
#include "DGtal/base/Common.h"
#include "DGtal/base/BasicFunctors.h"
#include "DGtal/base/ExpressionTemplates.h"

namespace DGtal
{
 
 

  struct Bits
  {
    template <typename T>
    static std::string bitString(T value, unsigned nbBits = 0)
    {
      std::string bitStr;
      /*MinFunctor<unsigned int> min;*/

      // if the requested number of bit is 0, use the size of the data type instead
      if(nbBits == 0) nbBits = sizeof(T)*8;
      int i = (int)(std::min((DGtal::int64_t)sizeof(T)*8-1, (DGtal::int64_t)nbBits-1));

      for(; i>=0; i--)
        {
          T mask = ((T)1) << i; // if you take these parenthesis out,
          // a mountain of incredible runtime
          // errors will jump on you.(I warned
          // ya !)
          if(value & mask)
            bitStr += "1" ;
          else
            bitStr += "0" ;
        }
      return bitStr;
    }


    // ---------------------------------------------------------------------
    //  Other functions
    // ---------------------------------------------------------------------

    template<typename T> 
    static inline T mask(unsigned nthBit)
    {
      return static_cast<T>(static_cast<T>(1) << nthBit); 
    }

    template <typename T>
    static inline bool getBit(T key, unsigned nthBit)
    {
      return ( key & mask<T>(nthBit) );
    }

  
    template <typename T>
    static inline  T firstSetBit(T val)
    {
      return ( (val & -val) | (val & (~val + 1)) );
    }


    template <typename T>
    static inline T firstUnsetBit(T val)
    {
      return ~val & (val + 1);
    }


    template <typename T>
    static inline unsigned int nbSetBits(T val)
    {
#ifdef TRACE_BITS
      std::cerr << "unsigned int nbSetBits(T val)" << std::endl;
#endif
      unsigned int i = 0;
      for ( ; val; ++i) {val ^= val & -val; }
      return i;
    }

    static inline 
    unsigned int nbSetBits( DGtal::uint8_t val )
    {
#ifdef TRACE_BITS
      std::cerr << "unsigned int nbSetBits( DGtal::uint8_t val )" << std::endl;
#endif
      return myBitCount[ val ];
    }

    static inline 
    unsigned int nbSetBits( DGtal::uint16_t val )
    {
#ifdef TRACE_BITS
      std::cerr << "unsigned int nbSetBits( DGtal::uint16_t val )" << std::endl;
#endif
      return nbSetBits( static_cast<DGtal::uint8_t>( val & 0xff ) ) 
        + nbSetBits( static_cast<DGtal::uint8_t>( val >> 8 ) );
    }

    static inline 
    unsigned int nbSetBits( DGtal::uint32_t val )
    {
#ifdef TRACE_BITS
      std::cerr << "unsigned int nbSetBits( DGtal::uint32_t val )" << std::endl;
#endif
      return nbSetBits( static_cast<DGtal::uint16_t>( val & 0xffff ) ) 
        + nbSetBits( static_cast<DGtal::uint16_t>( val >> 16 ) );
    }

    static inline 
    unsigned int nbSetBits( DGtal::uint64_t val )
    {
#ifdef TRACE_BITS
      std::cerr << "unsigned int nbSetBits( DGtal::uint64_t val )" << std::endl;
#endif
      return nbSetBits( static_cast<DGtal::uint32_t>( val & 0xffffffffLL ) ) 
        + nbSetBits( static_cast<DGtal::uint32_t>( val >> 32 ) );
    }

    static inline 
    unsigned int indexInSetBits( DGtal::uint8_t n, unsigned int b )
    {
      ASSERT( b < 8 );
      return myIndexInSetBits[ b ][ n ];
    }

    static inline 
    unsigned int indexInSetBits( DGtal::uint16_t n, unsigned int b )
    {
      ASSERT( b < 16 );
      if ( b < 8 ) 
        return indexInSetBits( static_cast<DGtal::uint8_t>( n & 0xff ), b );
      else 
        {
          unsigned int idx = indexInSetBits( static_cast<DGtal::uint8_t>( n >> 8 ), b - 8 );
          return ( idx == 0 )
            ? 0 // bit b is not set
            : idx + nbSetBits( static_cast<DGtal::uint8_t>( n & 0xff ) );
        }
    }

    static inline 
    unsigned int indexInSetBits( DGtal::uint32_t n, unsigned int b )
    {
      ASSERT( b < 32 );
      if ( b < 16 ) 
        return indexInSetBits( static_cast<DGtal::uint16_t>( n & 0xffff ), b );
      else 
        {
          unsigned int idx = indexInSetBits( static_cast<DGtal::uint16_t>( n >> 16 ), b - 16 );
          return ( idx == 0 )
            ? 0 // bit b is not set
            : idx + nbSetBits( static_cast<DGtal::uint16_t>( n & 0xffff ) );
        }
    }

    static inline 
    unsigned int indexInSetBits( DGtal::uint64_t n, unsigned int b )
    {
      ASSERT( b < 64 );
      if ( b < 32 ) 
        return indexInSetBits( static_cast<DGtal::uint32_t>( n & 0xffffffffLL ), b );
      else 
        {
          unsigned int idx = indexInSetBits( static_cast<DGtal::uint32_t>( n >> 32 ), b - 32 );
          return ( idx == 0 )
            ? 0 // bit b is not set
            : idx + nbSetBits( static_cast<DGtal::uint32_t>( n & 0xffffffffLL ) );
        }
    }

    static inline 
    unsigned int leastSignificantBit( DGtal::uint8_t n )
    {
      return myLSB[ n ];
    }

    static inline 
    unsigned int leastSignificantBit( DGtal::uint16_t n )
    {
      return ( n & 0xff ) 
        ? leastSignificantBit( (DGtal::uint8_t) n )
        : 8 + leastSignificantBit( (DGtal::uint8_t) (n>>8) );
    }

    static inline 
    unsigned int leastSignificantBit( DGtal::uint32_t n )
    {
      return ( n & 0xffff ) 
        ? leastSignificantBit( (DGtal::uint16_t) n )
        : 16 + leastSignificantBit( (DGtal::uint16_t) (n>>16) );
    }

    static inline 
    unsigned int leastSignificantBit( DGtal::uint64_t n )
    {
      return ( n & 0xffffffffLL ) 
        ? leastSignificantBit( (DGtal::uint32_t) n )
        : 32 + leastSignificantBit( (DGtal::uint32_t) (n>>32) );
    }
 
          
    static const DGtal::uint8_t myBitCount[ 256 ];

    static const DGtal::uint8_t myLSB[ 256 ];

    static const DGtal::uint8_t myIndexInSetBits[ 8 ][ 256 ];

    
  };//struct
}
#endif