Optimize std::midpoint for signed integers

[Aj0SK]

Summary

Idea of algorithm is based on finding floored "average" of numbers using bit hack.
Then we want to add -1/+1 only if the numbers have different parity.
We can make this decisions only using bit operators.

You can find benchmark of this algorithm against two older here ->
http://quick-bench.com/hqhZWR7IB4IoUj3aLTN28dOUuPY . In this benchmark
you can see that algorithm works faster for signed types and equally
fast for unsigned types. Even if this algorithm uses more instructions it has higher
Block RThroughput as ilustrated here -> https://godbolt.org/z/5TDmr4 .

[Aj0SK]

Maybe I would add explanation why the term

(__a & __b) + ((__a ^ __b) >> 1)

calculates the floored average. Adding a and b can be rewritten as a + b = (a ^ b) + ((a & b) << 1) . After this we have to divide a+b by 2. This can be done also using shifting to right by 1. After this we get (a + b)/2 = ((a ^ b) >>1) + (a & b).

libcxx/include/numeric

 
 #if _LIBCPP_STD_VER > 17
 template <class _Tp>
 _LIBCPP_INLINE_VISIBILITY constexpr
 enable_if_t<is_integral_v<_Tp> && !is_same_v<bool, _Tp> && !is_null_pointer_v<_Tp>, _Tp>
 midpoint(_Tp __a, _Tp __b) noexcept
 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
 {
-    using _Up = std::make_unsigned_t<_Tp>;
-    constexpr _Up __bitshift = std::numeric_limits<_Up>::digits - 1;
-
-    _Up __diff = _Up(__b) - _Up(__a);
-    _Up __sign_bit = __b < __a;
-
-    _Up __half_diff = (__diff / 2) + (__sign_bit << __bitshift) + (__sign_bit & __diff);
-
-    return __a + __half_diff;
+    _Tp floored_avg = (__a & __b) + ((__a ^ __b) >> 1);
+    _Tp shift =  (__a ^ __b)&(__a >__b);
+    return floored_avg + shift;
 }
 
 
 template <class _TPtr>
 _LIBCPP_INLINE_VISIBILITY constexpr
 enable_if_t<is_pointer_v<_TPtr>
              && is_object_v<remove_pointer_t<_TPtr>>
              && ! is_void_v<remove_pointer_t<_TPtr>>