Integer version of c++ standard library midpoint

Question

I was extremely annoyed by the lengthy, edge-case-galore explanation of integer version of C++ standard library mindpoint implementation here, so I made my own simple 2's complement version. I present it for your judgement.

The general idea is to carry out a + (b-a)/2 in a wider signed integer that won't ever overflow. Say a and b are N bit integers. Consider them as imaginary signed (2's complement) N+1 bit integers. The obvious magic of 2's complement is that we can carry out addition/subtraction as usual, so first we obtain the lower N bits of the hypothetical N+1 bit difference,

Unsigned diff = Unsigned(b) - Unsigned(a);

working with unsigned type to avoid signed overflow UB. We don't really have the +1 bit, so just imagine sign extension also happens. We only care about lower N bits anyway since we know the final half difference has to fit there. Problem is - we can't do division in this straightforward way, so we have to branch, based on the sign of the final result.

• If N+1 bit difference was negative (highest/sign bit set), we jump through hoops:
  Negate/abs (2's complement approved as subtraction 0-diff).
  Unsigned negative_2x = -diff;
  Divide (it works cause sign bit is now guaranteed 0).
  negative_2x /= 2;
  Now we can fit this halved difference back into our original N bit signed int, so we convert it back and negate to restore the original sign.
  Integer negative = -Integer(negative_2x);
  Converting first is important to avoid signed overflow UB again. If original Integer was unsigned this still works, since the wrapping behavior is consistent with 2's complement.

• Otherwise if difference was positive, it fully fit in N bits unsigned, and half of it should fit in signed, no hoops:
  Integer positive = diff / 2;

The actual branch looks like this to encourage conditional move, not that compilers care...

return a + (b < a ? negative : positive);

The code by itself with a primitive/stand-in function signature, for the purposes of copying into an IDE and compiling:

#include <type_traits>

template<typename Integer, typename Unsigned = std::make_unsigned_t<Integer>>
Integer midpoint(Integer a, Integer b)
{
    Unsigned diff = Unsigned(b) - Unsigned(a);

    Unsigned negative_2x = -diff;
    negative_2x /= 2;
    Integer negative = -Integer(negative_2x);

    Integer positive = diff / 2;

    return a + (b < a ? negative : positive);
}

Also available here, passes all the libstdc++ and libc++ unit tests for integers.

Answer 1

Naming things

The variable names are not very clear. I assume the _2x stands for "2's complement" instead for "times 2", but for someone who doesn't know the context, it will be hard to follow. I'm not sure what the best way to name them is though, but as shown below you can avoid the issue altogether.

Don't use a template parameter for a derived type

If you make Unsigned a template parameter, it means someone can override it to something nonsensical. If you want to have a named type that is a derivative of another type, use using inside the function body:

template<typename Integer>
Integer midpoint(Integer a, Integer b)
{
    using Unsigned = std::make_unsigned_t<Integer>;
    ...
}

Simplifying the code

Most of the temporary variables can be removed. I would keep the variable diff, as it is the most important one where the casts are essential, and since it is used twice:

template<typename Integer>
Integer midpoint(Integer a, Integer b)
{
    using Unsigned = std::make_unsigned_t<Integer>;
    Unsigned diff = Unsigned(b) - Unsigned(a);
    return a + (b < a ? -Integer(Unsigned(-diff) / 2) : Integer(diff / 2));
}

The return expression is still reasonably short, and I don't think any information was lost. Adding some comments explaining why the casts are necessary would be helpful though.