¿Qué técnica específica de aritmética a prueba de desbordamiento emplea **std::midpoint** para enteros con signo que la distingue del cálculo de diferencia de punteros usado para elementos de un array, y por qué la sustracción de punteros no requiere protección equivalente contra desbordamiento?

Respuesta a la pregunta

Historia de la pregunta

Antes de C++20, calcular la media aritmética de dos enteros o punteros requería implementación manual, típicamente a través de la expresión ingenua (a + b) / 2. Este enfoque, sin embargo, invoca comportamiento indefinido cuando la suma excede el valor máximo representable por el tipo. std::midpoint fue estandarizado en C++20 dentro del encabezado <numeric> para proporcionar una solución portátil, constexpr y noexcept que garantiza resultados correctos en todo el dominio de tipos integrales y de punteros sin activar desbordamiento de enteros con signo.

El problema

El desbordamiento de enteros con signo es comportamiento indefinido en C++, incluso con el mandato de complemento a dos de C++20. Al promediar dos enteros con signo grandes positivos (por ejemplo, cerca de INT_MAX), su suma desborda. De manera similar, para dos enteros negativos grandes, la suma puede estar por debajo del límite. Aunque la aritmética de punteros también tiene comportamiento indefinido en caso de desbordamiento, la diferencia entre dos punteros en el mismo array está garantizada para encajar dentro de std::ptrdiff_t, eliminando el riesgo de desbordamiento presente en la adición de enteros. El desafío es implementar un algoritmo de promediado para enteros que evite el desbordamiento inherente a la adición mientras mantiene la corrección para entradas de signo mixto.

La solución

Para enteros con signo, std::midpoint evita el desbordamiento convirtiendo los operandos a sus contrapartes sin signo antes de la sustracción. Calcula el promedio como a - (unsigned_type(a) - b) / 2 cuando a > b, o el equivalente simétrico en caso contrario. Esto aprovecha la aritmética de módulo bien definida de los tipos sin signo para calcular la media distancia entre los números sin crear jamás un valor intermedio cuya magnitud exceda las entradas. Para punteros, la implementación simplemente utiliza first + (last - first) / 2, ya que la diferencia (last - first) está bien definida y es representable, y al dividirla por dos se asegura que la suma posterior permanezca dentro del rango válido del 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; // Comportamiento indefinido: desbordamiento
    int safe = std::midpoint(a, b); // Bien definido: devuelve max - 6
    
    int arr[] = {1, 2, 3, 4, 5};
    int* mid = std::midpoint(&arr[0], &arr[4]); // Apunta a arr[2]
}

Situación de la vida real

Descripción del problema

En una plataforma de comercio de alta frecuencia, el sistema necesitaba calcular el punto medio temporal entre dos marcas de tiempo de órdenes representadas como std::int64_t nanosegundos desde la época Unix. Durante las pruebas de estrés cerca de la apertura del mercado, cuando las marcas de tiempo se acercaban a INT64_MAX, el cálculo legado (t1 + t2) / 2 causaba fallos intermitentes debido a desbordamiento de enteros con signo, corrompiendo la lógica de la cola de prioridad del motor de coincidencia de órdenes.

Diferentes soluciones consideradas

Solución 1: Usar tipos de precisión extendida incorporados El equipo consideró hacer un casting a __int128_t para el cálculo intermedio, y luego volver a hacer un casting. Este enfoque garantizaba aritmética correcta en compiladores compatibles (GCC, Clang, MSVC). Sin embargo, carecía de portabilidad a objetivos embebidos con estricto cumplimiento de C++17 e introducía sutiles regresiones de rendimiento en arquitecturas de 32 bits donde la emulación de 128 bits es costosa.

Solución 2: Casting a aritmética sin signo Se propuso convertir ambas marcas de tiempo a std::uint64_t, realizar el promedio y volver a convertir. Si bien esto evita desbordamientos para valores positivos, produce resultados definidos por la implementación al tratar con marcas de tiempo históricas (valores negativos bajo la representación con signo) porque la conversión sin signo de valores negativos da como resultado magnitudes positivas grandes (envoltura de complemento a dos), lo que hace que el promedio sea matemáticamente incorrecto para cálculos que cruzan cero.

Solución 3: Ramificación manual con verificaciones de desbordamiento Se consideró implementar una función personalizada que verificara los signos de los operandos y usara condicionalmente a + (b - a)/2 o manipulación a nivel de bits. Esto proporcionó corrección pero añadió sobrecarga de ramificación y complejidad. Mantener esta lógica a través de múltiples dominios numéricos (coordenadas, precios, marcas de tiempo) violaba el principio DRY e introducía riesgos de errores de mantenimiento.

Solución 4: Adoptar C++20 std::midpoint Actualizar la cadena de herramientas a C++20 y utilizar std::midpoint proporcionó una abstracción sin sobrecostos que manejaba correctamente todos los casos límite, incluidas las entradas de signo mixto y valores cercanos a los límites del dominio de enteros.

Solución elegida y resultado

El equipo seleccionó Solución 4, migrando la capa de cálculo a C++20. El cambio eliminó los fallos por desbordamiento en producción, redujo la base de código en 200 líneas de utilidades matemáticas seguras personalizadas y mejoró la localidad de caché al eliminar la lógica de ramificación. Las pruebas de regresión confirmaron un rendimiento idéntico al enfoque ingenuo en x86-64, con el beneficio adicional de evaluación constexpr para constantes de tiempo de compilación.

Lo que los candidatos a menudo pasan por alto

Pregunta 1: ¿Por qué no es suficiente convertir enteros con signo a tipos sin signo para un cálculo de punto medio genérico?

Respuesta Si bien la aritmética sin signo envuelve en módulo 2^N y evita desbordamientos, convertir un entero con signo negativo a sin signo da como resultado un valor positivo grande (por ejemplo, -1 se convierte en UINT_MAX). Promediar una marca de tiempo negativa y positiva a través de aritmética sin signo produce un resultado cerca del medio del rango sin signo, no el promedio con signo correcto. std::midpoint preserva el signo y redondea correctamente hacia el primer argumento cuando la diferencia es impar, manejando el bit de signo adecuadamente sin depender de la envoltura sin signo para el resultado final.

Pregunta 2: ¿Bajo qué restricción específica del modelo de objetos invoca std::midpoint para punteros comportamiento indefinido?

Respuesta std::midpoint requiere que ambos punteros apunten a elementos del mismo objeto de array (o uno más allá del último elemento). Si los punteros se refieren a diferentes arrays o memoria no relacionada, el comportamiento es indefinido porque la expresión last - first (utilizada internamente) solo está definida para punteros dentro del mismo array. Esta es una distinción sutil del punto medio de enteros; los candidatos a menudo asumen que funciona como un simple promedio numérico y pasan por alto los estrictos requisitos de aliasing y del modelo de objetos para la aritmética de punteros.

Pregunta 3: ¿Cómo se comporta std::midpoint de manera diferente para tipos de punto flotante en comparación con enteros, particularmente con respecto a los valores NaN?

Respuesta Para tipos de punto flotante, std::midpoint previene el desbordamiento y el subdesbordamiento en la suma (que podría producir infinito o cero incorrectamente) mediante una estrategia definida por la implementación, a menudo equivalente a a/2 + b/2. Fundamentalmente, si uno de los argumentos es NaN, std::midpoint devuelve NaN. Si un argumento es infinito positivo y el otro infinito negativo, devuelve NaN (indeterminado), mientras que el punto medio entero simplemente desbordaría o envolvería. Los candidatos a menudo suponen que realiza aritmética simple sin considerar las reglas de propagación de valores especiales de IEEE 754.