C++ - find string of N 1-bits in a bit-array

As the title sais I want to find a successive run of n one-bits in a bit-array of variable size (M).

The usual use-case is N <= 8 and M <= 128

I do this operation a lot in an innerloop on an embedded device. Writing a trivial implementation is easy but not fast enough for my taste (e.g. brute force search until a solution is found).

I wonder if anyone has a more elegant solution in his bag of tricks.

This question originated from stackoverflow.com

Question by Nils Pipenbrinck

Answer

int nr = 0;    for ( int i = 0; i < M; ++i )
{
  if ( bits[i] )
    ++nr;
  else
  {
    nr = 0; continue;
  }
  if ( nr == n ) return i - nr + 1; // start position    
}

What do you mean by brute force? O(M*N) or this O(M) solution? if you meant this, then I'm not sure how much more you can optimize things.

It's true we could achieve constant improvements by walking over every byte instead of every bit. This comes to mind: When I say byte I mean a sequence of N bits this time.

for ( int i = 0; i < M; i += N )
  if ( bits[i] == 0 ) // if the first bit of a byte is 0, that byte alone cannot be a solution. Neither can it be a solution in conjunction with the previous byte, so skip it.
    continue;
  else // if the first bit is 1, then either the current byte is a solution on its own or it is a solution in conjunction with the previous byte
  {
    // search the bits in the previous byte.
    int nrprev = 0;
    while ( i - nrprev >= 0 && bits[i - nrprev] ) ++nrprev;

    // search the bits in the current byte;
    int nrcurr = 0;
    while ( bits[i + nrcurr + 1] && nrcurr + nrprev <= N ) ++nrcurr;

    if ( nrcurr + nrprev >= N ) // solution starting at i - nrprev + 1.
      return i - nrprev + 1;   
  }

Not tested. Might need some additional conditions to ensure correctness, but the idea seems sound.