DGtal::Bits Struct Reference

#include <DGtal/base/Bits.h>

Static Public Member Functions
template<typename T >
static std::string	bitString (T value, unsigned nbBits=0)
	Bits Structs grouping all the functions of this tiny library for bitwise calculation. More...
template<typename T >
static T	mask (unsigned nthBit)
template<typename T >
static bool	getBit (T key, unsigned nthBit)
template<typename T >
static T	firstSetBit (T val)
template<typename T >
static T	firstUnsetBit (T val)
template<typename T >
static unsigned int	nbSetBits (T val)
static unsigned int	nbSetBits (DGtal::uint8_t val)
static unsigned int	nbSetBits (DGtal::uint16_t val)
static unsigned int	nbSetBits (DGtal::uint32_t val)
static unsigned int	nbSetBits (DGtal::uint64_t val)
static unsigned int	indexInSetBits (DGtal::uint8_t n, unsigned int b)
static unsigned int	indexInSetBits (DGtal::uint16_t n, unsigned int b)
static unsigned int	indexInSetBits (DGtal::uint32_t n, unsigned int b)
static unsigned int	indexInSetBits (DGtal::uint64_t n, unsigned int b)
static unsigned int	leastSignificantBit (DGtal::uint8_t n)
static unsigned int	leastSignificantBit (DGtal::uint16_t n)
static unsigned int	leastSignificantBit (DGtal::uint32_t n)
static unsigned int	leastSignificantBit (DGtal::uint64_t n)
static unsigned int	mostSignificantBit (DGtal::uint8_t n)
static unsigned int	mostSignificantBit (DGtal::uint16_t n)
static unsigned int	mostSignificantBit (DGtal::uint32_t n)
static unsigned int	mostSignificantBit (DGtal::uint64_t n)

Static Public Attributes
static const DGtal::uint8_t	myBitCount [256]
static const DGtal::uint8_t	myLSB [256]
static const DGtal::uint8_t	myMSB [256]
static const DGtal::uint8_t	myIndexInSetBits [8][256]

Detailed Description

Definition at line 39 of file Bits.h.

Member Function Documentation

bitString()

template<typename T >

static std::string DGtal::Bits::bitString ( T  value, unsigned  nbBits = 0  )

inlinestatic

Bits Structs grouping all the functions of this tiny library for bitwise calculation.

Todo:

Check that T is CInteger.

Returns a string containing value's bits. Mainly designed for debugging purposes.

Parameters

value	The value that you need to dipslay as a bit string.
nbBits	number of bits to be displayed. If equal to 0, the number of bits will correspond to the size of the type T.

Definition at line 57 of file Bits.h.

    {
      std::string bitStr;
      /*functors::Min<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;
    }

Referenced by test_get(), test_setVal(), and testMorton().

firstSetBit()

template<typename T >

static T DGtal::Bits::firstSetBit ( T  val )

inlinestatic

Returns a value such that only its bit corresponding to the first (least important) set bit of val, is set.

Definition at line 109 of file Bits.h.

    {
      return ( (val & -val) | (val & (~val + 1)) );
    }

firstUnsetBit()

template<typename T >

static T DGtal::Bits::firstUnsetBit ( T  val )

inlinestatic

Returns a value such that only its bit corresponding to the first (least important) unset bit of val, is set.

Definition at line 120 of file Bits.h.

    {
      return ~val & (val + 1);
    }

getBit()

template<typename T >

static bool DGtal::Bits::getBit ( T  key, unsigned  nthBit  )

inlinestatic

Returns the state of key's nthBit bit.

Definition at line 98 of file Bits.h.

    {
      return ( key & mask<T>(nthBit) );
    }

indexInSetBits() [1/4]

static unsigned int DGtal::Bits::indexInSetBits ( DGtal::uint16_t  n, unsigned int  b  )

inlinestatic

Specialization for uint16_t.

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 b in the number n.

Parameters

b	a bit index in 0..15
n	a number in 0..65535

Returns

this index or 0 if the bit is not set.

Definition at line 225 of file Bits.h.

    {
      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 ) );
        }
    }

References indexInSetBits(), and nbSetBits().

indexInSetBits() [2/4]

static unsigned int DGtal::Bits::indexInSetBits ( DGtal::uint32_t  n, unsigned int  b  )

inlinestatic

Specialization for uint32_t.

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 b in the number n.

Parameters

b	a bit index in 0..31
n	a number in 0..2^32-1

Returns

this index or 0 if the bit is not set.

Definition at line 251 of file Bits.h.

    {
      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 ) );
        }
    }

References indexInSetBits(), and nbSetBits().

indexInSetBits() [3/4]

static unsigned int DGtal::Bits::indexInSetBits ( DGtal::uint64_t  n, unsigned int  b  )

inlinestatic

Specialization for uint64_t.

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 b in the number n.

Parameters

b	a bit index in 0..63
n	a number in 0..2^64-1

Returns

this index or 0 if the bit is not set.

Definition at line 277 of file Bits.h.

    {
      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 ) );
        }
    }

References indexInSetBits(), and nbSetBits().

indexInSetBits() [4/4]

static unsigned int DGtal::Bits::indexInSetBits ( DGtal::uint8_t  n, unsigned int  b  )

inlinestatic

Specialization for uint8_t.

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 b in the number n.

Parameters

b	a bit index in 0..7
n	a number in 0..255

Returns

this index or 0 if the bit is not set.

Definition at line 207 of file Bits.h.

    {
      ASSERT( b < 8 );
      return myIndexInSetBits[ b ][ n ];
    }

References myIndexInSetBits.

Referenced by indexInSetBits(), and main().

leastSignificantBit() [1/4]

static unsigned int DGtal::Bits::leastSignificantBit ( DGtal::uint16_t  n )

inlinestatic

Parameters

n	any number

Returns

the index (0..) of the least significant bit.

Definition at line 307 of file Bits.h.

    {
      return ( n & 0xff ) 
        ? leastSignificantBit( (DGtal::uint8_t) n )
        : 8 + leastSignificantBit( (DGtal::uint8_t) (n>>8) );
    }

References leastSignificantBit().

leastSignificantBit() [2/4]

static unsigned int DGtal::Bits::leastSignificantBit ( DGtal::uint32_t  n )

inlinestatic

Parameters

n	any number

Returns

the index (0..) of the least significant bit.

Definition at line 319 of file Bits.h.

    {
      return ( n & 0xffff ) 
        ? leastSignificantBit( (DGtal::uint16_t) n )
        : 16 + leastSignificantBit( (DGtal::uint16_t) (n>>16) );
    }

References leastSignificantBit().

leastSignificantBit() [3/4]

static unsigned int DGtal::Bits::leastSignificantBit ( DGtal::uint64_t  n )

inlinestatic

Parameters

n	any number

Returns

the index (0..) of the least significant bit.

Definition at line 331 of file Bits.h.

    {
      return ( n & 0xffffffffLL ) 
        ? leastSignificantBit( (DGtal::uint32_t) n )
        : 32 + leastSignificantBit( (DGtal::uint32_t) (n>>32) );
    }

References leastSignificantBit().

leastSignificantBit() [4/4]

static unsigned int DGtal::Bits::leastSignificantBit ( DGtal::uint8_t  n )

inlinestatic

Parameters

n	any number

Returns

the index (0..) of the least significant bit.

Definition at line 297 of file Bits.h.

    {
      return myLSB[ n ];
    }

References myLSB.

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::const_iterator::const_iterator(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::const_iterator::increment(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::iterator::increment(), DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::iterator::iterator(), and leastSignificantBit().

mask()

template<typename T >

static T DGtal::Bits::mask ( unsigned  nthBit )

inlinestatic

Returns an value which bits are of the form 0..010..0 with the nthBit equal to 1.

Definition at line 89 of file Bits.h.

    {
      return static_cast<T>(static_cast<T>(1) << nthBit); 
    }

mostSignificantBit() [1/4]

static unsigned int DGtal::Bits::mostSignificantBit ( DGtal::uint16_t  n )

inlinestatic

Parameters

n	any number

Returns

the index (..0) of the mot significant bit.

Definition at line 353 of file Bits.h.

    {
      return ( n & 0xff00 ) 
        ? 8 + mostSignificantBit( (DGtal::uint8_t) (n>>8) )
        :  mostSignificantBit((DGtal::uint8_t) (n) );
    }

References mostSignificantBit().

mostSignificantBit() [2/4]

static unsigned int DGtal::Bits::mostSignificantBit ( DGtal::uint32_t  n )

inlinestatic

Parameters

n	any number

Returns

the index (..0) of the most significant bit.

Definition at line 365 of file Bits.h.

    {
      return ( n & 0xffff0000 ) 
        ? 16 + mostSignificantBit( (DGtal::uint16_t) (n>>16) )
        :  mostSignificantBit((DGtal::uint16_t) (n) );
    }

References mostSignificantBit().

mostSignificantBit() [3/4]

static unsigned int DGtal::Bits::mostSignificantBit ( DGtal::uint64_t  n )

inlinestatic

Parameters

n	any number

Returns

the index (..0) of the most significant bit.

Definition at line 377 of file Bits.h.

    {
      return ( n & 0xffffffff00000000LL ) 
        ? 32 + mostSignificantBit( (DGtal::uint32_t) (n>>32) )
        :  mostSignificantBit((DGtal::uint32_t) (n) );      
    }

References mostSignificantBit().

mostSignificantBit() [4/4]

static unsigned int DGtal::Bits::mostSignificantBit ( DGtal::uint8_t  n )

inlinestatic

Parameters

n	any number

Returns

the index (..0) of the most significant bit.

Definition at line 343 of file Bits.h.

    {
      return myMSB[ n ];
    }

References myMSB.

Referenced by mostSignificantBit(), and DGtal::functions::roundToUpperPowerOfTwo().

nbSetBits() [1/5]

static unsigned int DGtal::Bits::nbSetBits ( DGtal::uint16_t  val )

inlinestatic

Overloading for type uint16_t Returns the amount of set bits in val.

Definition at line 158 of file Bits.h.

    {
#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 ) );
    }

References nbSetBits().

nbSetBits() [2/5]

static unsigned int DGtal::Bits::nbSetBits ( DGtal::uint32_t  val )

inlinestatic

Overloading for type uint32_t Returns the amount of set bits in val.

Definition at line 172 of file Bits.h.

    {
#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 ) );
    }

References nbSetBits().

nbSetBits() [3/5]

static unsigned int DGtal::Bits::nbSetBits ( DGtal::uint64_t  val )

inlinestatic

Overloading for type uint64_t Returns the amount of set bits in val.

Definition at line 186 of file Bits.h.

    {
#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 ) );
    }

References nbSetBits().

nbSetBits() [4/5]

static unsigned int DGtal::Bits::nbSetBits ( DGtal::uint8_t  val )

inlinestatic

Overloading for type uint8_t Returns the amount of set bits in val.

Definition at line 145 of file Bits.h.

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

References myBitCount.

nbSetBits() [5/5]

template<typename T >

static unsigned int DGtal::Bits::nbSetBits ( T  val )

inlinestatic

Returns the amount of set bits in val.

Definition at line 130 of file Bits.h.

    {
#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;
    }

Referenced by DGtal::UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >::erase(), indexInSetBits(), main(), and nbSetBits().

Field Documentation

myBitCount

const DGtal::uint8_t DGtal::Bits::myBitCount

static

Lookup table for counting the number of bits set to 1 in a byte. ( Taken from STL <bitset> )

Definition at line 390 of file Bits.h.

Referenced by nbSetBits().

myIndexInSetBits

const DGtal::uint8_t DGtal::Bits::myIndexInSetBits

static

Usage: myIndexInSetBits[ b ][ n ]

• b in 0..7
• n in 0..255 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 b in the number n. return this index or 0 if the bit is not set.

Definition at line 411 of file Bits.h.

Referenced by indexInSetBits().

myLSB

const DGtal::uint8_t DGtal::Bits::myLSB

static

Lookup table for finding the least significant bit.

Lookup table for finding the least significant bit.

NB: Can also be obtained with:

Definition at line 395 of file Bits.h.

Referenced by leastSignificantBit().

myMSB

const DGtal::uint8_t DGtal::Bits::myMSB

static

Lookup table for finding the least significant bit.

Lookup table for finding the least significant bit.

NB: Can also be obtained with:

Definition at line 400 of file Bits.h.

Referenced by mostSignificantBit().

---

The documentation for this struct was generated from the following files:

• Bits.h
• Bits.cpp