BitArray.h

Go to the documentation of this file.

//-------------------------------------------------
//
//   Class: BitArray
//
//   Description: Manipulates arrays of bits
//
//
//   Author List:
//   C. Grandi
//   Modifications:
//
//
//--------------------------------------------------
#ifndef BIT_ARRAY_H_
#define BIT_ARRAY_H_

//---------------
// C++ Headers --
//---------------
#include <cassert>
#include <iostream>

//              ---------------------
//              -- Class Interface --
//              ---------------------

template <int N>
class BitArray {
public:
  class refToBit;
  friend class refToBit;

  // reference to bit class
  class refToBit {
    friend class BitArray;

    //refToBit();

  public:
    refToBit() {}
    refToBit(BitArray& b, int pos) {
      _word = &b.getWord(pos);
      _pos = getPosInWord(pos);
    }
    ~refToBit() {}

    refToBit& operator=(const int val) {
      if (val) {
        *_word |= getPosMask(_pos);
      } else {
        *_word &= ~(getPosMask(_pos));
      }
      return *this;
    }

    refToBit& operator=(const refToBit& rtb) {
      if ((*(rtb._word) & getPosMask(rtb._pos))) {
        *_word |= getPosMask(_pos);
      } else {
        *_word &= ~getPosMask(_pos);
      }
      return *this;
    }

    int operator~() const { return ((*_word) & getPosMask(_pos)) == 0; }

    operator int() const { return ((*_word) & getPosMask(_pos)) != 0; }

    refToBit& flip() {
      *_word ^= getPosMask(_pos);
      return *this;
    }

  private:
    unsigned* _word;
    int _pos;
  };

  BitArray() { this->zero(); }

  BitArray(const BitArray<N>& br) {
    for (int i = 0; i < this->nWords(); i++) {
      _data[i] = br._data[i];
    }
    this->cleanUnused();
  }
  BitArray(const char* str) {
    this->zero();
    this->assign(0, this->nBits(), str);
    this->cleanUnused();
  }
  BitArray(const char* str, const int p, const int n) {
    this->zero();
    this->assign(p, n, str);
  }
  BitArray(const unsigned i) {
    this->zero();
    _data[0] = i;  // the nBit least sign. bits are considered
    this->cleanUnused();
  }
  /*
  BitArray(const unsigned long i) { 
    this->zero();
    unsigned j = i&static_cast<unsigned long>(0xffffffff);
    _data[0] = j;                 // the nBit least sign. bits are considered
    if(this->nBits()>32) {
      j=i>>32;
      _data[1] = j;
    }
    this->cleanUnused();
  }
*/
  //  Destructor
  // ~BitArray() {}

  // Return number of bits
  inline int nBits() const { return N; }
  inline int size() const { return this->nBits(); }

  // Return number of words
  inline int nWords() const { return N / 32 + 1; }

  // Return a data word
  unsigned dataWord(const int i) const {
    assert(i >= 0 && i < this->nWords());
    return _data[i];
  }
  unsigned& dataWord(const int i) {
    assert(i >= 0 && i < this->nWords());
    return _data[i];
  }

  // Return the dataword which contains bit in position
  unsigned& getWord(const int pos) {
    assert(pos >= 0 && pos < this->nBits());
    return _data[pos / 32];
  }
  unsigned getWord(const int pos) const {
    assert(pos >= 0 && pos < this->nBits());
    return _data[pos / 32];
  }

  // Return the position inside a word given the position in bitArray
  static int getPosInWord(const int pos) {
    // assert(pos>=0&& pos<this->nBits());
    return pos % 32;
  }

  // Return the word mask for a given bit
  static unsigned getPosMask(const int pos) { return static_cast<unsigned>(1) << getPosInWord(pos); }

  // how many bits are not used (most significative bits of last word)
  int unusedBits() const {
    if (this->nBits() == 0)
      return 32;
    return 31 - ((this->nBits() - 1) % 32);
  }

  // mask to get rid of last word unused bits
  unsigned lastWordMask() const { return static_cast<unsigned>(0xffffffff) >> (this->unusedBits()); }

  // set unused bits to 0
  void cleanUnused() { _data[this->nWords() - 1] &= (this->lastWordMask()); }

  // count non 0 bits
  int count() const {
    int n = 0;
    for (int i = 0; i < this->nBits(); i++) {
      if (this->element(i))
        n++;
    }
    return n;
  }

  // true if any bit == 1
  int any() {
    int nw = this->nWords();
    int ub = unusedBits();
    if (this->dataWord(nw - 1) << ub != 0)
      return 1;
    if (nw > 1) {
      for (int iw = 0; iw < nw - 1; iw++) {
        if (this->dataWord(iw) != 0)
          return 1;
      }
    }
    return 0;
  }

  // true if any bit == 0
  int none() {
    int nw = this->nWords();
    int ub = unusedBits();
    if (this->dataWord(nw - 1) << ub != 0xffffffff)
      return 1;
    if (nw > 1) {
      for (int iw = 0; iw < nw - 1; iw++) {
        if (this->dataWord(iw) != 0xffffffff)
          return 1;
      }
    }
    return 0;
  }

  // Return i^th elemnet
  int element(const int pos) const { return (getWord(pos) & getPosMask(pos)) != static_cast<unsigned>(0); }
  inline int test(const int i) const { return element(i); }

  // Set/unset all elements
  void zero() {
    for (int i = 0; i < this->nWords(); i++) {
      _data[i] = 0x0;  // set to 0
    }
  }
  inline void reset() { zero(); }

  void one() {
    for (int i = 0; i < this->nWords(); i++) {
      _data[i] = 0xffffffff;  // set to 1
    }
  }

  // Set/unset i^th element
  void set(const int i) { getWord(i) |= getPosMask(i); }
  void unset(const int i) { getWord(i) &= ~getPosMask(i); }
  inline void reset(const int i) { this->unset(i); }

  // Set the i^th element to a given value
  inline void set(const int i, const int val) { this->assign(i, 1, val); }
  inline void set(const int i, const char* str) { this->assign(i, 1, str); }

  // Set/unset many bits to a given integer/bitArray/string
  void assign(const int p, const int n, const int val) {
    assert(p >= 0 && p + n <= this->nBits());
    // only the n least significant bits of val are considered
    for (int i = 0; i < n; i++) {
      if (val >> i & 1) {
        this->set(p + i);
      } else {
        this->unset(p + i);
      }
    }
  }
  void assign(const int p, const int n, const BitArray<N>& val) {
    assert(p >= 0 && p + n <= this->nBits());
    // only the n least significant bits of val are considered
    for (int i = 0; i < n; i++) {
      if (val.element(i)) {
        this->set(p + i);
      } else {
        this->unset(p + i);
      }
    }
  }
  void assign(const int p, const int n, const char* str) {
    assert(p >= 0 && p + n <= this->nBits());
    // only the n least significant bits of val are considered
    for (int i = 0; i < n; i++) {
      assert(str[i] == '1' || str[i] == '0');
      if (str[i] == '1') {
        this->set(p + n - i - 1);    // reading a string from left to right
      } else {                       // --> most significative bit is the one
        this->unset(p + n - i - 1);  // with lower string index
      }
    }
  }

  // Read a given range in an unsigned integer
  unsigned read(const int p, const int n) const {
    assert(p >= 0 && p + n <= this->nBits());
    assert(n <= 32);  // the output must fit in a 32 bit word
    // only the n least significant bits of val are considered
    unsigned out = 0x0;
    for (int i = 0; i < n; i++) {
      if (this->test(p + i))
        out |= 1 << i;
    }
    return out;
  }

  // Read BitArray in bytes. Returns a BitArray<8>
  BitArray<8> byte(const int i) const {
    BitArray<8> out;
    if (i >= 0 && i < 4 * this->nWords()) {
      unsigned k = (_data[i / 4] >> 8 * (i % 4)) & 0xff;
      out = k;
    }
    return out;
  }
  // Assignment
  BitArray<N>& operator=(const BitArray<N>& a) {
    if (this != &a) {
      for (int i = 0; i < this->nWords(); i++) {
        _data[i] = a._data[i];
      }
    }
    this->cleanUnused();
    return *this;
  }

  // Conversion from unsigned
  BitArray<N>& operator=(const unsigned i) {
    this->zero();
    _data[0] = i;  // the nBit least sign. bits are considered
    this->cleanUnused();
    return *this;
  }
  /*    
  // Conversion from unsigned long
  BitArray<N>& operator=(const unsigned long i) {
    this->zero();
    unsigned j = i&0xffffffff;
    _data[0] = j;                 // the nBit least sign. bits are considered
    if(this->nBits()>32) {
      j=i>>32;
      _data[1] = j;
    }
    this->cleanUnused();
    return *this;
  }
*/
  // Conversion from char
  BitArray<N>& operator=(const char* str) {
    this->zero();
    for (int i = 0; i < this->nBits(); i++) {
      assert(str[i] == '1' || str[i] == '0');
      if (str[i] == '1') {
        this->set(this->nBits() - i - 1);    // reading a string from left to right
      } else if (str[i] == '0') {            // --> most significative bit is the one
        this->unset(this->nBits() - i - 1);  // with lower string index
      } else {
        break;  // exit when find a char which is not 0 or 1
      }
    }
    this->cleanUnused();
    return *this;
  }

  // Print
  std::ostream& print(std::ostream& o = std::cout) const {
    for (int i = this->nBits() - 1; i >= 0; i--) {
      o << this->element(i);
    }
    return o;
  }

  // direct access to set/read elements
  refToBit operator[](const int pos) { return refToBit(*this, pos); }
  int operator[](const int pos) const { return element(pos); }

  // logical operators ==
  bool operator==(const BitArray<N>& a) const {
    int nw = this->nWords();
    int ub = this->unusedBits();
    if (this->dataWord(nw - 1) << ub !=  // check last word
        a.dataWord(nw - 1) << ub)
      return false;
    if (nw > 1) {
      for (int iw = 0; iw < nw - 1; iw++) {
        if (this->dataWord(iw) != a.dataWord(iw))
          return false;
      }
    }
    return true;
  }

  // logical operators <
  bool operator<(const BitArray<N>& a) const {
    int nw = this->nWords();
    int ub = this->unusedBits();
    unsigned aaa = this->dataWord(nw - 1) << ub;  // ignore unused bits
    unsigned bbb = a.dataWord(nw - 1) << ub;      // in both operands
    if (aaa < bbb) {
      return true;
    } else if (aaa > bbb) {
      return false;
    }
    if (nw > 1) {
      for (int iw = nw - 2; iw >= 0; iw--) {
        if (this->dataWord(iw) < a.dataWord(iw)) {
          return true;
        } else if (this->dataWord(iw) > a.dataWord(iw)) {
          return false;
        }
      }
    }
    return false;
  }

  // logical operators !=
  bool operator!=(const BitArray<N>& a) const { return !(a == *this); }

  // logical operators >=
  bool operator>=(const BitArray<N>& a) const { return !(*this < a); }

  // logical operators >
  bool operator>(const BitArray<N>& a) const { return !(*this < a || *this == a); }

  // logical operators <=
  bool operator<=(const BitArray<N>& a) const { return !(*this > a); }

  // non-const bit by bit negation
  BitArray<N>& flip() {
    for (int i = 0; i < this->nWords(); i++) {
      _data[i] = ~_data[i];
    }
    return *this;
  }

  // const bit by bit negation
  BitArray<N> operator~() const { return BitArray<N>(*this).flip(); }

  // bit by bit AND and assignment
  BitArray<N>& operator&=(const BitArray<N>& a) {
    for (int i = 0; i < this->nWords(); i++) {
      this->dataWord(i) &= a.dataWord(i);
    }
    return *this;
  }

  // bit by bit AND
  BitArray<N> operator&(const BitArray<N>& a) { return BitArray<N>(*this) &= a; }

  // bit by bit OR and assignment
  BitArray<N>& operator|=(const BitArray<N>& a) {
    for (int i = 0; i < this->nWords(); i++) {
      this->dataWord(i) |= a.dataWord(i);
    }
    return *this;
  }

  // bit by bit AND
  BitArray<N> operator|(const BitArray<N>& a) { return BitArray<N>(*this) |= a; }

  // bit by bit XOR and assignment
  BitArray<N>& operator^=(const BitArray<N>& a) {
    for (int i = 0; i < this->nWords(); i++) {
      this->dataWord(i) ^= a.dataWord(i);
    }
    return *this;
  }

  // bit by bit XOR
  BitArray<N> operator^(const BitArray<N>& a) { return BitArray<N>(*this) ^= a; }

  // left shift and assignment
  BitArray<N>& operator<<=(const int n) {
    assert(n >= 0 && n < this->nBits());
    if (n == 0)
      return *this;
    int i = 0;
    for (i = this->nBits() - 1; i >= n; i--)
      this->set(i, this->element(i - n));
    for (i = n - 1; i >= 0; i--)
      this->unset(i);
    return *this;
  }

  // left shift
  BitArray<N> operator<<(const int n) { return BitArray<N>(*this) <<= n; }

  // right shift and assignment
  BitArray<N>& operator>>=(const int n) {
    assert(n >= 0 && n < this->nBits());
    if (n == 0)
      return *this;
    int i = 0;
    for (i = 0; i < this->nBits() - n; i++)
      this->set(i, this->element(i + n));
    for (i = this->nBits() - n; i < this->nBits(); i++)
      this->unset(i);
    return *this;
  }

  // right shift
  BitArray<N> operator>>(const int n) { return BitArray<N>(*this) >>= n; }

  // sum and assignment
  BitArray<N>& operator+=(const BitArray<N>& a) {
    int rep = 0;
    int sum = 0;
    for (int i = 0; i < this->nBits(); i++) {
      sum = this->element(i) ^ rep;
      rep = this->element(i) & rep;
      this->set(i, sum ^ a.element(i));
      rep |= (sum & a.element(i));
    }
    return *this;
  }

  // sum
  BitArray<N> operator+(const BitArray<N>& a) { return BitArray<N>(*this) += a; }

  // postfix increment
  BitArray<N>& operator++(int) {
    int i = 0;
    while (i < this->nBits() && this->element(i) == 1) {
      this->unset(i);
      i++;
    }
    if (i < this->nBits())
      this->set(i);
    return *this;
  }

  // const 2 complement
  BitArray<N> twoComplement() const { return BitArray<N>(~*this)++; }

  // non-const 2 complement
  BitArray<N>& twoComplement() {
    (*this).flip();
    (*this)++;
    return *this;
  }

  // subtract and assignment
  BitArray<N>& operator-=(const BitArray<N>& a) { return *this += a.twoComplement(); }

  // subtract
  BitArray<N> operator-(const BitArray<N>& a) { return BitArray<N>(*this) -= a; }

private:
  unsigned _data[N / 32 + 1];
};

/*
template<int N>
ostream & operator <<(ostream & o, const BitArray<N> &b) {
  b.print(o); return o;
}
*/

#endif