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.