假设我有一个无符号的 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 可以在运行时变化。
尝试这样的事情：
x = ~x;
for (i=0; i<N; i++) x&=x/2;
for (i=0; i<N; i++) x|=x*2;
x = ~x;
非操作是为了解释零在顶部“移入”而不是一的事实。您可以通过手动在顶部添加一个来避免它；然后&=and|=步骤也会反转。
顺便说一句，如果这确实有效，您可能希望为每个 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
编辑：对于这个问题，除非相对较大，R..否则 ' 的解决方案会更好（在我的机器上，交叉点在附近，但这是使用所有可能的 32 位数字进行测试，这可能不代表预期用途）。所以我赞成该解决方案，但我将我的解决方案留在这里，因为它展示了如何在一个单词中迭代 s 的跨度（或者，对 s 进行小的修改），这可能对其他目的有用。NM = 32N = 1801
这是您的示例，标记了范围和前面的 1：
111 000 11 00 1 0000 1 0 1 00000 111
1 000 1 00 1 0
假设我们从这些范围中的每一个中减去“1”：（相对于范围，而不是真正的 1）
0 111 0 11 0 1
并将其添加回原始内容：
111 111 11 11 1 0000 1 1 1 00000 111
好的，看起来不错。所以我们需要计算出所有1要减去的 s，也就是0在每个 size less ≤ N 的范围内最后一个的位置。而要计算出范围的大小，我们还需要找到前面1的。
因此，基本上我们需要0通过交替搜索 last0和 last来找到 s 的所有跨度1，注意将尾随位设置为 all 1s 或 all 0s。如果范围不是太大，那么我们可以减去最后一个位置的bit，然后0再加1上最后一个1的位置，这会将0span中的所有s变成1s。我担心这不是很清楚，所以让我们尝试一些代码。
首先是以下小功能：
unsigned int last_one(unsigned int k) { return k & -k; }
unsigned int last_zero(unsigned int k) { return (k + 1) & ~k; }
尝试直到你确信它有效。请注意，它们都返回单个一位，如果没有则返回零last_{one,zero}
接下来，跨度有多大？计算 s 会有点痛苦，0因为这涉及到寻找位置（不是那么困难，但没有必要）。但我们不在乎实际数字是多少；我们只需要知道它与N. 但是我们可以看到，如果最后一个与最后一个（标记）N的比率最多为 2 N ，则跨度的大小最多为位。10
所以让我们把所有这些放在一起。
unsigned long fill_in_runs(unsigned long val, int N) {
unsigned long k = val;
while (k) {
unsigned long last_zero = (k + 1) & ~k;
k -= last_zero - 1;
if (k) {
unsigned long last_one = k & -k;
if ((last_one >> N) <= last_zero)
val += last_one - last_zero;
k += last_one - 1;
} else if (last_zero > (1UL << (M - N - 1)))
val -= last_zero;
}
return val;
}
我相信下面的代码可以满足您的要求，但您仍然可以优化它，我把它留给您...
#define BIT_GROUP 4
int main()
{
uint32_t i, j, n;
uint8_t bit_pos, zero_bit_pos, count;
i = n = 0xaa05;
printf("%x\n", i);
while (n)
{
if (n & 1)
printf("1");
else
printf("0");
n >>= 1;
}
printf("\n");
n = i;
bit_pos = count = 0;
while(n)
{
if(!(n & 1))
{
if(count <= BIT_GROUP)
{
zero_bit_pos = bit_pos;
count++;
}
else
{
zero_bit_pos = 0;
count = 0;
j = 0;
}
if(count <= BIT_GROUP)
{
j = ((1 << count) - 1);
}
}
else
{
j <<= ((zero_bit_pos + 1) - count);
i |= j;
j = 0;
zero_bit_pos = 0;
count = 0;
}
bit_pos++;
n >>= 1;
}
n = i;
while (n)
{
if (n & 1)
printf("1");
else
printf("0");
n >>= 1;
}
printf("\n");
printf("%x\n", i);
return 0;
}
希望能帮助到你！！！！！！