Get an n-bit mask avoiding UB when n is equal to the bit width of the type?

I have a small positive integer n, and I use an unsigned integral type to store a mask containing n bits. Often, there is a need to construct a mask with all n bits set. For example, if n is 5, then the mask would be 0b11111u.

The typical way to construct such a mask is to do the following (this example assumes that the mask uses unsigned, but it is possible to write something for any unsigned integral type):

unsigned all_set_mask = (1u << n) - 1u;

However, 1u << n is undefined behaviour if n is exactly equal to the bit width of the unsigned integral type, as seen from [expr.shift#1]:

> The operands shall be of integral or unscoped enumeration type and integral promotions are performed. The type of the result is that of the promoted left operand. The behavior is undefined if the right operand is negative, or greater than or equal to the width of the promoted left operand.

A reasonable interpretation of "construct a mask with all n bits set" arguably should permit the case when we have exactly as many bits as the bit width of the underlying integral type, and so the typical implementation does not support all reasonable inputs.

Furthermore, on modern processors, the assembly left shift instruction is a no-op when shifting by the bit width, and so all_set_mask might end up being 0, which isn't the expected answer in any case.

Is there an standard-compliant way to rewrite it without resorting to an if-statement or complex bit twiddling? I looked into <bit> but did not see anything of use there.

A simple way is the following:

n == 0 ? 0 : 0xffffffff >> (32 - n)

We can rewrite this slightly to save one instruction on typical architectures where shift counts are modulo register width:

n == 0 ? 0 : 0xffffffff >> (-n & 31)

and then to get rid of the conditional:

(unsigned)(-(signed)n >> 31) >> (-n & 31)

This should compile to just three instructions on typical CPUs (one of the rare cases where assembly is more readable than C++).

Note that this assumes that signed right-shifts are arithmetic shifts, which is pedantically correct only from C++20 on.

You can do this unconditionally with any unsigned type:

(((1u << (n + 1) / 2) - 1u) << n / 2) | ((1u << n / 2) - 1u);

The example with 16-bit unsigned:

#include <iostream>

int main() {
  for (int n = 0; n <= 16; ++n) {
    const uint16_t r = (((1u << (n + 1) / 2) - 1u) << n / 2) | ((1u << n / 2) - 1u);
    std::cout << std::hex << r << " ";
  }
}

// Output: 0 1 3 7 f 1f 3f 7f ff 1ff 3ff 7ff fff 1fff 3fff 7fff ffff

I suggest setting all bits and right shifting away the the unwanted bits.

You still need to test for the edge case when n is 0 though, otherwise it'll shift away all bits, with undefined behavior as a result.

template <class T>
    requires std::is_unsigned_v<T>
constexpr T all_set_mask(unsigned n) {
    if(n == 0) return T{};
    
    constexpr unsigned  bits = sizeof(T) * CHAR_BIT;
    // extra test for too many bits if needed:
    //if(n > bits) return static_cast<T>(-1);
    
    return static_cast<T>(-1) >> (bits - n);
}

Demo

On x86-64, _bextr_u64(UINT64_C(-1), 0, n).