… 111 000 11 00 1 0000 1 0 1 00000 111 …
给定一个N,其中0 <= N <= M,我想填充大小为< = N的整数的0的所有组.所以如果对于上述整数,我们给出N = 3,结果将是： … 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
