Fastest way to clear every kth bit in boost::dynamic_bitset

What is the fastest way to clear every kth bit in a boost::dynamic_bitset, optionally from offset j?

Currently I'm doing this which is pretty darn slow (pseudocode):

for (i = j; i < bitset.size(); i += k) {
    bitset[i] = 0;
}

Millio开发者_C百科ns of bit-clears have to be done, so that's why I'm looking for a fast way to do it.

okay, not sure if this is faster, but I think you can test:

The key operation is the construction of the mask bit sets, you should have a table of pre-constructed masks (which will allow you to reset every kth bit up to every 32nd bit [on my platform unsigned long is 32-bits]). Then the expensive operation is constructing a full mask of the same size as the input - if it's always the same size, and memory is not a constraint, you can simply construct a lookup table for this as well, and then it's simply &ing the two bit sets.

#include <iostream>
#include <limits>
#include <boost/dynamic_bitset.hpp>

using namespace std;

int main(void)
{
  boost::dynamic_bitset<> orig(64);
  for (int i = 0; i < orig.size(); ++i) {
    orig[i] = rand() % 2;
  }

  std::cout << orig << std::endl;

  unsigned long mask = 0x88888888; // reset every 4th bit
  boost::dynamic_bitset<> mbits(numeric_limits<unsigned long>::digits, mask);

  while(mbits.size() < orig.size())
    mbits.append(mask);
  mbits.resize(orig.size()); // incase not aligned
  mbits <<= 5; // arbitary starting point (i.e. j)
  std::cout << mbits << std::endl;

  mbits.flip();

  std::cout << mbits << std::endl;

  orig &= mbits;

  std::cout << orig << std::endl;

  return 0;
}

UPDATE: Okay, just tested it very roughly, and you can see the result here: http://www.ideone.com/ez3Oc, with a pre-constructed mask, it can be almost +40% quicker...

For very large bitsets, compute a mask n bits long (where n is your native size, e.g. 64 for x86_64) as Nim suggested, apply it.
If your native length is not a multiple of k, shift it accordingly.
So if you have a native length of 10 and want to set only every 3rd bit of a 30 bit-long bitset, you'd need 3 passes like this:
First 10 bits: 0010010010
Second 10 bits: 0100100100
Last 10 bits: 1001001001
So, after applying each mask you'd need to shift it (n%k) bits to the left.

Repeat until you're done.