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

2021-12-20 00:00:00 optimization bit-manipulation c++ bitmask

从位置pos开始生成len位设置为1的掩码的最快方法是什么(就常见现代架构的cpu周期而言):

What is the fastest way (in terms of cpu cycles on common modern architecture), to produce a mask with len bits set to 1 starting at position pos:

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 函数可以提供帮助?

Plus, is there any compiler intrinsics or BMI function that can help?

推荐答案

如果用starting at pos"表示掩码的最低位在2对应的位置pos(如你的例子):

If by "starting at pos", you mean that the lowest-order bit of the mask is at the position corresponding with 2pos (as in your example):

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

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

If it is possible that len is ≥ the number of bits in UIntType, avoid Undefined Behaviour with a test:

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

(如果 pos 也有可能是 ≥ std::numeric_limits，您将需要另一个三元运算测试.)

(If it is also possible that pos is ≥ std::numeric_limits<UIntType>::digits, you'll need another ternary op test.)

您也可以使用:

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

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

which avoids the ternary op at the cost of three extra shift operators; I doubt whether it would be faster but careful benchmarking would be necessary to know for sure.

相关文章