Listing 7 An implementation of the bits class template

// bits.h

#include <iostream. h>
#include <stddef. h>
#include <limits.h>
#include <assert.h>
#include "string.hpp"

template<size_t N>
class bits
{
   // Global I/O funtions
   friend ostream& operator<<(ostream& os, const bits<N>& rhs)
      {os << rhs.to_string(); return os;}
   friend istream& operator>>(istream& is, bits<N>& rhs)
      {rhs.read(is); return is;}

   // Global bitwise operators
   friend bits<N>operator&(const bits<N>& b1,const bits<N>& b2)
      {bits<N> r(b1); return r &= b2;}
   friend bits<N>operator|(const bits<N>&b1,const bits<N>& b2)
      {bits<N> r(b1); return r |= b2;}
   friend bits<N> operator^(const bits<N>& b1,const bits<N>& b2)
      {bits<N> r(b1); return r ^= b2;}

public:
   // Constructors
   bits();
   bits(unsigned long n);
   bits(const bits<N>& b);
   bits(const string& s);

   // Conversions
   unsigned short to_ushort() const;
   unsigned long to_ulong() const;
   string to_string() const;

   // Assignment
   bits<N>& operator=(const bits<N>& rhs);

   // Equality
   int operator==(const bits<N>& rhs) const;
   int operator!=(const bits<N>& rhs) const;

   // Basic bit operations
   bits<N>& set(size_t pos, int val = 1);
   bits<N>& set();
   bits<N>& reset(size_t pos);
   bits<N>& reset();
   bits<N>& toggle(size_t pos);
   bits<N>& toggle();
   bits<N> operator~() const;
   int test(size_t n) const;
   int any() const;
   int none() const;

   // Bit-wise operators
   bits<N>& operator&=(const bits<N>& rhs);
   bits<N>& operator|=(const bits<N>& rhs);
   bits<N>& operator^=(const bits<N>& rhs);

   // Shift operators
   bits<N>& operator<<=(size_t n);
   bits<N>& operator>>=(size_t n);
   bits<N> operator<<(size_t n) const;
   bits<N> operator>>(size_t n) const;

   size_t count() const;
   size_t length() const;

private:
   typedef unsigned int Block;
   enum {BLKSIZ = CHAR_BIT * sizeof (Block)};
   enum {nblks_ = (N+BLKSIZ-1) / BLKSIZ};

   Block bits_[nblks_];

   static size_t word(size_t pos)
     {return nblks_ - 1 - pos/BLKSIZ;}
   static size_t offset(size_t pos)
     {return pos % BLKSIZ;}
   static Block mask1(size_t pos)
     {return Block(1) << offset(pos);}
   static Block mask0(size_t pos)
     {return ~(Block(1) << offset(pos));}

   void cleanup();
   void set_(size_t pos);
   int set_(size_t pos, int val);
   void reset_(size_t pos);
   int test_(size_t pos) const;
   void from_string(const string& s);
   void read(istream& is);
   int any(size_t start_pos) const;
   unsigned long to(size_t) const;
};

template<size_t N>
inline bits<N>::bits()
{
   reset();
}

template<size_t N>
bits<N>::bits(const string& s)
{
   // Validate that s has only 0's and 1's
   for (int i = 0; i < s.length(); ++i)
   {
       char c = s.get_at(i);
       if (c != '0' && c != '1')
          break;
   }
   assert(i == s.length());

   from_string(s);
}

template<size_t N>
inline bits<N>::bits(const bits<N>& b)
{
   memcpy(bits_,b.bits_,nblks_*sizeof(bits_[0]));
}

template<size_t N>
bits<N>::bits(unsigned long n)
{
   // Don't drop any bits
   if (N < CHAR_BIT * sizeof(unsigned long))
      assert((n >> N) == 0);

   reset();

   size_t nblks = sizeof (unsigned long) / sizeof (Block);
   if (nblks > 1)
      for (int i = 0; i < nblks; ++i)
      {
          bits_[nblks - 1 - i] = Block(n);
          n >>= BLKSIZ;
      }
   else
      bits_[nblks_ - 1] = Block(n);
}

template<size_t N>
unsigned short bits<N>::to_ushort() const
{
   size_t limit = sizeof(unsigned short) * CHAR_BIT;
   assert(!(length() > limit && any(limit)));
   size_t nblks = sizeof(unsigned short) / sizeof(Block);
   return (unsigned short) to(nblks);
}
template<size_t N>
unsigned long bits<N>::to_ulong() const
{
   size_t limit= sizeof(unsigned long) * CHAR_BIT;
   assert(!(length() > limit && any(limit)));
   size_t nblks = sizeof(unsigned long) / sizeof(Block);
   return to(nblks);
}

template<size_t N>
string bits<N>::to_string() const
{
   char *s = new char[N+1];
   for (int i = 0; i < N;++i)
       s[i] = '0' + test_(N-1-i);
   s[N] = '\0';
   string s2(s);
   delete [] s;
   return s2;
}

template<size_t N>
bits<N>& bits<N>::operator=(const bits<N>& b)
{
   if (this != &b)
      memcpy(bits_,b.bits_, nblks_* sizeof(bits_[0]));
   return *this;
}

template<size_t N>
inline int bits<N>::operator==(const bits<N>& b) const
{
   return !memcmp(bits_,b.bits_,nblks_ * sizeof(bits_[0]));
}

template<size_t N>
inline int bits<N>::operator!=(const bits<N>& b) const
{
   return !operator==(b);
}

template<size_t N>
inline bits<N>& bits<N>::set(size_t pos, int val)
{
   assert(pos < N);
   (void) set_(pos,val);
   return *this;
}

template<size_t N>
inline bits<N>& bits<N>::set()
{
   memset(bits_,~0u,nblks_ * sizeof bits_[0]);
   cleanup();
   return *this;
}

template<size_t N>
inline bits<N>& bits<N>::reset(size_t pos)
{
   assert(pos < N);
   reset_(pos);
   return *this;
}

template<size_t N>
inline bits<N>& bits<N>::reset()
{
   memset(bits_,0,nblks_ * sizeof bits_[0]);
   return *this;
}

template<size_t N>
inline bits<N>& bits<N>::toggle(size_t pos)
{
   assert(pos < N);
   bits_[word(pos)] ^= mask1(pos);
   return *this;
}

template<size_t N>
bits<N>& bits<N>::toggle()
{
   size_t nw = nblks_;
   while (nw--)
       bits_[nw] = ~bits_[nw];
   cleanup();
   return *this;
}

template<size_t N>
inline bits<N> bits<N>::operator~() const
{
   bits<N> b(*this);
   b.toggle();
   return b;
}

template<size_t N>
inline int bits<N>::test(size_t pos) const
{
   assert(pos < N);
   return test_(pos);
}

template<size_t N>
int bits<N>::any() const
{
   for (int i = 0; i < nblks_; ++i)
       if (bits_[i])
          return 1;
   return 0;
}

template<size_t N>
inline int bits<N>::none() const
{
   return !any();
}

template<size_t N>
bits<N>& bits<N>::operator&=(const bits<N>& rhs)
{
   for (int i = 0; i < nblks_; ++i)
       bits_[i] &= rhs.bits_[i];
   return *this;
}

template<size_t N>
bits<N>& bits<N>::operator|=(const bits<N>& rhs)
{
   for (int i = 0; i < nblks_; ++i)
       bits_[i]  = rhs.bits_[i];
   return *this;
}

template<size_t N>
bits<N>& bits<N>::operator^=(const bits<N>& rhs)
{
   for (int i= 0; i < nblks ; ++i)
       bits_[i] ^= rhs.bits_[i];
   return *this;
}

template<size_t N>
bits<N>& bits<N>::operator>>=(size_t n)
{
   if (n > N)
       n = N;
   for (int i = 0; i < N-n;++i)
       (void) set_(i,test_(i+n));
   for (i = N-n; i < N; ++i)
       reset_(i);
   return *this;
}

template<size_t N>
bits<N>& bits<N>::operator<<=(size_t n)
{
   if (n > N)
       n = N;
   for (int i = N-1; i >= n; --i)
       (void) set_(i,test(i-n));
   for (i = 0; i < n; ++i)
       reset_(i);
   return *this;
}

template<size_t N>
inline bits<N> bits<N>::operator>>(size_t n) const
{
   bits r(*this);
   return r >>= n;
}

template<size_t N>
inline bits<N> bits<N>::operator<<(size_t n) const
{
   bits r(*this);
   return r <<= n;
}

template<size_t N>
size_t bits<N>::count() const
{
   size_t sum = 0;
   for (int i = 0; i < N; ++i)
       if (test_(i))
          ++sum;
   return sum;
}

template<size_t N>
inline size_t bits<N>::length() const
{
   return N;
}

// Private functions
template<size_t N>
inline void bits<N>::set_(size_t pos)
{
   bits_[word(pos)] |= mask1(pos);
}

template<size_t N>
int bits<N>::set_(size_t pos, int val)
{
   if (val)
      set_(pos);
   else
      reset_(pos);
   return !!val;
}

template<size_t N>
inline void bits<N>::reset_(size_t pos)
{
   bits_[word(pos)] &= mask0(pos);
}

template<size_t N>
inline int bits<N>::test_(size_t pos) const
{
   return !!(bits_[word(pos)] & mask1(pos));
}

template<size_t N>
inline void bits<N>::cleanup()
{
   // Make sure unused bits don't get set
   bits_[0] &= (~Block(0) >> (nblks_ * BLKSIZ - N));
}

template<size_t N>
void bits<N>::from_string(const string& s)
{
   // Assumes s contains only 0's and 1's
   size_t slen = s.length();
   reset();
   for (int i = slen-1; i >= 0; --i)
       if (s.get_at(i) == '1')set_(slen-i-1);
}

template<size_t N>
void bits<N>::read(istream& is)
{
   char *buf = new char[N];
   char c;

   is >> ws;
   for (int i = 0; i < N; ++i)
   {
       is.get(c);
       if (c == '0' || c == '1')
          buf[i] = c;
       else
       {
          is.putback(c);
          buf[i] = '\0';
          break;
       }
   }

   if (i==0)
       is.clear(ios::failbit);
   else
       from_string(string(buf));
   delete buf;
}

template<size_t N>
int bits<N>::any(size_t start) const
{
   // See if any bit past start (inclusive) is set
   for (int i = start; i < N; ++i)
       if (test_(i))
          return 1;
   return 0;
}

template<size_t N>
unsigned long bits<N>::to(size_t nblks) const
{
   if (nblks > 1)
   {
       int i;
       unsigned long n = bits_[nblks_ - nblks];

       /* Collect low-order sub-blocks into an unsigned */
       if (nblks > nblks_)
          nblks = nblks_;
       while (--nblks)
          n = (n << BLKSIZ) | bits_[nblks_ - nblks];
       return n;
   }
   else
       return (unsigned long) bits_[nblks_ - 1];

}

/* End of File */