c - 如何使用按位运算符实现模式 2^n-1

Question

在使用位运算编程时，我有一个疑问。也就是说，在我的项目中的某个时间点，我需要像这样设置位，如果我键入“1”，则表示第 1 位已设置。如果我键入“2”，则表示已设置前 2 位。

所以，

1-1 2-11 3-111 4-1111

同样如此。由此我分析出如下规律，即1-1,11-3,111-7,1111-15。

也就是2^1-1=1,2^2-1=3,2^3-1=7,...

现在我需要在一行中为此格式编写按位运算。

感谢任何帮助。

Answer 1

到目前为止，对于这个问题，我们已经有了您通常会得到的“主要两个答案”。它们的边缘条件不同。假设 32 位无符号整数取一些共同点，(1u<<n)-1 answer 可以处理 0 到 31，而 0xFFFFFFFF>>(32-n) answer 可以处理 1 到 32。

然后经常出现的一个问题是，我们可以从 0 到 32 吗？

你可以，但自然会更复杂，尤其是当你不接受条件时。通过将任何一种方法与三元运算符相结合，很容易得到完整的范围，但如果没有，仍然有其他方法。

请注意 n=32是位 0b00100000 的唯一情况设置在 n .

所以我们可以做的一件事是提取该位，将其取反，然后将其左移(注意不要执行未定义的移位)，如下所示:

((n >> 5 ^ 1) << (n & 31)) - 1

现在如果n < 32 , 它简化为旧的 (1u << n) - 1 .如果n == 32 , 它简化为 (0 << irrelevant) - 1 , 其中irrelevant恰好是 0，但我们可以选择 0 到 31 之间的任何值。

在某些语言(特别是 C# 和 Java)中，定义了按整数或更多宽度移动，并且 & 31可以删除。在某些汇编语言中，例如 PowerPC，按整数宽度移位会得到 0，在这种情况下，汇编级别相当于 (1u << n) - 1。将按原样工作。

在其他汇编语言中可能还有其他技巧，通常使用在高级语言中没有直接等效项的特殊指令。例如在带有 BMI1 的 x86 上:

or rax, -1
shl ecx, 8
bextr rax, rax, rcx

或者在带有 BMI2 的 x86 上:

or rax, -1
bzhi rax, rax, rcx