使用N个最低有效位创建掩码

Question

我希望创建一个宏或函数¹ mask(n)，给定一个数字n，返回其最低位的n个设置为1的无符号整数。虽然这似乎应该是一个基本的原语，有着大量讨论的实现，可以高效地编译 - 但事实并非如此。

当然，不同的实现可能对于像unsigned int这样的原始整型类型具有不同的大小，因此为了具体起见，我们假设特别返回一个uint64_t，尽管当然可接受的解决方案将针对任何无符号整型类型（具有不同的定义）工作。特别是当返回的类型等于或小于平台的本机宽度时，解决方案应该是有效的。

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

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

其次是性能：理想情况下，该成语应该编译为在常见平台上以大约最有效的平台特定方式执行此操作的方式。

为了性能而牺牲简单性（例如，在不同的平台上使用不同的实现）的解决方案也可以接受。

---

¹ 最一般的情况是函数，但理想情况下它也应该作为一个宏工作，而不会重新评估任何参数超过一次。

- BeeOnRope

Answer 1

不需要分支的另一种解决方案

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

n & 0x3F的作用是保持移位量最大为63，以避免未定义行为。实际上，大多数现代架构将仅抓取移位量的较低位，因此不需要进行and操作。

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

Clang的输出比gcc更好。发生这种情况是因为对于MIPS64和ARM64，gcc会生成条件指令，但对于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位问题：如何在无符号整数中设置最后的n个位

- phuclv

Answer 2

尝试

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草案)标准的相关部分 表示，对于左移和右移，都有以下规定：

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

这让我犯了错误。再次感谢评论区所有人对我的代码进行了审查并指出了错误。

- Davislor

---

至关重要的是，这必须适用于 [0, 64] 中的所有 n。特别地，mask(0) == 0 并且 mask(64) == (uint64_t)-1。 - n. m.

我不知道移位操作的含义，但在实践中，“1ULL << 64”通常是1，而不是0。 - harold

类似地，右移操作通常不能将所有位都移出去，除非在PowerPC和某些其他体系结构中。 - harold

唉，是的，标准规定类型宽度的右移是未定义行为。 - Davislor

C标准对于比类型宽度更多的位移操作有何规定？ - phuclv

Answer 3

这是一个便携且无条件限制的方案：

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

- n. m.

---

如果shlx支持单操作数可变计数左移，那么情况就不会太糟糕了：https://godbolt.org/z/QXW0ID - Peter Cordes

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上的2条BTS uop）高效地计算此问题。

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

(3-component LEA在Intel上有3个周期的延迟，但我认为在许多情况下这是uop计数和吞吐量最优的。)

---

在C语言中，除了x86 Intel SnB-family，所有64位ISA都可以很好地编译

C编译器不幸地很愚蠢，并且即使针对没有BMI2的Intel CPU进行调优（其中shl reg,cl是3个uops），也会忽略使用bts。

例如，gcc和clang都可以这样做（使用dec或add-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 开始。但是除此之外，MSVC 和 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 ），使用 -march = haswell 的gcc / clang可以得到最优化的AMD代码。

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

ICC仍然使用3元素LEA，因此如果您的目标是MSVC或ICC，请在源代码中使用2ULL << n版本，无论您是否启用了BMI2，因为您无论如何都不会得到BTS。这可以避免最糟糕的情况：慢速LEA和可变计数移位而不是BTS。

---

对于非x86 ISA（其中假定可变计数移位是高效的，因为它们没有x86税收，即使计数恰好为零，也不会保留标志，并且可以使用任何寄存器作为计数），这个问题编译得很好。

例如AArch64。当然，这可以提升常量2以重复使用不同的n，就像x86可以使用BMI2 shlx一样。

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

基本上，在 PowerPC、RISC-V 等上都是一样的。

- Peter Cordes

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以及icc -O2（但不是-Os）中将其优化为常量掩码。

解释：

&63被优化掉了，但确保移位<=64。

对于小于64的值，它只是使用(1<<n)-1设置前n个位。 1<<n设置第n位（等效于pow(2,n)），从2的幂中减去1会设置所有小于该数的位。

通过使用条件来设置要移位的初始1，没有创建分支，但是对于所有值>=64，它都会给出0，因为左移0始终会产生0。 因此，当我们减去1时，对于64及以上的值，我们得到所有位都被设置（由于-1的二进制补码表示）。

注意事项：

1. 补码系统必须消失-如果您有一个补码系统，则需要进行特殊处理

2. 一些编译器可能无法优化&63

- technosaurus

---

很遗憾，将64位值向左或向右移动64位或更多位是未定义的行为。 - BeeOnRope

@BeeOnRope：我添加了&63，它会被优化掉的。 - technosaurus

如果我没记错的话，有些ISA在指令的同时饱和移位计数而不是掩码计数（例如ARM32但不是AArch64）。一个聪明的编译器仍然可以合法地优化在这种情况下的&63。因为被移位的值对于更高的移位计数来说已经是0了。但是在实践中，针对32位版本的ARM32，GCC并没有这么做。https://godbolt.org/z/PiIOcO。然而，它对于AArch64编译得非常高效；AArch64的“cset”比x86的弱小的8位“setcc”更好。 - Peter Cordes

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 clang中，这编译成五条指令：

• 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

- Řrřola

---

如果BMI2可用，则只需要mov rax，-1; bzhi rax，rax，rdi。https://gcc.godbolt.org/z/ocdqa9 - phuclv