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

bit-manipulation, c, c++

Solution

x = ~x;
for (j = 1; j <= N/2; j *= 2) x &= (x >> j);
x &= (x >> (N - j + 1));
for (j = 1; j <= N/2; j *= 2) x |= (x << j);
x |= (x << (N - j + 1));
x = ~x;

Same idea as the solution by R.., but a little bit optimized.

To optimize more, it is possible to eliminate second loop:

t = ~x;
m = x & (t << 1);
for (j = 1; j <= N/2; j *= 2) t &= (t >> j);
t &= (t >> (N - j + 1));
t |= ((m - t) & ~m);
x = ~t;

Here the only remaining loop shifts away bit groups (exactly as in previous variant), but instead of second loop, a simple bitwise trick is used to restore longer-than-N groups.

Example (N = 4):

input string  110000100000011
inverted one  001111011111100
loop iter. 1  000111001111100
loop iter. 2  000001000011100
one more iter 000000000001100

First loop iteration works properly because each bit group is preceded by at least one zero bit. As a result we have at least two zero bits preceding each bit group. So it is possible to shift by two bits at once on second loop iteration. For the same reason third loop iteration may shift by 4 bits at once, etc. But this example doesn't need shift larger than two bits. Since loop has shifted bit groups by 3 bits already, we have to shift them by N-3=1 bit more (which is done by next line after the loop).

Now smaller bit group disappeared, but larger one is represented by a pair of bits. To reconstruct the remaining group(s), second loop may be used:

starting with 000000000001100
loop iter. 1  000000000011100
loop iter. 2  000000001111100
one more iter 000000011111100
result        111111100000011

Or instead of the second loop, we may use a bitwise trick:

m             010000100000000
t             000000000001100
m-t           010000011110100
(m-t) & ~m    000000011110100
t|((m-t)&~m)  000000011111100
result        111111100000011

`m` marks the beginning of each group. `m-t` restores all shifted-out bits. The next operation clears unused bits of `m`. One more operation is needed to combine restored bits with the bits remaining after the shifting loop.

Benchmark results (AMD K8, GCC 4.6.3 -O2), seconds:

N one_loop two_loops unoptimized
1     3.9     4.2       3.3
2     4.6     6.2       5.2
3     4.6     6.2       7.1
4     5.6     7.9       8.9
5     5.6     7.9      11.3
6     5.6     7.9      13.3
15    6.7    10.0      46.6

Problem

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.

Original source