从位置 i 开始生成 n 个掩码的最快方法

Question

从位置 pos 开始，生成 len 位设置为 1 的掩码的最快方法是什么（就普通现代架构的 cpu 周期而言）：

template <class UIntType>
constexpr T make_mask(std::size_t pos, std::size_t len)
{
    // Body of the function
}

// Call of the function
auto mask = make_mask<uint32_t>(4, 10);
// mask = 00000000 00000000 00111111 11110000 
// (in binary with MSB on the left and LSB on the right)

另外，是否有任何编译器内部函数或 BMI 函数可以提供帮助？

Answer 1

如果"starting at pos"，你的意思是掩码的最低位在对应于2^pos的位置（如你的例子）：

((UIntType(1) << len) - UIntType(1)) << pos

如果 len 可能 ≥ UIntType 中的位数，请通过测试避免未定义的行为：

(((len < std::numeric_limits<UIntType>::digits)
     ? UIntType(1)<<len
     : 0) - UIntType(1)) << pos

（如果pos也有可能≥std::numeric_limits<UIntType>::digits，你需要再做一次三元运算测试。）

您还可以使用：

(UIntType(1)<<(len>>1)<<((len+1)>>1) - UIntType(1)) << pos

以三个额外的移位运算符为代价避免了三元运算；我怀疑它是否会更快，但必须进行仔细的基准测试才能确定。

Answer 2

最快的方法？我会使用这样的东西：

template <class T>
constexpr T make_mask(std::size_t pos, std::size_t len)
{
  return ((static_cast<T>(1) << len)-1) << pos;
}

Answer 3

也许使用 table？对于类型 uint32_t 你可以这样写：

static uint32_t masks[] = { 0x0, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f...}; // only 32 such masks
return masks[len] << pos;

无论是int类型，掩码的数量都不是那么多，table可以很容易地通过模板生成。

对于 BMI，也许使用 BZHI？从设置的所有位开始，BZHI 值为 32-len，然后移动 pos.

Answer 4

速度在这里无关紧要，因为表达式是常量，因此由优化器预先计算，并且很可能用作直接操作数。无论你用什么，它都会花费你0个周期。

Answer 5

这里最大的问题是可能的输入范围。在 C 中，shifts with a count larger than the type width are Undefined Behaviour。但是，看起来 len 可以有意义地从 0 到类型宽度。例如uint32_t 有 33 种不同的长度。当 pos=0 时，我们得到从 0 到 0xFFFFFFFF 的掩码。（为了清楚起见，我只是假设 32 位英文和 asm，但使用通用 C++）。

如果我们可以排除该范围的任一端作为可能的输入，则只有 32 种可能的长度，我们可以使用左移或右移作为构建块。（使用 assert() 验证调试版本中的输入范围。）

我放了几个版本的函数（来自其他答案） on the Godbolt compiler explorer 用一些宏来用常量 len、常量 pos 或两个输入变量编译它们。有些人比其他人做得更好。 KIIV 在其有效范围内看起来不错 (len=0..31, pos=0..31).

此版本适用于 len=1..32 和 pos=0..31。它生成的 x86-64 asm 比 KIIV 稍差，所以如果它在没有额外检查的情况下工作，请使用 KIIV。

// right-shift a register of all-ones, then shift it into position.
// works for len=1..32 and pos=0..31
template <class T>
constexpr T make_mask_PJC(std::size_t pos, std::size_t len)
{
//  T all_ones = -1LL;
//  unsigned typebits = sizeof(T)*CHAR_BIT;  // std::numeric_limits<T>::digits
//  T len_ones = all_ones >> (typebits - len);
//  return len_ones << pos

  static_assert(std::numeric_limits<T>::radix == 2, "T isn't an integer type");
  return static_cast<T>(-1LL) >> (std::numeric_limits<T>::digits - len) << pos;  // pre-C++14 constexpr needs it all in one statement
}

// Same idea, but mask the shift count the same way x86 shift instructions do, so the compiler can do it for free.
// Doesn't always compile to ideal code with SHRX (BMI2), maybe gcc only knows about letting the shift instruction do the masking for the older SHR / SHL instructions
uint32_t make_mask_PJC_noUB(std::size_t pos, std::size_t len)
{
  using T=uint32_t;

  static_assert(std::numeric_limits<T>::radix == 2, "T isn't an integer type");

  T all_ones = -1LL;
  unsigned typebits = std::numeric_limits<T>::digits;
  T len_ones = all_ones >> ( (typebits - len) & (typebits-1));     // the AND optimizes away
  return len_ones << (pos & (typebits-1));

//  return static_cast<T>(-1LL) >> (std::numeric_limits<T>::digits - len) << pos;  // pre-C++14 constexpr needs it all in one statement
}

如果 len 可以是 [0..32] 中的任何值，我对高效的无分支代码没有任何好主意。也许分支是要走的路。

uint32_t make_mask_fullrange(std::size_t pos, std::size_t len)
{
  using T=uint32_t;

  static_assert(std::numeric_limits<T>::radix == 2, "T isn't an integer type");

  T all_ones = -1LL;
  unsigned typebits = std::numeric_limits<T>::digits;
  //T len_ones = all_ones >> ( (typebits - len) & (typebits-1));
  T len_ones = len==0 ? 0 : all_ones >> ( (typebits - len) & (typebits-1));
  return len_ones << (pos & (typebits-1));

//  return static_cast<T>(-1LL) >> (std::numeric_limits<T>::digits - len) << pos;  // pre-C++14 constexpr needs it all in one statement
}

从位置 i 开始生成 n 个掩码的最快方法

Fastest way to produce a mask with n ones starting at position i

c++

optimization

bit-manipulation

bitmask