Все мы привыкли округлять числа в десятичной системе. В двоичной системе округление устроено похоже, но всё же способно запутать. Больше всего сложностей вызывают дроби. Например, далеко не сразу очевидно, почему дробь 0.11101 при округлении до 2 знаков после запятой превращается в целое 1. В этой статье разбираются общие правила округления двоичных дробей и объясняется, откуда они берутся. Те же правила применимы и к округлению двоичных целых чисел.

Стандарт IEEE-754 определяет пять режимов округления, и большинство из них довольно прямолинейны. Первые два округляют к ближайшему значению (ничья — к чётному и ничья — от нуля); остальные называются направленными округлениями: к нулю, к плюс бесконечности и к минус бесконечности. Эти правила проще всего понять на примере десятичной системы:

Направленные округления совсем простые. В этой статье мы подробно разберём правило «к ближайшему; ничья — к чётному». Это режим по умолчанию для двоичной плавающей точки и рекомендуемый режим по умолчанию для десятичной. И понять его обычно не так легко, как направленные округления.

Общее правило округления двоичных дробей до n-го знака предписывает посмотреть на цифру, следующую за n-м знаком. Если это 0, число всегда округляется вниз. Если же цифра равна 1 и хотя бы одна из последующих цифр тоже 1, число округляется вверх. Если же все последующие цифры — 0, то нужно применить правило разрешения ничьей, и обычно это «ничья — к чётному». Оно гласит, что округлять следует к числу, у которого на n-м знаке стоит 0.

Чтобы увидеть эти правила в действии, округлим несколько чисел до 2 знаков после двоичной запятой:

• 0.11001 — округляется вниз до 0.11, потому что цифра на 3-м знаке — 0
• 0.11101 — округляется вверх до 1.00, потому что цифра на 3-м знаке — 1 и дальше есть цифры 1 (5-й знак)
• 0.11100 — применяем правило разрешения ничьей «к чётному» и округляем вверх, потому что цифра на 3-м знаке — 1, а все последующие цифры — 0.

Если вы похожи на меня, то с первого взгляда не очень понятно, откуда эти правила берутся. Похоже, ни в одной прочитанной мной статье об округлении эти правила не объясняются достаточно подробно и с наглядными иллюстрациями — а именно этого, на мой взгляд, и не хватает для ясного объяснения.

Варианты округления

Когда мы округляем число, приходится выбирать один из двух возможных вариантов: округлить вниз до ближайшего числа, которое меньше исходного, либо округлить вверх до ближайшего большего. У этих двух чисел не должно быть больше знаков после запятой, чем у результата округления.

Чтобы показать, как их найти, округлим десятичное число 0.42385 до 2 знаков. К каким числам его можно округлить? Это легко увидеть, если поместить его на числовую прямую вместе с дробями, имеющими два знака:

Диаграмма показывает, что исходное число попадает между 0.42 и 0.43. Так как 0.42385 = 0.42 + 0.00385, а меньшее число — 0.42, можно заключить, что для поиска меньшего числа достаточно отбросить дробную часть после второго знака. А чтобы найти большее число, можно взять уже найденное меньшее и увеличить его на один ULP, прибавив 1 к цифре последнего знака. Или, если посмотреть иначе, к меньшему числу нужно прибавить 0.01 — это 1, умноженная на 10 в степени минус 2, потому что мы округляем до 2 знаков. Если бы мы округляли до 3 знаков, то взяли бы меньшее число для 3 знаков и прибавили 1, умноженную на 10 в степени минус 3.

Обобщим это правило поиска вариантов округления:

Округляя дробное число до n знаков, сначала найдите меньшее число, отбросив дробную часть после n-го знака, а затем с его помощью найдите большее число, прибавив к нему один ULP — 1, умноженную на основание системы счисления в степени n.

Теперь найдём варианты округления для двоичного числа 0.11011. Снова округляем до 2 знаков. Следуя той же схеме, что и для десятичных дробей, получаем 0.11 в качестве меньшего числа, поскольку 0.11011 = 0.11 + 0.00011. Затем находим большее число, прибавив 0.01 — это 1, умноженная на 2 в степени минус 2, потому что система двоичная, то есть основание равно 2, а округляем мы до 2 знаков. Результат этого вычисления — 0.11+0.01=1.00.

Поиск наименьшего расстояния

Правило округления «к ближайшему» говорит, что округлять нужно к тому числу, разница с которым минимальна. На числовой прямой это означает, что минимально расстояние между исходным числом и одним из двух возможных результатов округления. Поэтому, если поместить исходное число и оба варианта на числовую прямую и обозначить расстояния через x, нужно определить, какой x меньше:

Сделать это вычитанием совсем несложно:

$$x_1 = |0.11 - 0.110110| = 0.000110$$ $$x_2 = |1.00 - 0.110110| = 0.001010$$

Здесь ясно видно, что x1 меньше x2, значит округлять нужно до 0.11. Но что, если бы мы захотели округлить бесконечную двоичную дробь? В этом случае вычитание перестало бы быть такой простой операцией. Как оказывается, есть куда более лёгкий подход.

Сравнение с серединой

Другой, более простой подход — определить, больше исходное число или меньше середины между двумя вариантами округления. Посмотрим на диаграмму:

Нетрудно заключить, что если число больше середины, то оно ближе к большему результату округления, иначе — ближе к меньшему.

Как же найти эту середину между двумя вариантами? Мы знаем, что расстояние между 0.11 и 1.00 равно 0.01. Значит, достаточно найти половину от 0.01 и прибавить её к меньшему числу. Половина — это 0.001, и в сумме с меньшим числом она даёт 0.111 = 0.11 + 0.001. По сути, это равносильно тому, чтобы просто дописать 1 в конец меньшего числа. Вот диаграмма с нужными числами на числовой прямой:

Теперь остаётся лишь сравнить исходное число с серединой:

$$0.11011 > 0.111 \quad or \quad 0.11011 < 0.111$$

Побитовое лексикографическое сравнение показывает, что 0.11011 меньше середины. Значит, округляем вниз до 0.11 — тот же результат, что мы получили, вычисляя расстояния.

Ничья — к чётному

Иногда расстояния от исходного числа до обоих вариантов округления равны, поэтому правило «к ближайшему» применить нельзя. Допустим, мы округляем число 0.11011 до 4 знаков после двоичной запятой. Мы знаем, что нужно найти два варианта округления и середину для сравнения. Чтобы найти меньшее число, просто отбрасываем оставшиеся цифры после 4-го знака, и получаем 0.1101. Теперь находим середину, дописав 1 в конец меньшего числа, — получаем 0.11011. И наконец, находим большее число, прибавив 1 ULP к меньшему: 0.1101+0.0001 = 0.1110.

Итак, у нас есть:

• исходное число — 0.11011
• число для округления вниз — 0.1101
• число для округления вверх — 0.1110
• середина между вариантами округления — 0.11011.

Побитовое сравнение показывает, что исходное число и середина равны, то есть исходное число попадает ровно посередине между двумя вариантами округления. Это как раз тот случай, когда нужно применить вторую часть правила — «ничья к чётному». Двоичное число чётно, если оканчивается на 0, и при наших вариантах округления чётным оказывается большее число, так что правило предписывает округлить вверх, до 0.1110.

Выводим общие правила округления

А нужно ли вообще сравнивать цифры на всех знаках? Как вы могли догадаться из правил, изложенных в начале статьи, — не нужно. В предыдущем разделе я показал, что середина всегда оканчивается на 1 на n+1-м знаке, где n — количество знаков, до которого округляется число. Исходное число и середина всегда совпадают вплоть до n+1-го знака — значит, именно с этого знака и следует начинать сравнение.

Итак, общие правила округления, приведённые в начале статьи, вытекают из сравнения исходного числа с серединой между двумя вариантами округления. Повторю эти правила ещё раз:

Общее правило округления до n-го знака предписывает посмотреть на цифру, следующую за n-м знаком. Если это 0, число всегда округляется вниз. Если же цифра равна 1 и хотя бы одна из последующих цифр тоже 1, число округляется вверх. Если же все последующие цифры — 0, то нужно применить правило разрешения ничьей, и обычно это «ничья — к чётному». Оно гласит, что округлять следует к числу, у которого на n-м знаке стоит 0.