bitstring Class Reference

Non-template and faster implementation of std::bitset. More...

#include <bitstring.h>

Collaboration diagram for bitstring:

Classes
class	reference

Public Types
typedef unsigned long	_ul

Public Member Functions
	bitstring ()
	bitstring (size_t length)
	bitstring (const bitstring &b)
	~bitstring ()
void	reset (size_t length)
void	reset ()
	Set all bits to 0. More...
_ul *	getword_atPos (size_t pos) const
_ul *	getword_atIdx (size_t index) const
size_t	size () const
size_t	nb_words () const
bool	at (size_t word, unsigned long bitmask) const
reference	operator[] (size_t pos)
bool	operator[] (size_t n) const
bitstring &	operator= (const bitstring &b)
bitstring &	operator&= (const bitstring &x)
bitstring &	operator|= (const bitstring &x)
bitstring &	operator^= (const bitstring &x)
bitstring	operator~ (void)
bitstring	operator& (const bitstring &x)
bitstring	operator| (const bitstring &x)
bitstring	operator^ (const bitstring &x)
unsigned int	local_popcountl (_ul wd) const
	Counts number of one's in a word using hardware POPCNT when available, falling back to a byte-table lookup otherwise. More...
unsigned int	count ()
	Count number of set bits. More...
unsigned int	count (size_t from, size_t to)
	Count set bits in the range [from, to). More...
unsigned int	count_and (const bitstring &mask) const
	Masked popcount: count set bits in (this AND mask). More...
unsigned int	count_xor (const bitstring &other) const
	Fused XOR popcount: count set bits in (this XOR other). More...
unsigned int	count_xor_and (const bitstring &other, const bitstring &mask) const
	Fused XOR + mask popcount: count set bits in ((this XOR other) AND mask). More...
unsigned int	count_and_and (const bitstring &other, const bitstring &mask) const
	Fused AND + mask popcount: count set bits in ((this AND other) AND mask). More...
void	set (size_t n)
	Set a bit to 1. More...
void	set (size_t n, bool x)
	Set a bit to 0 or 1. More...
void	flip (size_t n)
	Flip the bit at n. More...
void	set_data (_ul *srce, size_t nbwrd)
	Copy bits from an array of unsigned long words. More...
void	copy (const bitstring &b)
	Unchecked copy, assumes we have sames sizes. More...
void	copy (const bitstring &b, size_t word_pos)
	Copy one word. More...
void	copy (const bitstring &b, size_t from, size_t to)
	Copy a delimited sequence block. More...
std::string	to_string () const
std::string	to_string (size_t from, size_t to) const
void	print (size_t from, size_t to) const
void	print () const

Private Attributes
size_t	_size
	Number of bits in the sequence. More...
size_t	_words
	Number of _ul-long Words necessary to hold the _size bits. More...
_ul *	_data
	The sequence. More...

Static Private Attributes
static unsigned char	_bit_count [256]

Friends
class	reference

Detailed Description

Non-template and faster implementation of std::bitset.

Member Typedef Documentation

_ul

typedef unsigned long bitstring::_ul

Constructor & Destructor Documentation

bitstring() [1/3]

bitstring::bitstring ( )

inline

: _size(0), _words(0), _data(0) {}

bitstring() [2/3]

bitstring::bitstring ( size_t  length )

inline

  : _size(length), _words( BITSET_WORDS(length) ), _data(0)
  {
    _data = new _ul [_words];
    memset(_data, 0, _words * sizeof(_ul));
  }

References _data, and _words.

bitstring() [3/3]

bitstring::bitstring ( const bitstring &  b )

inline

  : _size(b._size), _words(b._words), _data(0)
  {
    _data = new _ul [_words];
    memcpy(_data, b._data, _words * sizeof(_ul));
  }

References _data, and _words.

~bitstring()

bitstring::~bitstring ( )

inline

{if(_data != NULL) delete [] _data;}

References _data.

Member Function Documentation

at()

bool bitstring::at ( size_t  word, unsigned long  bitmask  ) const

inline

  {
    return bool( _data[ word ] & bitmask );
  }

References _data.

copy() [1/3]

void bitstring::copy ( const bitstring &  b )

inline

Unchecked copy, assumes we have sames sizes.

  { memcpy(_data, b._data, _words * sizeof(_ul)); }

References _data, and _words.

Referenced by TTQuanti_diallelic_bitstring_no_pleio::copy_sequence_block(), TTQuanti_diallelic_bitstring_full_pleio::copy_sequence_block(), TTQuanti_diallelic_bitstring_var_pleio::copy_sequence_block(), TTQuanti_diallelic_bitstring_no_pleio_epistasis::copy_sequence_block(), TTQuanti_diallelic_bitstring_full_pleio_epistasis::copy_sequence_block(), TProtoBDMI::inherit_low(), TProtoDeletMutations_bitstring::inherit_low(), TTNeutralGenes_bitstring::inherit_low(), TT_BDMI::operator=(), TTDeletMutations_bitstring::operator=(), TTQuanti_diallelic_bitstring::operator=(), TTQuanti_diallelic_bitstring::set_bit_sequence(), TT_BDMI::set_sequence(), and TTDeletMutations_bitstring::set_sequence().

Here is the caller graph for this function:

copy() [2/3]

void bitstring::copy ( const bitstring &  b, size_t  from, size_t  to  )

inline

Copy a delimited sequence block.

  {
    assert(to <= _size);
    
    if(to != from) { // only if we do have something to copy
 
      size_t start_w, end_w, start_l, end_l;
      _ul mask, tmpl;
 
      start_w = from / BITS_PER_WORD;
      end_w = to / BITS_PER_WORD;
 
      start_l = from % BITS_PER_WORD;
      end_l = to % BITS_PER_WORD;
 
      if(start_w != end_w) {
        //copy wihtin first word:
        mask =  (MASK << start_l);
 
        _data[ start_w ]   &= ~mask;
        tmpl = b._data[ start_w ] & mask;
 
        _data[ start_w ] |= tmpl;
 
        //copy words in-between:
        size_t k = start_w + 1;
 
        memcpy(&_data[k], &b._data[k], (end_w - k)*sizeof(_ul));
 
        //copy within last word; skip when 'to' is word-aligned (end_l == 0),
        //since end_w then sits one past the last valid word and there's
        //nothing left to copy beyond what the memcpy above already did.
        if (end_l != 0) {
          mask =  (MASK >> (BITS_PER_WORD - end_l) );
 
          _data[ end_w ]   &= ~mask;
          tmpl = b._data[ end_w ] & mask;
 
          _data[ end_w ] |= tmpl;
        }
 
      } else {
        //bits to copy are within a word:
        mask =  (MASK << start_l) & (MASK >> (BITS_PER_WORD - end_l) );
 
        _data[ start_w ] &= ~mask;
        tmpl = b._data[ start_w ] & mask;
 
        _data[ start_w ] |= tmpl;
 
      }
    }
  }

References _data, _size, BITS_PER_WORD, and MASK.

copy() [3/3]

void bitstring::copy ( const bitstring &  b, size_t  word_pos  )

inline

Copy one word.

  { _data[ word_pos ] = b._data[ word_pos ]; }

References _data.

count() [1/2]

unsigned int bitstring::count ( )

inline

Count number of set bits.

  {
    unsigned int cnt = 0;
    
    for(size_t i = 0; i < _words; i++)
      cnt += local_popcountl(_data[i]);
    
    return cnt;
  }

References _data, _words, and local_popcountl().

Referenced by TTQuanti_diallelic_bitstring_no_pleio::get_additive_genotype_equal_effects(), TTDeletMutations_bitstring::set_nb_hmz_mutations(), TTDeletMutations_bitstring::set_nb_htz_mutations(), and TTDeletMutations_bitstring::set_nb_mutations().

Here is the caller graph for this function:

count() [2/2]

unsigned int bitstring::count ( size_t  from, size_t  to  )

inline

Count set bits in the range [from, to).

  {
      assert(from < to && to <= _size);
 
      unsigned int cnt = 0;
      size_t start_w = from / BITS_PER_WORD;
      size_t end_w   = to   / BITS_PER_WORD;
      size_t start_l = from % BITS_PER_WORD;
      size_t end_l   = to   % BITS_PER_WORD;
 
      if (start_w == end_w) {
          _ul mask = (MASK << start_l) & (MASK >> (BITS_PER_WORD - end_l));
          return local_popcountl( _ul(_data[start_w] & mask) );
      }
 
      // first partial word
      cnt += local_popcountl(_data[start_w] & (MASK << start_l));
 
      // full words in between
      for (size_t i = start_w + 1; i < end_w; ++i)
          cnt += local_popcountl(_data[i]);
 
      // last partial word
      if (end_l > 0)
          cnt += local_popcountl(_data[end_w] & (MASK >> (BITS_PER_WORD - end_l)));
 
      return cnt;
  }

References _data, _size, BITS_PER_WORD, local_popcountl(), and MASK.

count_and()

unsigned int bitstring::count_and ( const bitstring &  mask ) const

inline

Masked popcount: count set bits in (this AND mask).

  {
    unsigned int cnt = 0;
    for (size_t i = 0; i < _words; ++i)
      cnt += local_popcountl(_data[i] & mask._data[i]);
    return cnt;
  }

References _data, _words, and local_popcountl().

Referenced by TTQuanti_diallelic_bitstring_no_pleio::get_additive_genotype(), TTQuanti_diallelic_bitstring_full_pleio::get_additive_genotype(), TTQuanti_diallelic_bitstring_var_pleio::get_additive_genotype(), and TTDeletMutations_bitstring::set_value().

Here is the caller graph for this function:

count_and_and()

unsigned int bitstring::count_and_and ( const bitstring &  other, const bitstring &  mask  ) const

inline

Fused AND + mask popcount: count set bits in ((this AND other) AND mask).

  {
    unsigned int cnt = 0;
    for (size_t i = 0; i < _words; ++i)
      cnt += local_popcountl((_data[i] & other._data[i]) & mask._data[i]);
    return cnt;
  }

References _data, _words, and local_popcountl().

Referenced by TTQuanti_diallelic_bitstring_no_pleio::get_dominant_genotype(), TTQuanti_diallelic_bitstring_full_pleio::get_dominant_genotype(), and TTQuanti_diallelic_bitstring_var_pleio::get_dominant_genotype().

Here is the caller graph for this function:

count_xor()

unsigned int bitstring::count_xor ( const bitstring &  other ) const

inline

Fused XOR popcount: count set bits in (this XOR other).

  {
    unsigned int cnt = 0;
    for (size_t i = 0; i < _words; ++i)
      cnt += local_popcountl(_data[i] ^ other._data[i]);
    return cnt;
  }

References _data, _words, and local_popcountl().

Referenced by TTDeletMutations_bitstring::set_value(), and TTNeutralGenesSH::setHo().

Here is the caller graph for this function:

count_xor_and()

unsigned int bitstring::count_xor_and ( const bitstring &  other, const bitstring &  mask  ) const

inline

Fused XOR + mask popcount: count set bits in ((this XOR other) AND mask).

  {
    unsigned int cnt = 0;
    for (size_t i = 0; i < _words; ++i)
      cnt += local_popcountl((_data[i] ^ other._data[i]) & mask._data[i]);
    return cnt;
  }

References _data, _words, and local_popcountl().

Referenced by TTQuanti_diallelic_bitstring_no_pleio::get_dominant_genotype(), TTQuanti_diallelic_bitstring_full_pleio::get_dominant_genotype(), and TTQuanti_diallelic_bitstring_var_pleio::get_dominant_genotype().

Here is the caller graph for this function:

flip()

void bitstring::flip ( size_t  n )

inline

Flip the bit at n.

{_data[n / BITS_PER_WORD] ^= (1UL << (n % BITS_PER_WORD));}

References _data, and BITS_PER_WORD.

Referenced by TTQuanti_diallelic_bitstring_no_pleio::init_sequence(), TTQuanti_diallelic_bitstring_full_pleio::init_sequence(), TTQuanti_diallelic_bitstring_var_pleio::init_sequence(), TTQuanti_diallelic_bitstring_no_pleio_epistasis::init_sequence(), TTQuanti_diallelic_bitstring_full_pleio_epistasis::init_sequence(), TT_BDMI::mutate_diplo(), TT_BDMI::mutate_haplo(), TTQuanti_diallelic_bitstring::mutate_inplace(), TTDeletMutations_bitstring::mutate_noredraw(), and TTQuanti_diallelic_bitstring::set_allele_value().

Here is the caller graph for this function:

getword_atIdx()

_ul* bitstring::getword_atIdx ( size_t  index ) const

inline

  { return &_data[ index ]; }

References _data.

Referenced by TTQuanti_diallelic_bitstring_no_pleio::get_dominant_genotype(), TTNeutralGenes_bitstring::inherit(), TProtoDeletMutations_bitstring::inherit_free(), TTDeletMutations_bitstring::set_counts_and_bitstrings(), TTNeutralGenesSH::setAlleleTables(), TTDeletMutBitstrSH::setDeletStats(), TTNeutralGenesSH::setFstat_bitstring(), TTNeutralGenesSH::setFstatWeirCockerham_bitstring(), TTNeutralGenesSH::setHo2(), TT_BDMI::store_data(), TTDeletMutations_bitstring::store_data(), TTQuanti_diallelic_bitstring::store_data(), TTDeletMutations_bitstring::viability_epist_continuous(), and TTDeletMutations_bitstring::viability_multi_continuous().

Here is the caller graph for this function:

getword_atPos()

_ul* bitstring::getword_atPos ( size_t  pos ) const

inline

  { return &_data[ pos / BITS_PER_WORD ]; }

References _data, and BITS_PER_WORD.

Referenced by bitstring::reference::reference().

Here is the caller graph for this function:

local_popcountl()

unsigned int bitstring::local_popcountl ( _ul  wd ) const

inline

Counts number of one's in a word using hardware POPCNT when available, falling back to a byte-table lookup otherwise.

  {
    unsigned char* c = (unsigned char*)&wd;
    unsigned short cnt = 0;
 
    for(unsigned int i = 0; i < sizeof(_ul); i++)
      cnt += _bit_count[ (unsigned int)c[i] ];
 
    return (unsigned int) cnt;
  }

References _bit_count.

Referenced by count(), count_and(), count_and_and(), count_xor(), and count_xor_and().

Here is the caller graph for this function:

nb_words()

size_t bitstring::nb_words ( ) const

inline

{return _words;}

References _words.

Referenced by TTNeutralGenes_bitstring::inherit(), TProtoDeletMutations_bitstring::inherit_free(), TT_BDMI::retrieve_data(), TTDeletMutations_bitstring::retrieve_data(), TTQuanti_diallelic_bitstring::retrieve_data(), TTDeletMutations_bitstring::set_counts_and_bitstrings(), TTNeutralGenesSH::setAlleleTables(), TTDeletMutBitstrSH::setDeletStats(), TTNeutralGenesSH::setHo2(), TT_BDMI::store_data(), TTDeletMutations_bitstring::store_data(), TTQuanti_diallelic_bitstring::store_data(), TTDeletMutations_bitstring::viability_epist_continuous(), and TTDeletMutations_bitstring::viability_multi_continuous().

Here is the caller graph for this function:

operator&()

bitstring bitstring::operator& ( const bitstring &  x )

inline

  {
    bitstring result(*this);
    result &= x;
    return result;
  }

operator&=()

bitstring& bitstring::operator&= ( const bitstring &  x )

inline

  {
    for (size_t i = 0; i < _words; i++)
      _data[i] &= x._data[i];
    return *this;
  }

References _data, and _words.

operator=()

bitstring& bitstring::operator= ( const bitstring &  b )

inline

  {
    _size = b._size;
    if (_words != b._words) {
      _words = b._words;
      if(_data != NULL) delete [] _data;
      _data = new _ul [_words];
    }
    memcpy(_data, b._data, _words * sizeof(_ul));
    return *this;
  }

References _data, _size, and _words.

operator[]() [1/2]

bool bitstring::operator[] ( size_t  n ) const

inline

  { return bool( _data[ n / BITS_PER_WORD ] & ( 1UL << ( n % BITS_PER_WORD ) ) ); }

References _data, and BITS_PER_WORD.

operator[]() [2/2]

reference bitstring::operator[] ( size_t  pos )

inline

  { return reference(*this, pos); }

References reference.

operator^()

bitstring bitstring::operator^ ( const bitstring &  x )

inline

  {
    bitstring result(*this);
    result ^= x;
    return result;
  }

operator^=()

bitstring& bitstring::operator^= ( const bitstring &  x )

inline

  {
    for (size_t i = 0; i < _words; i++)
      _data[i] ^= x._data[i];
    return *this;
  }

References _data, and _words.

operator|()

bitstring bitstring::operator| ( const bitstring &  x )

inline

  {
    bitstring result(*this);
    result |= x;
    return result;
  }

operator|=()

bitstring& bitstring::operator|= ( const bitstring &  x )

inline

  {
    for (size_t i = 0; i < _words; i++)
      _data[i] |= x._data[i];
    return *this;
  }

References _data, and _words.

operator~()

bitstring bitstring::operator~ ( void  )

inline

  {
    for (size_t i = 0; i < _words; i++)
      _data[i] = ~(_data[i]);
    return *this;
  }

References _data, and _words.

print() [1/2]

void bitstring::print ( ) const

inline

  {
    for(unsigned int i = 0; i < _size; ++i)
      std::cout<< (bool)(_data[ i / BITS_PER_WORD ] & ( 1UL << ( i % BITS_PER_WORD ) ));
    std::cout<<std::endl;
  }

References _data, _size, and BITS_PER_WORD.

print() [2/2]

void bitstring::print ( size_t  from, size_t  to  ) const

inline

  {
    assert(from < to && to < _size+1);
    for(unsigned int i = from; i < to; ++i)
      std::cout<< (bool)(_data[ i / BITS_PER_WORD ] & ( 1UL << ( i % BITS_PER_WORD ) ));
    std::cout<<std::endl;
  }

References _data, _size, and BITS_PER_WORD.

reset() [1/2]

void bitstring::reset ( )

inline

Set all bits to 0.

  { for(unsigned int i = 0; i < _words; i++) _data[i] = 0UL; }

References _data, and _words.

reset() [2/2]

void bitstring::reset ( size_t  length )

inline

  {
    _size = length;
 
    _words = BITSET_WORDS(length);
 
    if(_data) delete [] _data;
 
    _data = new _ul [_words];
    memset(_data, 0UL, _words * sizeof(_ul));
  }

References _data, _size, _words, and BITSET_WORDS.

Referenced by TTDeletMutBitstrFH::FHread(), TT_BDMI::init(), TTNeutralGenes_bitstring::init(), TTQuanti_diallelic_bitstring::init(), TT_BDMI::init_sequence(), TTDeletMutations_bitstring::init_sequence(), TTNeutralGenes_bitstring::init_sequence(), TTQuanti_diallelic_bitstring_no_pleio::init_sequence(), TTQuanti_diallelic_bitstring_full_pleio::init_sequence(), TTQuanti_diallelic_bitstring_var_pleio::init_sequence(), TTQuanti_diallelic_bitstring_no_pleio_epistasis::init_sequence(), TTQuanti_diallelic_bitstring_full_pleio_epistasis::init_sequence(), and TT_BDMI::reset().

Here is the caller graph for this function:

set() [1/2]

void bitstring::set ( size_t  n )

inline

Set a bit to 1.

{_data[n / BITS_PER_WORD] |= (1UL << (n % BITS_PER_WORD));}

References _data, and BITS_PER_WORD.

Referenced by TTDeletMutBitstrFH::FHread(), TT_BDMI::init_sequence(), TTDeletMutations_bitstring::init_sequence(), TTQuanti_diallelic_bitstring::mutate_add(), TTDeletMutations_bitstring::mutate_noredraw(), TTDeletMutations_bitstring::mutate_noredraw_noBackMutation(), TTDeletMutations_bitstring::mutate_redraw(), TTQuanti_diallelic_bitstring::set_allele_bit(), and TTDeletMutations_bitstring::set_allele_value().

Here is the caller graph for this function:

set() [2/2]

void bitstring::set ( size_t  n, bool  x  )

inline

Set a bit to 0 or 1.

                              {
    if (x)
      _data[n / BITS_PER_WORD] |= ( 1UL << ( n % BITS_PER_WORD ) );
    else
      _data[n / BITS_PER_WORD]  &= ~( 1UL << ( n % BITS_PER_WORD ) );
  }

References _data, and BITS_PER_WORD.

set_data()

void bitstring::set_data ( _ul *  srce, size_t  nbwrd  )

inline

Copy bits from an array of unsigned long words.

  { 
    //    if(nbwrd != _words) { 
    //      std::cerr<<"bitstring::set_data: different sizes in memcpy!!\n";
    //      exit(1);
    //      }
    assert(nbwrd == _words);
    memcpy(_data, srce, nbwrd * sizeof(_ul));
  }

References _data, and _words.

Referenced by TT_BDMI::retrieve_data(), TTDeletMutations_bitstring::retrieve_data(), and TTQuanti_diallelic_bitstring::retrieve_data().

Here is the caller graph for this function:

size()

size_t bitstring::size ( ) const

inline

{return _size;}

References _size.

to_string() [1/2]

std::string bitstring::to_string ( ) const

inline

  {
    const char one = '1';
    std::string result;
 
    result.assign(_size, '0');
 
    for(size_t i = 0; i < _size; ++i) {
      if(_data[ i / BITS_PER_WORD ] & ( 1UL << ( i % BITS_PER_WORD ) ))
        result[i] = one;
    }
 
    return result;
  }

References _data, _size, and BITS_PER_WORD.

to_string() [2/2]

std::string bitstring::to_string ( size_t  from, size_t  to  ) const

inline

  {
    assert(from < to && to < _size+1);
 
    const char one = '1';
 
    size_t len = to - from;
 
    std::string result;
 
    result.assign(len, '0');
 
    for(size_t i = from, s = 0; i < to && s < len; ++i, ++s) {
      if(_data[ i / BITS_PER_WORD ] & ( 1UL << ( i % BITS_PER_WORD ) ))
        result[s] = one;
    }
    return result;
  }

References _data, _size, and BITS_PER_WORD.

Friends And Related Function Documentation

reference

friend class reference

friend

Referenced by operator[]().

Member Data Documentation

_bit_count

unsigned char bitstring::_bit_count

staticprivate

Referenced by local_popcountl().

_data

_ul* bitstring::_data

private

The sequence.

Referenced by at(), bitstring(), copy(), count(), count_and(), count_and_and(), count_xor(), count_xor_and(), flip(), getword_atIdx(), getword_atPos(), operator&=(), operator=(), operator[](), operator^=(), operator|=(), operator~(), print(), reset(), set(), set_data(), to_string(), and ~bitstring().

_size

size_t bitstring::_size

private

Number of bits in the sequence.

Referenced by copy(), count(), operator=(), print(), reset(), size(), and to_string().

_words

size_t bitstring::_words

private

Number of _ul-long Words necessary to hold the _size bits.

Referenced by bitstring(), copy(), count(), count_and(), count_and_and(), count_xor(), count_xor_and(), nb_words(), operator&=(), operator=(), operator^=(), operator|=(), operator~(), reset(), and set_data().

---

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

• bitstring.h
• bitstring.cc