Ответ на вопрос

История вопроса

До C++20 вычисление арифметического среднего для двух целых чисел или указателей требовало ручной реализации, обычно через наивное выражение (a + b) / 2. Однако такой подход вызывает неопределенное поведение, когда сумма превышает максимальное значение, представимое данным типом. std::midpoint была стандартизирована в C++20 в заголовке <numeric>, чтобы предоставить переносимое, constexpr и noexcept решение, которое гарантирует корректные результаты для всех целых и указательных типов без вызова переполнения знакового целого.

Проблема

Переполнение знаковых целых чисел — это неопределенное поведение в C++, даже с мандатом комплементации по модулю 2 в C++20. При вычислении среднего для двух крупных положительных знаковых целых чисел (например, близко к INT_MAX) их сумма вызывает переполнение. Аналогично, для двух больших отрицательных целых чисел сумма может вызвать недополнение. Хотя арифметика указателей также имеет неопределенное поведение при переполнении, разность между двумя указателями в одном массиве гарантированно помещается в std::ptrdiff_t, что устраняет риск переполнения, присутствующий в сложении целых чисел. Задача состоит в том, чтобы реализовать алгоритм усреднения для целых чисел, который избегал бы переполнения, присущего сложению, при этом сохраняя корректность для входных данных со смешанными знаками.

Решение

Для знаковых целых чисел std::midpoint избегает переполнения, конвертируя операнды в их беззнаковые аналоги перед вычитанием. Она вычисляет среднее как a - (unsigned_type(a) - b) / 2, когда a > b, или как симметричный эквивалент в противном случае. Это использует четко определенную модульную арифметику беззнаковых типов для вычисления половинного расстояния между числами, не создавая промежуточного значения, величина которого превышает входные данные. Для указателей реализация просто использует first + (last - first) / 2, так как разность (last - first) четко определена и представима, а деление на два гарантирует, что последующее сложение остается в допустимом диапазоне массива.

#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; // Непределенное поведение: переполнение
    int safe = std::midpoint(a, b); // Четко определено: возвращает max - 6
    
    int arr[] = {1, 2, 3, 4, 5};
    int* mid = std::midpoint(&arr[0], &arr[4]); // Указывает на arr[2]
}

Ситуация из жизни

Описание проблемы

В платформе высокочастотной торговли системе необходимо было вычислить временной средний показатель между двумя временными метками заказов, представленными как std::int64_t наносекунд с момента Unix-эпохи. Во время стресс-тестирования близко к открытию рынка, когда временные метки приближались к INT64_MAX, наследуемое вычисление (t1 + t2) / 2 вызывало случайные сбои из-за переполнения знакового целого, нарушая логику приоритетной очереди механизма сопоставления заказов.

Разные рассматриваемые решения

Решение 1: Использовать встроенные расширенные типы с плавающей запятой Команда рассматривала возможность преобразования в __int128_t для промежуточного вычисления, а затем обратного преобразования. Этот подход гарантировал правильную арифметику на поддерживаемых компиляторах (GCC, Clang, MSVC). Однако он не имел переносимости для встроенных целей с строгим соблюдением C++17 и ввел тонкие регрессии производительности на 32-разрядных архитектурах, где эмуляция 128 бит стоит дорого.

Решение 2: Преобразование в беззнаковую арифметику Предложили преобразовать обе временные метки в std::uint64_t, выполнить усреднение и преобразовать обратно. Хотя это избегает переполнения для положительных значений, оно дает определенные результаты реализации при работе с историческими временными метками (отрицательные значения в знаковом представлении), поскольку беззнаковое преобразование отрицательных значений дает большие положительные величины (зацикливание по модулю 2), что делает усреднение математически некорректным для расчетов пересечения нуля.

Решение 3: Ручная ветвь с проверками переполнения Рассмотрели реализацию пользовательской функции, проверяющей знаки операндов и условно использующей a + (b - a)/2 или побитовые манипуляции. Это обеспечивало корректность, но добавляло накладные расходы и сложность ветвления. Поддержание этой логики в нескольких числовых областях (координаты, цены, временные метки) нарушало принцип DRY и вводило риск ошибок во время обслуживания.

Решение 4: Принять C++20 std::midpoint Обновление инструментов до C++20 и использование std::midpoint обеспечивало абстракцию с нулевыми накладными расходами, которая корректно обрабатывала все крайние случаи, включая входные данные со смешанными знаками и значения, близкие к пределам знаковой области чисел.

Выбранное решение и результат

Команда выбрала Решение 4, мигрировав слой вычислений на C++20. Изменение устранило сбои из-за переполнения в производстве, уменьшило кодовую базу на 200 строк пользовательских утилит безопасной арифметики и улучшило локальность кеша за счет удаления логики ветвления. Регрессионные тесты подтвердили идентичную производительность по сравнению с наивным подходом на x86-64, с добавленной возможностью constexpr для констант времени компиляции.

Что кандидаты часто упускают

Вопрос 1: Почему преобразование знаковых целых чисел в беззнаковые типы недостаточно для общего вычисления средних значений?

Ответ Хотя беззнаковая арифметика зацикливается по модулю 2^N и избегает переполнения, преобразование отрицательного знакового целого в беззнаковый дает большое положительное значение (например, -1 становится UINT_MAX). Усреднение отрицательной и положительной временной метки через беззнаковую арифметику дает результат, близкий к середине беззнакового диапазона, а не правильное знаковое среднее. std::midpoint сохраняет знаковость и корректно округляет к первому аргументу, когда разница нечетная, правильно обрабатывая знак без привязки к зацикливанию беззнакового типа для конечного результата.

Вопрос 2: Под каким конкретным ограничением модели объектов возникает неопределенное поведение у std::midpoint для указателей?

Ответ std::midpoint требует, чтобы оба указателя указывали на элементы одного и того же объекта массива (или один за последним элементом). Если указатели относятся к разным массивам или несвязанной памяти, поведение неопределенно, поскольку выражение last - first (используемое внутренне) определено только для указателей внутри одного массива. Это тонкое различие от усреднения целых чисел; кандидаты часто предполагают, что это работает как простое числовое среднее, и упускают строгие требования по алиасингу и модели объектов для арифметики указателей.

Вопрос 3: Как std::midpoint ведет себя по-другому для типов с плавающей запятой по сравнению со знаковыми числами, особенно относительно значений NaN?

Ответ Для типов с плавающей запятой std::midpoint предотвращает переполнение и недополнение в сумме (которые могут неправильно производить бесконечность или ноль), используя стратегию, определяемую реализацией, которая часто эквивалентна a/2 + b/2. Критически, если один из аргументов является NaN, std::midpoint возвращает NaN. Если один аргумент является положительной бесконечностью, а другой — отрицательной бесконечностью, он возвращает NaN (неопределенно), тогда как усреднение целых чисел просто переполнится или зациклится. Кандидаты часто предполагают, что она выполняет простую арифметику, не учитывая правила пропаганды специальных значений IEEE 754.