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

Question

在使用按位运算进行编程时，我有一个疑问。也就是说，在我的项目中，在某个时间点我需要设置这样的位，如果我输入“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答案可以处理 0 到 31，而 0xFFFFFFFF>>(32-n)答案可以处理 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