[boost] subbitset

Subject: [boost] subbitset
From: Andreas Klein (klein_at_[hidden])
Date: 2008-11-19 06:19:15

Hello.

I am using your dynamic_bitset and I encountered the following problem.

I have realy large bits sets (>100000) bits. At some point I need do
some xor Operations on only a small fraction of the bits. So I need a
way to access the bits from index n to n+s-1. The bitclass has no
convient way to do this.

I suggest add the member function sub_bitset for that purpose.

Example:

a = 100000101101101001110101
                   ^^^^^^^
a.subbitset(3,7)
b = 1001110

(The ^^^^^^^ marks the position of b in a).

I implemented subbitset as follows:

template<typename B, typename A>
dynamic_bitset<B, A>
dynamic_bitset<B, A>::subbitset(size_type n,size_type s) const
{
   assert(n+s < size());
   dynamic_bitset res(s);
   size_type  const last  = res.num_blocks() - 1; // num_blocks() is >= 1
   size_type  const last2 = num_blocks() - 1;
   size_type  const div   = n / bits_per_block;   // div is <= last
   block_width_type const r  = bit_index(n);
   const block_type * const b   = &m_bits[0];
   block_type * const bb   = &res.m_bits[0];

   if (r != 0) {

     block_width_type const ls = bits_per_block - r;

     for (size_type i = 0; i <= last; ++i) {
       if (div+i+1 >last2) {   // Do we reach the last block?
         bb[i] = (b[div+i] >> r);
         break;
       }
       bb[i] = (b[div+i] >> r) | (b[div+i+1]  << ls);
     }
   }

   else {
     for (size_type i = 0; i <= last; ++i) {
       if (i+div>last2)  // Do we reach the last block?
         break;
       bb[i] = b[i+div];
     }
     // note the '<=': the last iteration 'absorbs'
     // b[last-div] = b[last] >> 0;
   }

   // Zero unused bits
   block_width_type const rr  = bit_index(s);
   if(rr != 0)
     bb[last] &= (1<<(block_type)(rr))-1;

   return res;
}

I guess, that I am not the only one who would benefit from the
possibility to access subbitsets. I could also imagine that references
to subbitsets could be of some use. Foe example I could imagine that
one would use subbitset as follows.

a= 00000000
b= 111
a.subbit(2,3) ^= b;

->  a=00011100

But such a reference would be harder to implement and at the moment I
do not need it.

What do you think? Is there any hope for subbitset in boost?

Best wishes
      Andreas Klein.