What specific overflow-safe arithmetic technique does **std::midpoint** employ for signed integers that distinguishes it from the pointer difference calculation used for array elements, and why does pointer subtraction not require equivalent overflow protection?

Answer to the question

History of the question

Before C++20, calculating the arithmetic mean of two integers or pointers required manual implementation, typically via the naive expression (a + b) / 2. This approach, however, invokes undefined behavior when the sum exceeds the maximum value representable by the type. std::midpoint was standardized in C++20 within the <numeric> header to provide a portable, constexpr, and noexcept solution that guarantees correct results across the entire domain of integral and pointer types without triggering signed integer overflow.

The problem

Signed integer overflow is undefined behavior in C++, even with C++20's two's complement mandate. When averaging two large positive signed integers (e.g., near INT_MAX), their sum overflows. Similarly, for two large negative integers, the sum may underflow. While pointer arithmetic also has undefined behavior on overflow, the difference between two pointers into the same array is guaranteed to fit within std::ptrdiff_t, eliminating the overflow risk present in integer addition. The challenge is implementing an averaging algorithm for integers that avoids the overflow inherent in addition while maintaining correctness for mixed-sign inputs.

The solution

For signed integers, std::midpoint avoids overflow by converting the operands to their unsigned counterparts before subtraction. It computes the average as a - (unsigned_type(a) - b) / 2 when a > b, or the symmetric equivalent otherwise. This leverages the well-defined modulo arithmetic of unsigned types to calculate the half-distance between the numbers without ever creating an intermediate value whose magnitude exceeds the inputs. For pointers, the implementation simply uses first + (last - first) / 2, as the difference (last - first) is well-defined and representable, and halving it ensures the subsequent addition stays within the valid range of the array.

#include <numeric>
#include <limits>
#include <iostream>

int main() {
    int a = std::numeric_limits<int>::max() - 10;
    int b = std::numeric_limits<int>::max() - 2;
    
    // int naive = (a + b) / 2; // Undefined behavior: overflow
    int safe = std::midpoint(a, b); // Well-defined: returns max - 6
    
    int arr[] = {1, 2, 3, 4, 5};
    int* mid = std::midpoint(&arr[0], &arr[4]); // Points to arr[2]
}

Situation from life

Problem description

In a high-frequency trading platform, the system needed to calculate the temporal midpoint between two order timestamps represented as std::int64_t nanoseconds since the Unix epoch. During stress testing near market open, when timestamps approached INT64_MAX, the legacy calculation (t1 + t2) / 2 caused intermittent crashes due to signed integer overflow, corrupting the order matching engine's priority queue logic.

Different solutions considered

Solution 1: Use built-in extended precision types The team considered casting to __int128_t for the intermediate calculation, then casting back. This approach guaranteed correct arithmetic on supported compilers (GCC, Clang, MSVC). However, it lacked portability to embedded targets with strict C++17 compliance and introduced subtle performance regressions on 32-bit architectures where 128-bit emulation is costly.

Solution 2: Unsigned arithmetic cast Converting both timestamps to std::uint64_t, performing the average, and converting back was proposed. While this avoids overflow for positive values, it produces implementation-defined results when dealing with historical timestamps (negative values under the signed representation) because the unsigned conversion of negative values yields large positive magnitudes (2's complement wrap-around), rendering the average mathematically incorrect for cross-zero calculations.

Solution 3: Manual branching with overflow checks Implementing a custom function checking the signs of operands and conditionally using a + (b - a)/2 or bitwise manipulation was considered. This provided correctness but added branching overhead and complexity. Maintaining this logic across multiple numerical domains (coordinates, prices, timestamps) violated the DRY principle and introduced risk of maintenance errors.

Solution 4: Adopt C++20 std::midpoint Upgrading the toolchain to C++20 and utilizing std::midpoint provided a zero-overhead abstraction that correctly handled all edge cases, including mixed-sign inputs and values near the limits of the integer domain.

Chosen solution and result

The team selected Solution 4, migrating the calculation layer to C++20. The change eliminated the overflow crashes in production, reduced the codebase by 200 lines of custom safe-math utilities, and improved cache locality by removing branching logic. Regression tests confirmed identical performance to the naive approach on x86-64, with the added benefit of constexpr evaluation for compile-time constants.

What candidates often miss

Question 1: Why is casting signed integers to unsigned types insufficient for a generic midpoint calculation?

Answer While unsigned arithmetic wraps modulo 2^N and avoids overflow, converting a negative signed integer to unsigned yields a large positive value (e.g., -1 becomes UINT_MAX). Averaging a negative and positive timestamp via unsigned arithmetic produces a result near the middle of the unsigned range, not the correct signed average. std::midpoint preserves the signedness and correctly rounds towards the first argument when the difference is odd, handling the sign bit properly without relying on unsigned wrap-around for the final result.

Question 2: Under what specific object model constraint does std::midpoint for pointers invoke undefined behavior?

Answer std::midpoint requires that both pointers point to elements of the same array object (or one past the last element). If the pointers refer to different arrays or unrelated memory, the behavior is undefined because the expression last - first (used internally) is only defined for pointers within the same array. This is a subtle distinction from integer midpoint; candidates often assume it works like a simple numerical average and miss the strict aliasing and object model requirements for pointer arithmetic.

Question 3: How does std::midpoint behave differently for floating-point types compared to integers, particularly regarding NaN values?

Answer For floating-point types, std::midpoint prevents overflow and underflow in the sum (which could produce infinity or zero incorrectly) by using an implementation-defined strategy, often equivalent to a/2 + b/2. Crucially, if either argument is NaN, std::midpoint returns NaN. If one argument is positive infinity and the other negative infinity, it returns NaN (indeterminate), whereas integer midpoint would simply overflow or wrap. Candidates frequently assume it performs simple arithmetic without considering the IEEE 754 special value propagation rules.