bitVector.cpp

Go to the documentation of this file.

/************************************************************************
* CVS version control block - do not edit manually
*  $RCSfile: bitVector.cpp,v $
*  $Revision: 1.1 $
*  $Date: 2003/09/05 04:20:11 $
*  $Source: /usr/sci/projects/chimera/cvsroot/arbeit/gutz/mathGutz/bitVector.cpp,v $
*************************************************************************
* Aaron Lefohn
* Userid:       lefohn
* Email:        lefohn@eng.utah.edu
**************************************************************************
* This is the implementation for BitVector and BitRef classes
*************************************************************************/

#include "bitVector.h"
#include <assert.h>

namespace gutz {

using namespace std;

const uint g_BITS_PER_WORD = 8 * sizeof(uint);
const uint g_POW_OF_2_BITS_PER_WORD = log(g_BITS_PER_WORD) / log(2);

// ********* BitRef Class *************
BitRef::BitRef( uint* wordPtr, uint bitNum) //Constructor 
{
  m_wordPtr = wordPtr;
  m_mask    = bitMask(bitNum);
}

BitRef::BitRef( const BitRef& rhs)
{
  m_wordPtr = rhs.m_wordPtr;
  m_mask    = rhs.m_mask;
}

//Test whether bit is TRUE or FALSE 
bool BitRef::operator()() const
{
  return ((*m_wordPtr) & m_mask) > 0;
}

//Assignment to other BitRef
BitRef& BitRef::operator=(const BitRef& rhs)
{
  if(this==&rhs) {return *this;}

  m_wordPtr = rhs.m_wordPtr;
  m_mask    = rhs.m_mask;
  
  return *this;
} 

//Set value 
bool BitRef::operator=(const bool bVal)
{
  if(bVal) {
    (*m_wordPtr) |= m_mask;
  }
  else {
    (*m_wordPtr) &= ~m_mask;
  }
  
  return bVal;
}

// ********* BitVector Class *************
//Constructors

// Create uninitialized BitVec of 'size' 
BitVector::BitVector(const int numBits)
{
  uint numWords = bits2Words(numBits);
  m_vec = arrayo1ui(numWords, (int)0);
  m_numBits = numBits;
}

// Create BitVec of 'size', with all elts init'd to 'initVal' 
BitVector::BitVector(const int numBits, const bool initVal)
{
  m_vec = arrayo1ui( bits2Words(numBits), (int)0 );
  m_numBits = numBits;

  //Set bits to all 1's or all 0's
  uint bits = fillWord(initVal);
  
  for(uint i=0; i<m_vec.size(); i++) {
    m_vec[i] = bits;
  }
}

// Create a BitVec from a 0/1 character string
// NOTE: Will have an assertion failure if non-0/1 chars are found in char string
BitVector::BitVector(const string& bitStr)
{
  m_numBits = bitStr.size();
  m_vec = arrayo1ui( bits2Words(m_numBits), (int)0 );

  uint bitNum = 0;
  for(uint w=0; w < m_vec.size(); w++) {//Words (array elts)
    uint bitWord = 0;
    
    for(uint b=0; (b < g_BITS_PER_WORD) && (bitNum < m_numBits); b++) {//Bits in each word
      char aBit = bitStr[bitNum];
      assert( aBit=='0' || aBit=='1' );
      
      uint valMask = (aBit == '0') ? 0 : bitMask(b);
      bitWord |= valMask; // Add the new bit to the bitWord
      bitNum++;
    }
    m_vec[w] = bitWord;   // Add the new bitWord to the array
  }
      
  /* This should work, but is "might be" less efficient than the code above
  for(uint i=0; i < m_numBits; i++) {
    char aBit = bitString[i];
    assert( aBit=='0' || aBit=='1' );
    (*this)[i] = aBit=='0' ? false : true;
  }
  */
}

// Create BitVec from single word
BitVector::BitVector( uint word )
{
        m_vec = arrayo1ui( 1, word );
        m_numBits = 8 * sizeof(uint);
}

// Create BitVec from array of unsigned ints
BitVector::BitVector( const arrayw1ui& data )      
{
        m_vec = arrayo1ui( data.size(), (int)0 );
        m_numBits = 8 * sizeof(uint) * data.size();

        for(uint i=0; i < m_vec.size(); i++) {
                m_vec[i] = data[i];
        }
}

// Create BitVec from array of unsigned bytes
BitVector::BitVector(const arrayw1ub& data )
{
        m_numBits = 8 * data.size();
        uint numWords = bits2Words(m_numBits);
        m_vec = arrayo1ui( numWords, (int)0 );

        int b = 0;//Byte index
        for(uint i=0; i < m_vec.size(); i++) {
                uint word = 0;
                word |= data[b+0];
                word |= data[b+1];
                word |= data[b+2];
                word |= data[b+3];
                b+=4;

                m_vec[i] = word;
        }
}

//Copy Constructor
BitVector::BitVector(const BitVector& rhs)
{
  m_vec = rhs.m_vec;
  m_numBits = rhs.m_numBits;
}

BitVector::~BitVector()
{}

// Copy a bit vector
BitVector& BitVector::operator= (const BitVector& rhs)
{
  if(this==&rhs) {return *this;}

  m_vec = rhs.m_vec;
  m_numBits = rhs.m_numBits;

  return *this;
}

// Fill a bit_vector with value 
BitVector& BitVector::operator= (const bool value)
{
  uint bits = fillWord(value);
  
  for(uint i=0; i<m_vec.size(); i++) {
    m_vec[i] = bits;
  }

  return *this;
}

// Fill bit vector with a word-sized value
BitVector& BitVector::operator= (const uint valWord)
{
        for(uint i=0; i < m_vec.size(); i++) {
                m_vec[i] = valWord;
        }

        return *this;
}

// Boolean NOT on a bit vector in-place 
BitVector& BitVector::not()
{
  for(uint i=0; i < m_vec.size(); i++) {
    m_vec[i] = ~(m_vec[i]);
  }

  return *this;
}

// Boolean AND operation on two bit vectors in-place 
BitVector& BitVector::operator&= (const BitVector& rhs)
{
  assert( this->size() == rhs.size() );
  for(uint i=0; i < m_vec.size(); i++) {
    m_vec[i] &= rhs.m_vec[i];
  }

  return *this;
}

// Boolean OR operation on two bit vectors in-place 
BitVector& BitVector::operator|= (const BitVector& rhs)
{
  assert( this->size() == rhs.size() );
  for(uint i=0; i < m_vec.size(); i++) {
    m_vec[i] |= rhs.m_vec[i];
  }

  return *this;
}

// Boolean XOR operation on two bit vectors in-place 
BitVector& BitVector::operator^= (const BitVector& rhs)
{
  assert( this->size() == rhs.size() );
  for(uint i=0; i < m_vec.size(); i++) {
    m_vec[i] ^= rhs.m_vec[i];
  }

  return *this;
}

// Difference set on two bit vectors in-place (creates 1 temporary)
BitVector& BitVector::operator-= (const BitVector& rhs)
{
  assert( this->size() == rhs.size() );

  return ((*this) &= ~rhs);
}

// Do all elts in bitVec have value 'u'?
// NOTE: This is NOT an optimized operation!
bool BitVector::operator== (const bool u)
{
  //old version
  bool equal=true;

  for(uint i=0; i<m_numBits && equal; i++) {
    bool val = (*this)[i]();
    equal = (val == u);
  }
  

  /* (CURRENTLY BROKEN)
  //new version
  bool equal = true;
  uint inVal = fillWord(u);

  for(uint i=0; i<m_vec.size() && equal; i++) {
    if( (m_vec[i] & inVal) != m_vec[i] ) {
      equal = false;
    }
  }*/

  return equal;
}

// Check if no bit of vector has the value u
// NOTE: This is NOT an optimized operation!
// TODO: Optimize this function
bool BitVector::operator!= (const bool u)
{
  bool notEqual=false;

  for(uint i=0; i<m_numBits && (notEqual == false); i++) {
    bool val = (*this)[i]();
    notEqual = (val != u);
  }
  return notEqual;
}

// Returns number of true bits in vector
uint BitVector::numTrueBits() const
{
/*  uint tCount = 0;         // # of true bits we found
  uint trueVal = UINT_MAX;

  for(uint w=0; w < m_vec.size(); w++) {
    uint word = m_vec[w];
    
    if( (trueVal & word) != 0 ) { //If the word contains some 1's, then find the individual bits
      uint mask = 1 << (g_BITS_PER_WORD-1);

      for(uint b=0; b < g_BITS_PER_WORD; b++) {
        if( (word & mask) != 0 ) {// If bit is 1
          tCount++;
        }
        mask >>= 1;
      }
    }
  }
*/
        uint tCount = 0;//# of true bit found in the bitVec
        for(uint w=0; w < m_vec.size(); w++) {//Loop over words 
                tCount += numOnesInWord( m_vec[w] );
        }

        return tCount;
}

//TODO: Make this general for true or false?
// Return a vector of bitIndices for all true bits in the bitVector
// Note: Despite the similarity between this 'numTrueBits', they
//       are separte for the sake of optimizations
vector<uint> BitVector::trueBits() const
{
        vector<uint> trueIndices(m_numBits); // Make it too big to avoid resizing inside loop
        uint tCount = 0;                     // # of true bits we found
        uint trueVal = UINT_MAX;

        for(uint w=0; w < m_vec.size(); w++) {
                uint word = m_vec[w];
    
                if( (trueVal & word) != 0 ) { //If the word contains some 1's, then find the individual bits
                        uint mask = 1 << (g_BITS_PER_WORD-1);

                        for(uint b=0; b < g_BITS_PER_WORD; b++) {
                                if( (word & mask) != 0 ) {// If bit is 1
                                        trueIndices[tCount] = w * g_BITS_PER_WORD + b;
                                        tCount++;
                                }
                                mask >>= 1;
                        }
                }
        }

        trueIndices.resize(tCount);
        return trueIndices;
}

// Non-memory-allocating version of 'trueBits()'
void BitVector::trueBits( arrayw1ui& trueIndices ) const
{
        assert( trueIndices.size() >= m_numBits );
        trueIndices.reshape( trueIndices.size() );
        
        uint tCount = 0;                     // # of true bits we found
        uint trueVal = UINT_MAX;

        for(uint w=0; w < m_vec.size(); w++) {
                uint word = m_vec[w];

                if( (trueVal & word) != 0 ) { //If the word contains some 1's, then find the individual bits
                        uint mask = 1 << (g_BITS_PER_WORD-1);

                        // TODO: Could speed this up by checking if byte is 0 before checking bits
                        for(uint b=0; b < g_BITS_PER_WORD; b++) {
                                if( (word & mask) != 0 ) {// If bit is 1
                                        trueIndices[tCount] = w * g_BITS_PER_WORD + b;
                                        tCount++;
                                }
                                mask >>= 1;
                        }
                }
        }

        trueIndices.reshape(tCount);
}

/* TODO: THis is WRONG!!
// Return a vector of bitIndices for all false bits in the bitVector
vector<uint> BitVector::falseBits() const
{
  vector<uint> falseIndices(m_numBits); // Make it too big to avoid resizing inside loop. Fixed after loop.
  uint fCount = 0;                      // # of false bits we found

  for(uint w=0; w < m_vec.size(); w++) {
    uint word = m_vec[w];
    
    if( (word | 0) != 0 ) { //If the word contains some 1's, then find the individual bits
      uint mask = 1 << (g_BITS_PER_WORD-1);

      for(uint b=0; b < g_BITS_PER_WORD; b++) {
        if( (word & mask) != 0 ) {// If bit is 1
          trueIndices[tCount] = w * g_BITS_PER_WORD + b;
          tCount++;
        }
        mask >>= 1;
      }
    }
  }

  trueIndices.resize(tCount);
  return trueIndices;
}*/

// Compare two bit vectors for EQUALITY
bool BitVector::operator== (const BitVector& bv)
{
  assert( this->size() == bv.size() );
  bool equal=true;

  for(uint i=0; i<m_vec.size() && equal; i++) {
    equal = (m_vec[i] == bv.m_vec[i]);
  }

  return equal;
}

// Compare two bit vectors for INEQUALITY 
bool BitVector::operator!= (const BitVector& bv)
{
  assert( this->size() == bv.size() );
  bool equal = false;
  for(uint i=0; i<m_vec.size() && !equal; i++) {
    equal = (m_vec[i] != bv.m_vec[i]);
  }

  return equal;
}

// Boolean NOT on a bit vector 
BitVector operator~ (const BitVector& rhs)
{
  BitVector newVec = rhs;
  return newVec.not();
}

//For all ops that need 2 BitVectors as args, both vecs MUST be same length. Assertion failure if not same size.
// Boolean AND operation on two bit vectors
BitVector operator& (const BitVector& lhs, const BitVector& rhs)
{
  assert( lhs.size() == rhs.size() );
  BitVector newVec = lhs;
  return newVec &= rhs;
}

// Boolean OR operation on two bit vectors 
BitVector operator| (const BitVector& lhs, const BitVector& rhs)
{
  assert( lhs.size() == rhs.size() );
  BitVector newVec = lhs;
  return newVec |= rhs;
}

// Boolean XOR operation on two bit vectors 
BitVector operator^ (const BitVector& lhs, const BitVector& rhs)
{
  assert( lhs.size() == rhs.size() );
  BitVector newVec = lhs;
  return newVec ^= rhs;
}

// Difference set on two bit vectors (creates 2 temporaries)
BitVector operator- (const BitVector& lhs, const BitVector& rhs)
{
  assert( lhs.size() == rhs.size() );
  return lhs & (~rhs);
}

ostream &operator<<(ostream& ostr, const BitVector& bv)
{
  uint bitNum=0;
  for(uint w=0; w < bv.m_vec.size(); w++) {
    uint num = bv.m_vec[w];
    
    /*for(int b=g_BITS_PER_WORD - 1; (b>=0) && (bitNum<bv.m_numBits); b--) {
          if( modPowOf2( b+1, 2 ) == 0) { ostr << " ";}//if((b+1)%4 == 0) { ostr << " ";}
          ostr << getBinary(num, b);
      bitNum++;
     }*/
        for(int b=0; b < g_BITS_PER_WORD && (bitNum < bv.m_numBits); b++) {//(b>=0) && (bitNum<bv.m_numBits); b--) {
          if( modPowOf2( b, 2 ) == 0) { ostr << " ";}//if((b+1)%4 == 0) { ostr << " ";}
          ostr << getBinary(num, b);
      bitNum++;
     }
  }
  
  return ostr;
}

ostream &operator<<(ostream & ostr, const BitRef& bv)
{
  ostr << (((*bv.m_wordPtr) & bv.m_mask) > 0);
  return ostr;
}

} // End of namespace gutz

---

Send questions, comments, and bug reports to: