c++ - 将大小 <= N 的所有连续 0 位组翻转为 1s

Question

假设我有一个无符号 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 在运行时可能会发生变化。

Answer 1

尝试这样的事情:

x = ~x;
for (i=0; i<N; i++) x&=x/2;
for (i=0; i<N; i++) x|=x*2;
x = ~x;

not 操作是为了说明零“移入”在顶部而不是一个的事实。您可以通过手动在最高位中引入一个来避免它；那么 &= 和 |= 步骤也会反转。

顺便说一句，如果这确实有效，您可能希望为每个 N 编写一个展开的版本，而不是使用那些循环。