Flip all groups of consecutive 0 bits of size <= N to 1s

Question

Say I have an unsigned M-bit integer (where M is one of 8, 16, 32, 64), with various runs of 0-bits inside it:

...111 000 11 00 1 0000 1 0 1 00000 111...

Given a number N where 0 <= N <= M, I'd like to fill all the groups of 0s in the integer that are <=N in size. So if for the above integer we were given N=3, the result would be:

...111 111 11 11 1 0000 1 1 1 00000 111...

Notice that the 4 group and 5 group of zeroes are not flipped, because their size is > 3.

How would I approach writing an efficient implementation in C/C++? I assume there is some clever bit twiddling I could do, but I'm not sure where to start. I've seen multiplication used to propogate a bit pattern but not with this sort of variable length checking. Lookup tables seem painful for the same reason. A well placed subtraction of 1 can flip a run of bits, but figuring out what to subtract looks tricky.

Edit: To be clear, although M is fixed at compile time, N can vary at runtime.

Answer 1

Try something like this:

x = ~x;
for (i=0; i<N; i++) x&=x/2;
for (i=0; i<N; i++) x|=x*2;
x = ~x;

The not operation is to account for the fact that zeros "shift in" at the top rather than ones. You could avoid it by bringing in a one in the top bit manually; then the &= and |= steps would reverse too.

By the way, if this does work, you'll probably want to write an unrolled version for each N rather than using those loops.