
Казалось бы: сложно отыскать формулу проще, чем нахождение среднего арифметического. Однако код — не формула, вдобавок, если вы пишете на С++, то разного (и в основном неприятного) рода сюрпризы могут ожидать вас где угодно.
Постановка задачи: реализовать функцию uint32_t average(uint32_t a, uint32_t b), не используя типов шире, чем uint32_t, и затем обобщить этот подход на произвольное количество аргументов.
Математик Давид Гилберт отвечает на вопросы:
— Какая задача сейчас для науки наиболее важна?
— Поймать муху на обратной стороне Луны!
— А кому это надо?
— Это никому не надо. Но подумайте над тем, сколько важных сложнейших задач надо решить, чтобы это осуществить!
Два значения
Сразу оговорюсь: всюду под средним будет пониматься результат деления суммы аргументов нацело на их количество, иначе говоря, average(1, 1) это 1, и average(1, 2) это тоже 1, потому что
Итак, сначала рассмотрим вариант наивный и, очевидно, неверный:
uint32_t average(uint32_t a, uint32_t b)
{
return (a + b) / 2;
}
К сожалению или нет, но такое буквальное переложение школьной формулы в код будет очень часто давать неверный ответ, например: average(0x80000000, 0x80000000) будет равно нулю, а должно быть равно 0x80000000 — это происходит из-за переполнения uint32_t при сложении a + b, при этом важно заметить, что и аргументы, и конечный результат во всех случаях влезают в тип uint32_t . Таким образом, задача-то вполне корректна, в отличие от кода.
Первая пришедшая мне в голову идея была основана лишь на интуиции и заключалась в следующем исправлении:
uint32_t average(uint32_t a, uint32_t b)
{
return a / 2 + b / 2;
}
Проблемы с переполнением тут, конечно, быть не может, потому что a /2 и b /2 не превосходят половины от numeric_limits<uint32_t >::max(), но проблема с неправильными ответами остаётся актуальной: average(3, 3) будет равен...2, а не 3.
Несложно догадаться, если оба аргумента нечётны, при делении нацело на два отбрасывается два раза по половинке от единицы, поправим это:
uint32_t average(uint32_t a, uint32_t b)
{
return a / 2 + b / 2 + (a & b & 1);
}
Этот вариант — верный, но методически бесполезный: для обобщения его даже для трёх аргументов придётся внести правки, чем мы сейчас и займёмся.
А ещё есть способ избавиться от обоих делений, используя немного битовой магии:
(a & b) + ((a ^ b) >> 1).
Однако обобщить эти способы на большее количество чисел не представляется возможным.
Три значения
Прежде чем идти дальше, повторим материальную часть: для пары натуральных чисел a и b (b не равно нулю) существует единственное представление вида:
Если мы запишем все три значения в вышеприведённом виде, учтя, что b = 3, затем перегруппируем их, а уже потом разделим, то, во-первых, очевидно, ничего не изменится (от перестановки мест слагаемых сумма не меняется), а, во-вторых, получится следующее:
uint32_t average(uint32_t x1, uint32_t x2, uint32_t x3)
{
return x1 / 3 + x2 / 3 + x3 / 3 + (x1 % 3 + x2 % 3 + x3 % 3) / 3;
}
Проговорим алгоритм словами: сначала сложим все частные, потом посмотрим: «добежали ли» остатки до целого значения или нет.
Выглядит неплохо, но может ли здесь быть переполнение? Короткий ответ — нет.
Действительно: x1 / 3 + x2 / 3 + x3 / 3 не превосходит максимального значения numeric_limits<uint32_t >::max(), а если быть ещё точнее: это будет максимальное из чисел, делимых на три и не превосходящих при этом numeric_limits<uint32_t >::max(). Пожалуй, я его посчитаю:
cout << dec << numeric_limits<uint32_t>::max() - numeric_limits<uint32_t>::max() % 3 << ' ' << numeric_limits<uint32_t>::max() << endl;
Вывод:
4294967295 4294967295
То есть numeric_limits<uint32_t>::max() делится на 3 без остатка (если не верите — сосчитайте сумму его цифр и убедитесь, что она делится на 3), x1 / 3 + x2 / 3 + x3 / 3 будет равно исходному числу, а вторая часть с остатками будет нулевой. Случай, если один или более элементов меньше максимального значения, — довольно технический и проверяемый такими же рассуждениями — не будем тратить на это время.
N значений. Первая попытка
Обобщая код из нашего последнего примера, получаем:
uint32_t average(const vector<uint32_t>& nums)
{
uint32_t res = 0;
uint32_t rem = 0;
uint32_t size = nums.size();
if (!size)
{
return 0;
}
for (const auto& x: nums)
{
res += x / size;
}
for (const auto& x: nums)
{
rem += x % size;
}
return res + rem / size;
}
Отлично, код выглядит, прямо скажем, незамысловато! А вот работает ли?
cout << average({1, 2, 3, 4, 5, 6, 7, 8, 9}) << endl;
Эта строчка предсказуемо выведет 5. Попробуем другой пример:
cout << hex << average(vector<uint32_t>(0x10001, 0x10000)) << endl;
Напомню, что первый аргумент в конструкторе вектора — это количество элементов, и второй — значение этих элементов, вывод будет:
0
Похоже, мы опять столкнулись с переполнением, но ведь выше мы разбирали, почему переполнения возникнуть не может? Или может?
Переполнение не может возникнуть здесь:
for (const auto& x: nums)
{
res += x / size;
}
И переполнение не может возникнуть здесь:
return res + rem / size;
При условии, что rem сам по себе посчитан корректно.
Но оно может возникнуть и возникает здесь:
for (const auto& x: nums)
{
rem += x % size;
}
Проанализируем работу функции с данным вектором:
x / size равно 0, x % size равно самому x т.е. 0x10000, в то же время 0x10000 * 0x10001 = (0x10000 * 0x10000) + 0x10000 — первое слагаемое не влезает в 4 байта и даёт 0 — значит итоговый rem будет 0x10000 и при делении на 0x10001 мы получим 0.
N значений. Чиним алгоритм
В предыдущем абзаце была выявлена проблема с циклом накопления остатка rem — рассмотрим его подробнее. Например, не утруждаясь оперированием большими числами, возьмём вектор из трёх элементов — пусть каждый элемент будет равен 8, тогда x % size равно 2. А есть ли вообще смысл в накоплении суммарного остатка? Нет. Достаточно факта, что остаток превышает или равен модулю (модуль — он же размер вектора в данном контексте) и накопления остатка уже взятого по модулю. Так, на первом шаге мы получим rem = 2, на втором шаге мы не получим 4, вместо этого rem = 1, и инкрементация частного (quotient++).
Воплотим идею в код:
uint32_t average(const vector<uint32_t>& nums)
{
if (!nums.size())
{
return 0;
}
uint32_t size = nums.size();
uint32_t quotient = 0;
uint32_t reminder = 0;
for (const auto& x: nums)
{
quotient += x / size;
uint32_t rem = x % size;
if ((size - reminder) > rem)
{
reminder += rem;
}
else
{
quotient++;
reminder += rem - size;
}
}
return quotient;
}
Здесь в if мы контролируем переполнение, но не переполнение uint32_t, а переполнение нашего модуля (size). Если его нет, то просто накапливаем остаток — иначе пересчитываем остаток уже по модулю (size) и инкрементируем частное (quotient). Тут нужно понимать, что за одну итерацию частное (quotient) может увеличиться не больше чем на 1, потому что и reminder, и rem оба меньше модуля (size) — следовательно, их сумма меньше 2 * size.
Можно убедиться, что предыдущий пример отработает теперь верно, выведя 0x10000:
cout << hex << average(vector<uint32_t>(0x10001, 0x10000)) << endl;
Анализ алгоритма и замеры
В терминах О-большого полученный алгоритм ничем не отличается от своей наивной и страдающей от переполнений версии:
uint32_t naive_average(const vector<uint32_t>& nums)
{
uint32_t sum = 0;
for (const auto& x: nums)
{
sum += x;
}
return sum / nums.size();
}
В обоих случаях количество итераций равно размеру вектора, и в каждой итерации выполняется конечное, не зависящее от размера вектора, число операций — то есть это линейная сложность O(n). Однако в реальном мире
Однако на данный момент это всего лишь гипотеза — нужно подкрепить её результатами измерений.
#include <iostream>
#include <vector>
#include <chrono>
#include <cstdint>
#include <random>
using namespace std;
using namespace std::chrono;
uint32_t average(const vector<uint32_t>& nums) {
if (nums.empty()) {
return 0;
}
uint32_t size = nums.size();
uint32_t quotient = 0;
uint32_t reminder = 0;
for (const auto& x : nums) {
quotient += x / size;
uint32_t rem = x % size;
if ((size - reminder) > rem) {
reminder += rem;
} else {
quotient++;
reminder += rem - size;
}
}
return quotient;
}
uint32_t naive_average(const vector<uint32_t>& nums) {
uint32_t sum = 0;
for (const auto& x : nums) {
sum += x;
}
return sum / nums.size();
}
vector<uint32_t> generate_test_data(size_t size) {
vector<uint32_t> data;
data.reserve(size);
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<uint32_t> dist(0, UINT32_MAX);
for (size_t i = 0; i < size; ++i) {
data.push_back(dist(gen));
}
return data;
}
template<typename Func>
long long measure_time(Func func, const vector<uint32_t>& data, uint32_t& result) {
auto start = high_resolution_clock::now();
result = func(data);
auto end = high_resolution_clock::now();
return duration_cast<milliseconds>(end - start).count();
}
int main() {
vector<size_t> sizes = {100'000, 200'000, 400'000, 800'000, 1'600'000};
cout << "Testing different vector sizes:\n";
for (size_t size : sizes) {
auto data = generate_test_data(size);
uint32_t res_opt, res_naive;
auto time_opt = measure_time(average, data, res_opt);
auto time_naive = measure_time(naive_average, data, res_naive);
cout << "Size: " << size << endl;
cout << " Optimized average: " << time_opt << " ms\t Result: " << res_opt << endl;
cout << " Naive average: " << time_naive << " ms\t Result: " << res_naive << endl;
cout << "----------------------------------------\n";
}
return 0;
}
Собрав этот код с флагами -O3 в релизе, получим следующие результаты:
Testing different vector sizes:
Size: 10000000
Optimized Average: 14 ms Result: 2147686718
Naive average: 2 ms Result: 348
— Size: 20000000
Optimized Average: 25 ms Result: 2147422219
Naive average: 3 ms Result: 203
— Size: 40000000
Optimized Average: 49 ms Result: 2147451718
Naive average: 6 ms Result: 67
— Size: 80000000
Optimized Average: 103 ms Result: 2147364889
Naive average: 13 ms Result: 50
— Size: 160000000
Optimized Average: 200 ms Result: 2147464194
Naive average: 31 ms Result: 8
—
Видно, что версия алгоритма, учитывающая переполнение, медленнее в 7-8 раз наивного алгоритма. Может показаться, что разница весьма внушительна, но на самом деле такая разница вызывает вопросы, потому что деление обычно более чем в 10 раз медленнее сложения.
Железо, на котором запускали тесты: 13th Gen Intel® Core(TM) i7-13700H, 32 Гб ОЗУ.
Если посмотреть, как компилятор оптимизировал naive_average, например, в godbolt, то можно заметить, что компилятор использовал в ней SIMD-инструкции, в то время как в average — нет. В свете этого не столь большая разница в их времени выполнения становится ещё более загадочной, тем не менее — оставим исследование этого феномена до следующего раза (или до ответа в комментариях).


Выводы
Даже простые формулы и привычные математические операции часто утрачивают свои аксиоматические свойства, будучи реализованными на реальном «железе».
Несмотря на это, удалось найти элегантный алгоритм решения исходной задачи. Как это часто бывает, изменение одного из свойств алгоритма, в данном случае расширение области, где он корректен, привело к ухудшению его другой характеристики — времени выполнения.
Ссылки
- C++ Integral Promotions
- Integer Overflow in C++
- Division Algorithm
- SIMD Optimization
- Modular Arithmetic Basics
© 2025 ООО «МТ ФИНАНС»
Telegram-канал со скидками, розыгрышами призов и новостями IT ?

Комментарии (62)
tenzink
03.06.2025 13:34Похоже, что не работает корректно для больших массивов, т.е. таких, у которых size не помещается в uint32
StarPilgrim Автор
03.06.2025 13:34так, такого и не заявлено
tenzink
03.06.2025 13:34А как же `и затем обобщить этот подход на произвольное количество аргументов` и тесты с std::vector?
С другой стороны понятно, что это уже задача со звёздочкой
StarPilgrim Автор
03.06.2025 13:34тут я бы сам своё условие нарушил: раз сам размер не влезает в 32 бита, пришлось бы использовать uint64_t
tenzink
03.06.2025 13:34Можно попробовать придумать алгоритм, где не будет явно использоваться размер, а вектор обрабатывать чанками по 2**32. Range-based-for все 64bit-указатели прячет под капотом
sci_nov
03.06.2025 13:34Можно просто суммировать и накапливать количество переполнений.
haqreu
03.06.2025 13:34Два чая. В кои-то веки можно переполнять переменную без UB :)
И по факту это является вариантом суммирования в переменную большей разрядности, не выходя за рамки задачи не использовать ничего, кроме uint32_t.
sci_nov
03.06.2025 13:34А что значит два чая?
haqreu
03.06.2025 13:34Плохая калька от «I second this», использование которой не выставляет меня в лучшем свете :)
AlexSky
03.06.2025 13:34Вот и выросло поколение...
Это выражение поддержки, пришедшее с имиджборды 2ch (двач). Изначально звучало как "двачую", потом переродилось в "два чая [этому господину]".
haqreu
03.06.2025 13:34Ну да, а «двачую» это искажённое «дваждую», которое является дурацкой калькой с «I second». Я вырос чуть раньше 2ch :)
Damiryh
03.06.2025 13:34Велосипедить сложение с переносом?
sci_nov
03.06.2025 13:34Нет. У ЦПУ есть флаг переноса.
kipar
03.06.2025 13:34а как к нему обратиться на C++? Ведь целевая плафторма может быть какой-нибудь wasm.
haqreu
03.06.2025 13:34А что мешает сделать ассемблерную вставку при сильной необходимости?
(Впрочем, оптимизатор скорее всего велосипед со сравнением превратит ровно в тот ассемблер, что был бы написан руками)
punzik
03.06.2025 13:34Не у всякого. Например, у MIPS и RISC-V нет флагов. Но можно, конечно, просто сравнить результат с операндами - если он меньше любого, то случилось переполнение.
pnmv
03.06.2025 13:34читая о целочисленных преобразованиях (назовем их так), невольно, думаешь о делении сдвигами на два, с накоплением результата.
не удивлюсь, если я где-нибудь промахнулся, но, вот такое "поверхностное представление".
Tuxman
03.06.2025 13:34Всё хорошо, но формул для вычисления средних очень много.
Вот у тебя, Хабра читатель, есть машина? Она показывает среднюю скорость, средний расход? А как она это делает, никогда не задумывался?
nsmcan
03.06.2025 13:34У меня нарисовался такой алгоритм. Пардон, что без форматирования. Прошу сильно не пенять.
Считаем ближайшую степень двойки, большую количества элементов:
2**k >= n
m = 2**k. m всегда >= n
(A1+A2+...+An)/n = (A1+A2+...+An) × 2**k / n × 2**k = (A1+A2+...+An+0+0+...+0m) / 2**k × 2**k / n
Здесь мы добиваем нулям, чтобы общее количество элементов стало m.
Выражение S = (A1+A2+...+An+0+0+...+0m) / 2**k обсчитывется рекурсивным разбиением на пары и сдвигом вправо на 1 бит. Придётся учитывать теряемый бит нечётных чисел.
После чего имеем S × 2**k / n
Это, по идее, можно просчитать без вылета за границы величин.
Я алгоритм не тестировал. Так что если вкралась ошибка, то прошу не серчать
Panzerschrek
03.06.2025 13:34Деления и ветвления на каждой итерации предсказуемо медленны. Проще было бы реализовать сложение с учётом переполнение (с записью старших битов в отдельную переменную) с финальным делением с учётом этих битов. А можно даже этим не заниматься и использовать 64-битные переменные - компиляторы достаточно умны, чтобы выдать аналогичный код на системе без 64-битных инструкций.
https://godbolt.org/z/zzbjqrv3T
dx-77
03.06.2025 13:34Небольшая поправка
натуральных чисел a и b (b не равно нулю)
Натуральные числа они по определению больше нуля
Vytian
03.06.2025 13:34По Бурбаки ноль тоже натуральный, потому что мощности множеств, а не индексы нумерации существующих объектов. По ISO
с нулем. А вот \mathbb{N}^* без нуля.
dx-77
03.06.2025 13:34Ну да, а в России общепринято, что N это 1, 2, 3... Как говорится "у ней особенная стать"
Группа Бурбаки в 20 веке решила ввести свою аксиоматику у которой есть как сторонники, так и противники. Но имхо, она идет в разрез с этимологией слова "натуральные" ну и самим способом их появления идущим ещё со времен до н.э. А так да, удобно в теории множеств считать число 0 натуральным. Как по мне французы заоверрайдили этот термин по-своему, но пора прекращать холиварный оффтоп)
StjarnornasFred
03.06.2025 13:34По определению, натуральные числа - это целые положительные числа. То есть это числа, которые строго больше нуля.
haqreu
03.06.2025 13:34Ха, определения очень сильно зависят от школы, в которой вы учились. Знаете ли вы, что для французов «nombre positif» означает «большее либо равное нулю»?
vk6677
03.06.2025 13:34На счёт 2-х чисел. Видимо настолько частая была ошибка с переполнением, что в стандарт ввели std::midpoint.
sci_nov
03.06.2025 13:34Эта функция несколько отличается от той, если бы мы усредняли, используя более широкие регистры.
vk6677
03.06.2025 13:34Согласен. Классическая формула a + (b - a) /2. Оформленная в виде шаблона.
Tuxman
03.06.2025 13:34a + (b - a) /2
тоже переполняется, еслиb > a
.
Если вам по классике, тогда вот такauto avg = (a & b) + ((a ^ b) >> 1);
vk6677
03.06.2025 13:34В реализации GCC есть эта проверка на условие. Видимо что-бы работало с числами с плавающей запятой. Приведённое Вами решение только для целых чисел.
И скорее переполнение будет если b < a.
wataru
03.06.2025 13:34Нет, не переполнится (в беззнаковых числах, как в статье). Ответ влезает, потому что это среднее. Разность влезает, потому что худший вариант - это MAX_UINT - 0 = MAX_UINT.
Со знаковыми числами, да - может переполниться.
WASD1
03.06.2025 13:34<pedant mode>
Я понимаю "горячий" заголовок, но дистрибутивность - это закон согласования ДВУХ бинарных операций.
</pedenat mode>StarPilgrim Автор
03.06.2025 13:34Их две: сложение (это 1) и деление (это два). Правильно посчитал до двух ?
wataru
03.06.2025 13:34Тоже первая мысль была считать отдельно частные и остатки.
Умный алгоритм работает так быстро из-за пайплайна в процессоре. Да, одно деление выполняется в 10 раз медленнее одного умножения. Но если у вас куча делений подряд, то они выполняются лишь немного медленнее кучи сложений, потому что куча микроопераций выполняется параллельно и самое медленное - чтение из памяти.
kovserg
А кто мешает использовать для суммы большую разрядность?
Daemonis
Условие задачи?
middle
Тогда это задача ради задачи.
CBET_TbMbI
Возможно, это приобретает практический смысл, когда нужно посчитать среднее из фиглиардов чисел.
Kahelman
Для этого рекомендую читать классиков. Дональд Кнут: Искусство программирования для ЭВМ. Том 2 . Получисленные алгоритмы .
Как всегда Гугл засрали спамеры но ЧатГПТ все помнит:
Ты, вероятно, имеешь в виду алгоритм Кнута для скользящего (инкрементального) среднего, также известный как online mean или running mean.
Он позволяет не хранить все значения, а пересчитывать среднее на каждом шаге при поступлении нового элемента.
Вот алгоритм:
Пусть:
• n — количество уже обработанных элементов (сначала n = 0)
• \mu_n — текущее среднее после n элементов
• x_{n+1} — новый поступающий элемент
Обновление среднего:
\mu_{n+1} = \mu_n + \frac{x_{n+1} - \mu_n}{n+1}
n = 0
mu = 0.0
for x in stream_of_values:
n += 1
mu += (x - mu) / n
print("Mean =", mu)
kukovik
Тут очевидно, что быстрее не будет. Ибо на каждый чих то самое деление, которое и у автора статьи. Плюс надо как-то решать проблему с потерями от округления.
wataru
Вот что это за мода пошла лениться и просто перепечатывать выхлоп из нейросетей? Во-первых, они галлюционируют. Их вывод надо проверять и осозновать. Если вы его проверили и переварили, то уже можно своими словами одно предложнение скинуть.
Во-вторых, если кому-то хочется вывод чатажпт почитать, они у него сами спросят.
Далее, проблема автора - не онлайн или ограничения по памяти, а переполнение целочисленной переменной. Обратите внимание в перепечатоном вами бездумно ответе нейросетки ни слова о переполнении нет.
Вам тут очень повезло, и в этом алгоритме действительно нет переполнения.
dyadyaSerezha
Сдаётся мне, что чтение этих фиглиардов с диска или инета будет занимать на порядки больше времени, чем само вычисление.
Tuxman
Меня такое на интервью спросили кстати.
wataru
Нет, если у вас в задаче уже куча uint64_t, например. Или процессор 32-битный (микроконтроллеры какие-нибудь). У вас просто тупо нет большей разрядности.
Serge78rus
В данном случае мешает условие
В реальной жизни надо провести замеры времени исполнения и сравнить с полученными автором для его алгоритма. Естественно, сама задача актуальна для архитектуры, не имеющей аппаратной реализации операций с 64-битными числами.
middle
... и не имеющей аппаратной реализации сложения с переносом?
Serge78rus
Там еще придется поделить число двойной длинны, правда только один раз.
kovserg
А какая разница есть апаратная реализация или нет. Использовать большую разрядность никто не запрещает. Даже если компилятор умеет auto, но вдруг почему-то не умеет uint64_t, то разве это может остановить?
Ведь c++ универсальный язык и не запрещает реализовывать всё что хочется:
ext::div
wataru
Это называется длинная арифметика. И у автора фактически ровно это и реализовано. Только весьма частный случай: в системе основания с базой size и с оптимизацией, что мы знаем, что нам надо будет выдать обычное целочисленное значение цифр, кроме младшей и оно помещается в uint32_t - так что вместо старших цифр можно сразу хранить их значение в десятичной системе в одной переменной.