Числа №7. Нормализация

Возвращаемся к числам. Мы выяснили, что любая десятичная дробь приводится к двоичной чередой делений и умножений на два. Чаще всего вы получите периодическую дробь как в случае с 0.1. Но бывают и удачные варианты: например, число 42.515625 в двоичном представлении дает 101010.100001.

Легко заметить: проблем не создают те десятичные числа, которые являются половинками, четвертинками, восьмушками и так далее. Объяснение простое: помните таблицу умножения на 2 из прошлой заметки? Мы останавливаемся, когда получаем единицу, вычитаем из нее единицу и получаем ноль. Это значит, что очередное умножение должно вернуть 1. Если размотать алгоритм назад, на предыдущем шаге должно быть 0.5, перед ним — 0.25 и так далее.

Поэтому 25% — это ок: в двоичном виде 0.25 будет 0.01. А 10% — не ок: 0.1 будет 0.0(0011). Двоичная природа дает о себе знать.

Хорошо, мы привели десятичную дробь к двоичной, что дальше? Как ее хранить? Наивное решение — выделить группу бит под целую и дробные части отдельно. Например, если float занимает 4 байта, разделим его пополам: по два байта под каждую часть. В два байта умещаются числа от -32,768 до 32,767. Выходит, подобный float сможет хранить числа от -32,768.32768 до 32,767.32767. Не густо, если сравнить с нормальным float.

Стандарт чисел с плавающей запятой предусматривает другой принцип хранения. Первый шаг на пути к нему — нормализовать двоичную дробь. Возьмем число 42.515625, которое привели к двоичному виду:

101010.100001

Это же число я могу представить так:

101010.100001 * 2^0

Оператор “крышка” означает возведение в степень. Два в нулевой степени равно единице, поэтому такое умножение ничего не изменит.

Далее: я могу побитово сдвинуть число влево или вправо и компенсировать это степенью двойки. Например, если я передвину точку влево, это равносильно тому, что поделить число на 2. Чтобы уравновесить это деление, я умножу число на два — то есть увеличу степень на единицу. Поэтому число можно записать так:

10101.0100001 * 2^(0+1)

Оно ничуть не изменилось: это все то же число, только в другой записи.

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

1010101.00001 * 2^(0+1-2)

Выходит, что разделитель можно двигать куда угодно и компенсировать его степенью. Если у нас безграничное число битов, точность не пострадает. Разумеется, на практике это не так: биты конечны, и передвижение разделителя приводит к тому, что их часть отбрасывается.

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

С числом

101010.100001 * 2^0

нам повезло: оно начинается сразу с единицы (в отличии, скажем, от 0.00001). Потребуется пять сдвигов влево. Это равносильно тому, чтобы поделить число на 2 пять раз. Компенсация степени составит +5. Вот как выглядит нормализованное число:

1.01010100001 * 2^5

Этой процедуре подвергаются все числа после перевода из десятичной системы к двоичной.

Теперь вспомним 0.1 — оно становится 0.0(0011) в двоичной системе. Чтобы разделитель оказался за единицей, нужно четыре сдвига вправо. Это равносильно умножению, поэтому степень уменьшается. Вот что было до:

0.0(0011) * 2^0

и после:

1.1(0011) * 2^-4

Обращаю внимание: только сейчас мы рассмотрели ключевое свойство чисел с плавающей запятой — их разделитель плавает! Ни одна из прошлых заметок не раскрывала этого, но теперь вы в курсе. Как мы увидим позже, разделитель плавает и в других случаях, например при сложении чисел. Вот почему в их названии есть слово float.

После нормализации следует третий этап — битовая упаковка, который мы рассмотрим в следующей заметке.