Fastest function to set bits to one between two bits in an unsigned integer

Question

I have an algorithm for simulations on supercomputers that will need the use of a lot of bit manipulations. Some operations will need masks and particularly a function like this:

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
}

that will generate a mask of type Type where the bits in the range [first, last[ are set to 1 (first and last are runtime variables)

For example:

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

I will need hundreds of billions of these masks so I need this function to be as optimized as possible (but in plain standard C++11). How to do that ?

Answer 1

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

Answer 2

You could make a lookup table and the cost would be a single memory read. If you're using 32-bit elements, the table only needs to be 32x32 = 1024 words in memory (4 kilobytes), so it'll stay in cache if you're using it heavily. Even for 64-bit elements, a 64x64 lookup is only 4096 words (32 kilobytes).

Answer 3

This is an extract from the standard:

Shift operators

[expr.shift]

... The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

That's why the expression '(1 << last) - (1 << first)' does not work when last == sizeof(Type)*CHAR_BIT. I propose you another alternative that computes values at compile-time when possible. See the following example:

#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");
}