Биты дробного числа: знак, порядок и дробь

Если ты разложишь 64 бита числа -2.5 на три поля, объяснишь, почему после 2⁵³ дробные числа идут через одно целое, и скажешь, чем поле порядка 0 отличается от поля 2047, - листай до «Теперь сам».

Как думаешь, сколько дробных чисел между 1 и 2

Между единицей и двойкой бесконечно много вещественных чисел. В 64 битах можно записать только конечное их количество.

Прежде чем читать дальше, попробуй угадать: дробных чисел двойной точности больше между 1 и 2 или между 1024 и 1025? А между 1 и 2 или между 2 и 4? Ответы: между 1 и 2 их в 1024 раза больше, чем между 1024 и 1025, и ровно столько же, сколько между 2 и 4. Чем дальше от нуля, тем реже стоят числа.

На что это похоже

Запись числа в физике: 6,02 · 10²³. Она состоит из трёх частей: знак, несколько значащих цифр - и порядок, который говорит, куда поставить запятую. Число значащих цифр фиксировано, поэтому точность относительная: и масса атома, и масса галактики записаны с тремя цифрами, хотя абсолютная погрешность у них различается в немыслимое число раз.

Дробное число в компьютере - та же запись в двоичной системе. Значащих битов 53, порядок - степень двойки. А первая значащая цифра в двоичной записи всегда единица - кроме нуля, других цифр нет, - и её можно не хранить.

Механизм: три поля и два особых значения порядка

бит 63      биты 62-52             биты 51-0
знак        порядок, 11 битов      дробь, 52 бита
  s         e (от 0 до 2047)       f (от 0 до 2⁵² − 1)

значение  =  (−1)ˢ · (1 + f / 2⁵²) · 2^(e − 1023)          при e от 1 до 2046

Поле порядка хранит не саму степень, а степень плюс 1023 - смещение. Так поле всегда неотрицательно: степень −4 записана как 1019, степень 0 - как 1023, степень 19 - как 1042. Смещение вместо знака выбрано не случайно: у большего по модулю числа поле порядка больше, а при равных порядках больше поле дроби. Значит, 63 бита после знака, прочитанные как одно целое, идут в том же порядке, что и сами числа, и положительные дробные числа можно сравнивать и сортировать как целые.

Число 1023 - середина диапазона поля: степени получаются от −1022 до 1023, поровну в обе стороны. Часть 1 + f / 2⁵² лежит от 1 включительно до 2. В двоичной записи это 1,ffff…: неявная единица и 52 бита после запятой. Соседние числа различаются единицей в младшем бите дроби, и её вес при степени p - 2^(p − 52).

Два значения поля порядка отданы особым случаям.

e = 0,     f = 0        ноль (со знаком: +0 и −0)
e = 0,     f ≠ 0        малое число без неявной единицы:  f / 2⁵² · 2^(−1022)
e = 2047,  f = 0        бесконечность, + или −
e = 2047,  f ≠ 0        «не число»: результат действий вроде «бесконечность минус бесконечность»

Малые числа заполняют промежуток между нулём и наименьшим обычным числом 2⁻¹⁰²²; степень у них та же, −1022, а не −1023, чтобы между ними и обычными числами не было разрыва. Без них разность двух очень близких малых чисел округлялась бы до нуля, и из a ≠ b не следовало бы a − b ≠ 0.

Правило

Двойная точность: знак - 1 бит, порядок - 11 битов со смещением 1023, дробь - 52 бита. При поле порядка от 1 до 2046 значение равно (−1)ˢ · (1 + f / 2⁵²) · 2^(e − 1023). Поле 0 - ноль и малые числа f · 2⁻¹⁰⁷⁴, поле 2047 - бесконечность и «не число». Значащих битов 53; соседние числа со степенью p отстоят на 2^(p − 52). Все целые до 2⁵³ представимы точно.

Разбор: поля четырёх чисел

Битовую запись дробного числа в 64 битах тренажёр одним целым не удержит - она больше 2⁵³. Поэтому число задаётся двумя 32-битными словами: старшим hi и младшим lo. Так же его видит 32-битный процессор и JavaScript. В настоящем Python слова получают так: struct.unpack(">II", struct.pack(">d", x)).

def razobrat(hi, lo):
    znak = hi >> 31
    poryadok = hi >> 20 & 0x7FF
    drob = (hi & 0xFFFFF) << 32 | lo
    return [znak, poryadok, drob]

def znachenie(hi, lo):
    polya = razobrat(hi, lo)
    drob = polya[2] / 4503599627370496
    if polya[1] == 0:
        x = drob * 2.0 ** -1022
    else:
        x = (1 + drob) * 2.0 ** (polya[1] - 1023)
    if polya[0] == 1:
        x = -x
    return x

print(razobrat(0x3FF00000, 0), znachenie(0x3FF00000, 0))
print(razobrat(0xC0040000, 0), znachenie(0xC0040000, 0))
print(razobrat(0x412E8480, 0), znachenie(0x412E8480, 0))
print(razobrat(0x3FB99999, 0x9999999A), znachenie(0x3FB99999, 0x9999999A))

[0, 1023, 0] 1.0
[1, 1024, 1125899906842624] -2.5
[0, 1042, 4086334964629504] 1000000.0
[0, 1019, 2702159776422298] 0.1

В старшем слове лежат знак, все 11 битов порядка и 20 старших битов дроби; младшее слово - остальные 32 бита дроби. Число 4503599627370496 в программе - это 2⁵². Поле 2047 функция znachenie не разбирает: бесконечность и «не число» обычной формулой не вычислить.

Единица: поле порядка 1023, то есть степень ноль, дробь ноль - 1,0 · 2⁰. Число −2,5: знак 1, степень 1024 − 1023 = 1, дробь - четверть от 2⁵²: 1,25 · 2 = 2,5. Миллион: степень 1042 − 1023 = 19 - это ⌊log₂ 1 000 000⌋, та же девятнадцать, что давал bit_length() - 1 в главе про длину числа. Поле порядка - готовый целый логарифм.

Последняя строка - одна десятая. Степень −4, а дробь в шестнадцатеричной записи - 999999999999A: повторяющиеся четвёрки битов 1001. Одна десятая в двоичной системе - бесконечная периодическая дробь, как треть в десятичной; 52 бита обрывают её и последний округляют вверх - отсюда A на конце вместо 9. Хранится не 0,1, а ближайшее к нему число из тех, что можно записать.

Разбор: край точности и особые значения

print(znachenie(0x43400000, 0), znachenie(0x43400000, 1), znachenie(0x43400000, 2))
print(znachenie(0, 1), znachenie(0x00100000, 0))

9007199254740992.0 9007199254740994.0 9007199254740996.0
5e-324 2.2250738585072014e-308

Первая строка - число 2⁵³ и два следующих за ним дробных числа. Степень 53, дробь меняется на единицу в последнем бите - и число прыгает на два. Нечётных целых здесь нет: на 53 значащих бита приходится 54 двоичных разряда числа, и младший всегда ноль. 2⁵³ + 1 записать нельзя - оно округлится до соседа, а при равном расстоянии до двух соседей - до того, у которого последний бит дроби нулевой, то есть до 2⁵³. Это и есть причина предела точного счёта: числа в JavaScript, на которых работает тренажёр, - те самые 64 бита, и целые в них точны, пока помещаются в 53 значащих бита.

Вторая строка - самое маленькое положительное число, 2⁻¹⁰⁷⁴: поле порядка ноль, в дроби одна младшая единица. И рядом - наименьшее обычное, 2⁻¹⁰²². Между ними почти 2⁵² малых чисел с шагом 2⁻¹⁰⁷⁴.

Теперь ответ на вопрос из начала. Между 1 и 2 степень одна и та же, меняется только дробь: 2⁵² значений, считая саму единицу. Между 2 и 4 - следующая степень и снова 2⁵² значений, на вдвое более длинном отрезке. Между 1024 и 1025 - степень 10, шаг 2⁻⁴², и на отрезке длиной один помещается 2⁴² чисел: в 1024 раза меньше.

Граница упорядоченности: сравнивать как целые можно только числа одного знака. У отрицательных чисел упорядоченность обратная - знак хранится отдельным битом, а не дополнительным кодом, - а «не число» не равно ничему, включая себя.

Что ломается без этого

Первое: 0.1 + 0.2 == 0.3. Ложно: слева и справа стоят разные ближайшие числа, они отличаются в последнем бите дроби. Дробные числа сравнивают с допуском.

Второе: большое целое в дробной переменной. Идентификатор записи 9 007 199 254 740 993, прошедший через JSON и JavaScript, превращается в …992. Поэтому 64-битные идентификаторы передают строками.

Третье: «не число» в сортировке и в поиске. Сравнения на равенство и порядок с ним ложны, включая x == x. Сортировка массива с таким элементом оставляет его в непредсказуемом месте, а поиск по равенству его не находит.

Четвёртое: минус ноль. −0.0 == 0.0 истинно, но биты разные, и там, где деление дробных на ноль разрешено - в C и JavaScript, - 1 / −0.0 даёт минус бесконечность. Хеш от битов и сравнение на равенство расходятся.

Зачем это в работе

Доставать поля приходится в трёх случаях. Первый - степень как логарифм: быстрая оценка log₂ x. В Python без разбора битов это math.frexp(x) - степень у неё на единицу больше, потому что значащую часть она возвращает по модулю от 0,5 до 1, - а всю запись показывает x.hex(): (0.1).hex() - это 0x1.999999999999ap-4: неявная единица, тринадцать шестнадцатеричных цифр дроби и степень двойки после p.

Второй - двоичные форматы: числа в файлах, сетевых протоколах и базах данных лежат этими 64 битами, и порядок байтов из прошлой главы касается их так же, как целых.

Третий - сортировка и сравнение через целые. Поразрядная сортировка дробных чисел работает с их битами как с целыми, заранее поправив знаковый бит и перевернув отрицательные; базы данных кодируют дробные ключи так, чтобы байтовое сравнение совпадало с числовым.

И рассуждения о погрешности из раздела про числа получают опору: машинный эпсилон 2⁻⁵² - это вес младшего бита дроби при степени ноль.

Теперь сам

1. Запиши поля числа 6,0: знак, поле порядка, дробь как долю.
2. Какое число задано полями: знак 0, поле порядка 1021, дробь - половина от 2⁵²?
3. С каким шагом идут дробные числа около миллиона?
4. Число 2⁵³ + 3 присвоили дробной переменной. Что в ней окажется?
5. Поле порядка 2047, hi = 0x7FF00000, lo = 1. Что это?