假设我有一个无符号的M位整数(其中M是8、16、32、64之一)，其中包含各种0位游程:
... 111 000 11 00 1 0000 1 0 1 00000 111 ...
给定一个数字N，其中0
... 111 111 11 11 1 0000 1 1 1 00000 111 ...
请注意，零的4组和5组的零不会翻转，因为它们的大小> 3。
如何使用C/C++编写高效的实现？我认为我可以做些巧妙的事情，但是我不确定从哪里开始。我已经看到乘法用于传播位模式，但是这种可变长度检查却没有。由于相同的原因，查找表似乎很痛苦。适当放置的减法1可以翻转一连串的位，但是弄清楚要减去的内容似乎很棘手。
编辑:显然，尽管M在编译时是固定的，但N在运行时可能会有所不同。
最佳答案
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 001111011111100
loop iter. 1 000111001111100
loop iter. 2 000001000011100
one more iter 000000000001100
因为每个位组之前至少有一个零位，所以第一循环迭代工作正常。结果，我们在每个位组之前至少有两个零位。因此，有可能在第二个循环迭代中一次移位两位。出于相同的原因，第三次循环迭代可能一次移位4位，依此类推。但是此示例不需要大于2位的移位。由于循环已经将位组移位了3位，因此我们必须将它们再移位N-3 = 1位(这是在循环后的下一行完成的)。
现在较小的位组消失了，但是较大的位组由一对位表示。要重建其余组，可以使用第二个循环:
starting with 000000000001100
loop iter. 1 000000000011100
loop iter. 2 000000001111100
one more iter 000000011111100
result 111111100000011
或代替第二个循环，我们可以使用按位技巧:
m 010000100000000
t 000000000001100
m-t 010000011110100
(m-t) & ~m 000000011110100
t|((m-t)&~m) 000000011111100
result 111111100000011
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