C语言 创建设置了 N 个最低有效位的掩码

Question

我想创建一个宏或函数¹mask(n)，它给定一个数字n返回一个无符号整数，并设置了n个最低有效位。尽管这似乎应该是一个基本的原语，具有大量讨论的高效编译的实现 - 但事实似乎并非如此。

当然，对于像unsigned int这样的原始整型，各种实现可能有不同的大小，所以为了具体起见，让我们假设我们正在谈论返回一个uint64_t，尽管当然一个可接受的解决方案适用于任何无符号整型(具有不同的定义)。特别是，当返回的类型等于或小于平台的本机宽度时，解决方案应该是有效的。

至关重要的是，这必须适用于 [0， 64] 中的所有n。特别是mask(0) == 0和mask(64) == (uint64_t)-1.许多"明显"的解决方案不适用于这两种情况之一。

最重要的标准是正确性：只有不依赖于未定义行为的正确解决方案才是有趣的。

第二个最重要的标准是性能：理想情况下，习语应该编译为大约最有效的特定于平台的方式，以便在常见平台上执行此操作。

以性能的名义牺牲简单性的解决方案，例如，在不同平台上使用不同的实现，是可以的。

---

¹最一般的情况是函数，但理想情况下，它也可以作为宏工作，而无需多次重新评估其任何参数。

Answer 1

尝试

unsigned long long mask(const unsigned n)
{
assert(n <= 64);
return (n == 64) ? 0xFFFFFFFFFFFFFFFFULL :
(1ULL << n) - 1ULL;
}

有几个伟大的、聪明的答案可以避免条件，但现代编译器可以为此生成不分支的代码。

您的编译器可能会弄清楚内联它，但您可以使用inline或C++constexpr给它一个提示。

unsigned long long int类型保证至少为 64 位宽，并且存在于每个实现中，uint64_t不是。

如果你需要一个宏(因为你需要一些用作编译时常量的东西)，那可能是：

#define mask(n) ((64U == (n)) ? 0xFFFFFFFFFFFFFFFFULL : (1ULL << (unsigned)(n)) - 1ULL)

正如几个人在评论中正确提醒我的那样，1ULL << 64U潜在的未定义行为！因此，请插入该特殊情况的检查。

如果支持宽于64 位的实现上该类型的全部范围对您来说很重要，则可以将64U替换为CHAR_BITS*sizeof(unsigned long long)。

类似地，您可以从无符号的右移生成此值，但您仍然需要n == 64作为特殊情况进行检查，因为按类型宽度右移是未定义的行为。

伊塔：

(N1570草案)标准的相关部分说，左右位移：

如果右操作数的值为负数或大于或等于提升的左操作数的宽度，则行为未定义。

这让我绊倒了。 再次感谢评论中审查我的代码并向我指出错误的每个人。

Answer 2

另一种没有分支的解决方案

unsigned long long mask(unsigned n)
{
return ((1ULL << (n & 0x3F)) & -(n != 64)) - 1;
}

n & 0x3F将班次数量保持在最大 63 以避免 UB。事实上，大多数现代架构只会抓取移位量的较低位，因此不需要and指令。

可以将 64 的检查条件更改为-(n < 64)，使其返回 n ⩾ 64 的所有 1，这相当于_bzhi_u64(-1ULL, (uint8_t)n)如果您的 CPU 支持 BMI2。

Clang的输出看起来比gcc更好。碰巧 gcc 会为 MIPS64 和 ARM64 发出条件指令，但不为 x86-64 发出条件指令，从而导致更长的输出

---

这个条件也可以简化为n >> 6，利用如果 n = 64 时它将是 1 的事实。我们可以从结果中减去它，而不是像上面那样创建一个掩码

return (1ULL << (n & 0x3F)) - (n == 64) - 1; // or n >= 64
return (1ULL << (n & 0x3F)) - (n >> 6) - 1;

GCC 将后者编译为

mov     eax, 1
shlx    rax, rax, rdi
shr     edi, 6
dec     rax
sub     rax, rdi
ret

---

更多选择

return ~((~0ULL << (n & 0x3F)) << (n == 64));
return ((1ULL << (n & 0x3F)) - 1) | (((uint64_t)n >> 6) << 63);
return (uint64_t)(((__uint128_t)1 << n) - 1); // if a 128-bit type is available

32 位的类似问题：在无符号 int 中设置最后的"n"位

Answer 3

这是一个可移植且无条件的：

unsigned long long mask(unsigned n)
{
assert (n <= sizeof(unsigned long long) * CHAR_BIT);
return (1ULL << (n/2) << (n-(n/2))) - 1;
}

Answer 4

这不是确切问题的答案。仅当0不是必需的输出时，它才有效，但效率更高。

2ⁿ⁺¹- 1 计算无溢出。 即设置了低位n位的整数，对于 n = 0 .。all_bits

可能在三元中使用它进行cmov可能是解决问题中整个问题的更有效的解决方案。 也许基于MSB设置的数字的左旋，而不是1的左移，以照顾这个计数与pow2计算问题的差异。

// defined for n=0 .. sizeof(unsigned long long)*CHAR_BIT
unsigned long long setbits_upto(unsigned n) {
unsigned long long pow2 = 1ULL << n;
return pow2*2 - 1;                  // one more shift, and subtract 1.
}

编译器输出建议使用替代版本，如果您不使用 gcc/clang(已经这样做了)，则在某些 ISA 上很好：烘焙额外的移位计数，以便初始移位可以移出所有位，保留0 - 1 =所有位设置。

unsigned long long setbits_upto2(unsigned n) {
unsigned long long pow2 = 2ULL << n;      // bake in the extra shift count
return pow2 - 1;
}

此函数的 32 位版本的输入/输出表为：

n   ->  1<<n        ->    *2 - 1
0    ->    1         ->   1        = 2 - 1
1    ->    2         ->   3        = 4 - 1
2    ->    4         ->   7        = 8 - 1
3    ->    8         ->  15        = 16 - 1
...
30   ->  0x40000000  ->  0x7FFFFFFF  = 0x80000000 - 1
31   ->  0x80000000  ->  0xFFFFFFFF  = 0 - 1

您可以在它后面打一个cmov，或者以其他方式处理必须产生零的输入。

---

在 x86 上，我们可以通过 3 个单 uop 指令有效地计算这一点：(或 Ryzen 上的 BTS 为 2 uops)。

xor  eax, eax
bts  rax, rdi               ; rax = 1<<(n&63)
lea  rax, [rax + rax - 1]   ; one more left shift, and subtract

(3 分量 LEA 在英特尔上具有 3 个周期延迟，但我相信这对于 uop 计数和在许多情况下的吞吐量是最佳的。

---

在 C 语言中，这适用于所有 64 位 ISA，除了 x86 Intel SnB 家族

不幸的是，C 编译器很笨，即使在针对没有 BMI2 的英特尔 CPU 进行调优时(其中shl reg,cl为 3 uops)，也无法使用bts。

例如，GCC 和 Clang 都在Godbolt 上执行此操作(使用 dec 或添加 -1)

# gcc9.1 -O3 -mtune=haswell
setbits_upto(unsigned int):
mov     ecx, edi
mov     eax, 2       ; bake in the extra shift by 1.
sal     rax, cl
dec     rax
ret

由于 Windows x64 调用约定，MSVC 在 ECX 中以n开头，但模数，它和 ICC 做同样的事情：

# ICC19
setbits_upto(unsigned int):
mov       eax, 1                                        #3.21
mov       ecx, edi                                      #2.39
shl       rax, cl                                       #2.39
lea       rax, QWORD PTR [-1+rax+rax]                   #3.21
ret                                                     #3.21

---

使用BMI2(-march=haswell)，我们从gcc/clang获得针对AMD的最佳代码，并带有-march=haswell

mov     eax, 2
shlx    rax, rax, rdi
add     rax, -1

ICC 仍然使用 3 分量 LEA，因此，如果您以 MSVC 或 ICC 为目标，无论是否启用 BMI2，都使用源中的2ULL << n版本，因为无论哪种方式都不会获得 BTS。 这避免了两全其美的最坏情况;慢 LEA 和可变计数移位而不是 BTS。

---

在非 x86 ISA 上(其中可能可变计数移位是有效的，因为它们没有在计数恰好为零时保留标志不变的 x86 税，并且可以使用任何寄存器作为计数)，这编译得很好。

例如 AArch64。 当然，这可以提升恒定的2，以便以不同的n重复使用，就像 x86 可以与 BMI2shlx一样。

setbits_upto(unsigned int):
mov     x1, 2
lsl     x0, x1, x0
sub     x0, x0, #1
ret

在PowerPC，RISC-V等上基本相同。

Answer 5

#include <stdint.h>
uint64_t mask_n_bits(const unsigned n){
uint64_t ret = n < 64;
ret <<= n&63; //the &63 is typically optimized away
ret -= 1;
return ret;
}

结果：

mask_n_bits:
xor     eax, eax
cmp     edi, 63
setbe   al
shlx    rax, rax, rdi
dec     rax
ret

返回预期的结果，如果传递一个常量值，它将在 clang 和 gcc 以及 -O2(但不是 -Os)处的 icc 中优化为常量掩码。

解释：

&63 被优化，但确保班次为 <=64。

对于小于 64 的值，它仅使用(1<<n)-1设置前 n 位。1<<n设置第 n 位(等效的 pow(2，n))，并从 2 的幂中减去 1 设置所有小于该位的位。

通过使用条件将初始 1 设置为移位，不会创建分支，但它为所有值提供 0>=64，因为左移 0 将始终产生 0。因此，当我们减去 1 时，我们会得到为 64 或更大的值设置的所有位(因为 -1 的 2s 补码表示)。

警告：

• 1s 补体系统必须死亡 - 如果您有特殊外壳，则需要特殊外壳
• 某些编译器可能无法优化 &63

Answer 6

当输入 N 介于 1 和 64 之间时，我们可以使用-uint64_t(1) >> (64-N & 63).
常量 -1 有 64 个设置位，我们将其中的 64-N 移开，所以我们只剩下 N 个设置位。

当 N=0 时，我们可以在移位之前将常数设为零：

uint64_t mask(unsigned N)
{
return -uint64_t(N != 0) >> (64-N & 63);
}

这将编译为 x64 叮当声中的五条指令：

• neg 将携带标志设置为N != 0。
• SBB 将进位标志转换为 0 或 -1。
• shr rax，N 已经有一个隐式N & 63，所以64-N & 63被优化为-N。

mov rcx,rdi
neg rcx
sbb rax,rax
shr rax,cl
ret

使用 BMI2 扩展，它只有四条指令(班次长度可以保留在rdi中)：

neg edi
sbb rax,rax
shrx rax,rax,rdi
ret