最快的函数将位设置为无符号整数中的两位之间的位。

Question

我有一个在超级计算机上进行模拟的算法，它需要使用大量的位操作。有些操作需要掩码，特别是像这样的函数：

template <typename Type,
          class = typename std::enable_if<std::is_integral<Type>::value>::type,
          class = typename std::enable_if<std::is_unsigned<Type>::value>::type>
inline Type mask(const std::size_t first, const std::size_t last)
{
     // Something
}

这将生成一个Type类型的掩码，其中范围[first, last[中的位被设置为1 (first和last是运行时变量)。

例如：

mask<unsigned char>(3, 6) -> 00111000

我将需要数千亿的这些面具，所以我需要这个功能尽可能优化(但在普通的标准C++11)。怎么做？

Answer 1

return (1 << last) - (1 << first);

Answer 2

您可以创建一个查找表，只需读取一个内存即可。如果使用32位元素，表只需为内存中的32x32 = 1024字(4千字节)，因此如果大量使用它，它将留在缓存中。即使是64位元素，64x64查找也只有4096个单词(32 32)。

Answer 3

这是标准的摘录：

移位算子

expr.shift

..。如果右操作数为负数，或大于或等于提升的左操作数的位长，则行为是未定义的。

这就是为什么表达式'(1 << last) - (1 << first)‘在最后== sizeof(Type)*CHAR_BIT时不能工作的原因。我建议您在可能的情况下，在编译时计算值的另一种选择。请参见以下示例：

#include <limits>
#include <iostream>
#include <bitset>


template <class Integer>
constexpr Integer ones()
{
    return ~static_cast<Integer>(0);
}


template <class Integer>
constexpr Integer mask(std::size_t first, std::size_t last)
{
    return (ones<Integer>() << first) &
           (ones<Integer>() >> (std::numeric_limits<Integer>::digits - last));
}


//Requires: first is in [0,8) and last is in (0,8]
void print8(std::size_t first, std::size_t last)
{
    std::cout << std::bitset<8>(mask<unsigned char>(first, last)) << '\n';
}

int main()
{
    print8(0,1); //000000001
    print8(2,6); //001111100
    print8(0,8); //111111111
    print8(2,2); //000000000

    static_assert(mask<unsigned char>(0,8) == 255,
                  "It should work at compile-time when possible");
}