Jos*_*vin 9 c c++ bit-manipulation
假设我有一个无符号的M位整数(其中M是8,16,32,64中的一个),其中有不同的0位运行:
... 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可以在运行时变化.
R..*_*R.. 10
尝试这样的事情:
x = ~x;
for (i=0; i<N; i++) x&=x/2;
for (i=0; i<N; i++) x|=x*2;
x = ~x;
不操作是为了解释零在顶部而不是从"移入"的事实.您可以通过手动引入顶部的一个来避免它; 那么&=和|=步骤会扭转过.
顺便说一句,如果这确实有效,你可能想要为每个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