c – 将大小<= N到1的连续0位的所有组翻转

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;

与R ..的解决方案相同的想法,但有一点优化.

为了优化更多,可以消除第二个循环：

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;

这里唯一剩下的循环移除位组(与前面的变体完全相同),而不是第二个循环,使用简单的按位技术来恢复长于N个组.

实施例(N = 4)：

input string  110000100000011
inverted one  001111022222100
loop iter. 1  000111002222200
loop iter. 2  000001000011100
one more iter 000000000001100

第一个循环迭代工作正常,因为每个位组前面至少有一个零位.因此,我们在每个位组之前至少有两个零位.因此,可以在第二次循环迭代时一次移位两位.同样的原因,第三次循环迭代可能会一次移位4位,但是这个例子不需要大于2位的位移.由于循环已经将位组移位了3位,我们必须将它们移位N-3 = 1位以上(由循环后的下一行完成).

现在较小的位组消失了,但较大的位组由一对位表示.为了重建剩余的组,可以使用第二循环：

starting with 000000000001100
loop iter. 1  000000000011100
loop iter. 2  000000002222200
one more iter 000000022222100
result        222221100000011

或者代替第二个循环,我们可能会使用一个按位的技巧：

m             010000100000000
t             000000000001100
m-t           010000011110100
(m-t) & ~m    000000011110100
t|((m-t)&~m)  000000022222100
result        222221100000011

m标志着每个组的开始. m-t恢复所有偏移位.下一个操作会清除m的未使用位.需要一个操作来将恢复的位与移位循环之后剩余的位组合.

基准测试结果(AMD K8,GCC 4.6.3 -O2),秒数：

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