Bit-shifting left and discarding bits

Question

Let's consider the function (one of possible implementations of it) which would zero out right N bits of an unsigned short value (or any other unsigned integral type). The possible implementation could look like following:

template<unsigned int shift>
unsigned short zero_right(unsigned short arg) {
  using type = unsigned short;

  constexpr type mask = ~(type(0));
  constexpr type right_zeros = mask << shift; // <-- error here
  return arg & right_zeros;
}

int check() {
  return zero_right<4>(16);
}

With this code, all compilers I have access to complain, in one way or another, about possible overflow. CLang is the most explicit one, with following clear message:

error: implicit conversion from 'int' to 'const type' (aka 'const unsigned short') changes value from 1048560 to 65520 [-Werror,-Wconstant-conversion]

This code looks well defined and clear as day to me, yet when 3 compilers complain, I am becoming very nervous. Am I missing something here? Is there really a chance something fishy is happening?

P.S. While alternative implementations of zeriong out left X bits might be welcome and interesting, the primary focus of this question is of validity of code as posted.

Answer 1

From the C++11 Standard:

5.8 Shift operators [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 expression

mask << shift;

is evaluated after integral promotion is applied to mask. Hence, it evaluates to 1048560 if sizeof(unsigned short) is 2, which explains the message from clang.

One way to avoid the overflow problem is to right shift first before performing a left shift, and move that to a function of its own.

template <typename T, unsigned int shift>
constexpr T right_zero_bits()
{
   // ~(T(0)) performs integral promotion, if needed
   // T(~(T(0))) truncates the number to T, if needed.
   return (T(~(T(0))) >> shift ) << shift;
}

template<unsigned int shift>
unsigned short zero_right(unsigned short arg) {
   return arg & right_zero_bits<unsigned short, shift>();
}

Answer 2

Yes, as you suspect, even after suppressing the compiler diagnostics, your code is strictly speaking not fully portable because of the promotion from unsigned short to signed int, bit arithmetic being done in signed int, and then signed int being converted back to unsigned short. You've managed to avoid undefined behaviour (I think, after a quick look), but the result is not guaranteed to be what you are hoping for. (type)~(type)0 is not required to correspond to "all bits one" in type type; it's already iffy before the shift.

To get something fully portable, simply make sure you do all your arithmetic in at least unsigned int (wider types if necessary, but never narrower). Then there won't be any promotions to signed types to worry about.

template<unsigned int shift>
unsigned short zero_right(unsigned short arg) {
  using type = unsigned short;

  constexpr auto mask = ~(type(0) + 0U);
  constexpr auto right_zeros = mask << shift;
  return arg & right_zeros;
}

int check() {
  return zero_right<4>(16);
}

Answer 3

I don't know if this is exactly what you want, but it compiles:

template<unsigned int shift>
unsigned short zero_right(unsigned short arg) {
  using type = unsigned short;

  //constexpr type mask = ~(type(0));
  type right_zeros = ~(type(0));
  right_zeros <<= shift;
  return arg & right_zeros;
}

int check() {
  return zero_right<4>(16);
}

---

UPDATE:

Seems like you simply hushed the compiler by making sure it has no idea what is going on with the types.

No

First you get right_zeros with value FFFF (from ~0). Normally, ~0 is FFFFFFFFFFFFFF... but because you're using u16, you get FFFF.

Then, shift by 4 produces FFFF0 [calculation is extended to 32 bits], but when stored back, only the rightmost 16 bits remain, so the value is FFF0

This is perfectly legal and defined behavior and you're taking advantage of the truncation. The compiler is not "being fooled". Actually, it works fine with or without truncation.

You could make right_zeros into u32 or u64 if you wished, but then you'd need to add right_zeros &= 0xFFFF

If there is an undefined behavior (the very essence of my question!) you simply made it undetectable.

There is no UB based on the totality of your code, no matter what the compiler says.

Actually, Tavian got it. Use an explicit cast:

constexpr type right_zeros = (type) (mask << shift); // now clean

This is telling the compiler, amongst other things, that you want the truncation to 16 bits.

If there were UB, then the compiler should still complain.

Answer 4

The message seems pretty plain:

error: implicit conversion from 'int' to 'const type' (aka 'const unsigned short') changes value from 1048560 to 65520 [-Werror,-Wconstant-conversion]

mask << shift has value 1048560 (arising from 65535 << 4), and you assign it to unsigned short, which is defined to adjust the value mod 65536, giving 65520.

This last conversion is well-defined. The error message is because you passed compiler flags -Werror,-Wconstant-conversion requesting to get an error message in this situation anyway. If you don't want this error then don't pass those flags.

---

Although this particular usage was well-defined, there could be undefined behaviour for some inputs (namely, shift being 16 or greater, if you are on a 32-bit int system). So you should fix the function.

To fix the function you need to be more careful in the unsigned short case, because of the supremely annoying rule about integer promotion of unsigned short to signed int.

Here's one solution a bit different from the other offerings.. avoid the shift issue entirely, works for any shift size:

template<unsigned int shift, typename T>
constexpr T zero_right(T arg)
{
    T mask = -1;
    for (int s = shift; s--; ) mask *= 2u;
    return mask & arg;
}

// Demo
auto f() { return zero_right<15>((unsigned short)65535); }  //  mov eax, 32768