CPU·IV Машина Глава 28 из 65

Всё есть биты

Детектив кракозябр. На столе шесть писем, превратившихся в «ËÁËÏÊ-ÔÏ» и «РџСЂРёРІРµС‚». Чтобы их прочитать, придётся узнать, как машина хранит числа, дроби и буквы: двоичная запись, дополнительный код и счётчик «Gangnam Style», плавающая запятая и 0,1 + 0,2, КОИ-8, кодировки Windows и UTF-8, придуманная на бумажной салфетке.

Основы 60 минут Устройство компьютера История

CPU·IV

Машина

Опирается на: 02 · Имена и значения

Что вы унесёте из главы

читать двоичную и шестнадцатеричную запись и понимать, как в байтах лежат целые со знаком и дробные числа
объяснять, почему 0.1 + 0.2 != 0.3, что такое переполнение и проблема 2038 года
понимать кодировки и Юникод, раскладывать символ в байты UTF-8 и чинить кракозябры

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

Дело о шести письмах

Детективу принесли папку. В ней шесть писем, которые за тридцать лет пришли одному человеку от разных друзей. Каждое отправлялось по-русски, а дошло вот таким. Файл с ними лежит в песочнице, в /data/bits/letters.txt.

÷ÞÅÒÁ ÐÒÉÛ£Ì ËÁËÏÊ-ÔÏ ÓÔÒÁÎÎÙÊ ÔÅËÓÔ
РџСЂРёРІРµС‚! РљРѕРіРґР° РїСЂРёРµРґРµС€СЊ?
pRIWET, DOROGOJ DRUG
яОЮЯХАН ГЮ ОХЯЭЛН
Р вЂ“Р Т‘РЎС“ Р С•РЎвЂљР Р†Р ВµРЎвЂљР В°!
��

Кое-что видно сразу. Третье письмо почти читается: «привет, дорогой друг», только латиницей и с перевёрнутым регистром. Во втором и пятом слишком много букв «Р» и «С». Четвёртое написано русскими буквами, но слов таких нет. А шестое состоит из одних вопросительных знаков в ромбах. Каждое письмо испорчено по-своему, и у каждой порчи есть причина. Чтобы её найти, нам понадобится то, что не видно на экране: числа, которыми письма записаны.

Улика первая: буква — это число

Мы уже знаем функцию ord: она возвращает номер символа. В главе 16 мы складывали эти номера в хеш. Но номер — ещё не то, что лежит в памяти. В памяти лежат биты — двоичные цифры, нули и единицы, — и сгруппированы они по восемь. Восемь битов — это байт, у него 256 возможных значений, от 00000000 до 11111111, то есть от 0 до 255. Как записывают числа двоичными цифрами и почему это та же позиционная запись, что и десятичная, только с основанием 2, рассказывает последний зал музея счёта в «Царице наук». Посмотрим, что получается из слова.

Номера русских букв больше тысячи: «к» — 1082. В один байт такое число не помещается, и метод encode превращает три буквы в шесть байт. Эти шесть чисел от 0 до 255 и есть то, что запишется в файл и уйдёт по сети. Python показывает их как b'\xd0\xba…' — это тип bytes, последовательность байтов, а list превращает её в обычные числа.

Последняя строка — инструменты на каждый день: bin и hex переводят число в двоичную и шестнадцатеричную запись, int(строка, 2) — обратно, а в коде число можно сразу написать в нужной системе: 0b1010 — это 10, 0xFF — 255. Двоичная запись длинная, поэтому программисты почти всегда пишут байты в шестнадцатеричной системе: в ней шестнадцать цифр, от 0 до 9 и от a до f, и каждая цифра — это четыре бита. Байт — две цифры: 1101 0000 — это d0. Переводить в уме тоже несложно: d — 13, значит, $13 \cdot 16 + 0 = 208$.

Сколько байт в килобайте, зависит от того, кого спросить. Исторически программисты говорили «килобайт» про 1024 байта: $2^{10}$ близко к тысяче, и память удобно мерить степенями двойки. Но «кило» везде, кроме компьютеров, значит тысячу, и производители дисков считают десятичными тысячами. В 1998 году Международная электротехническая комиссия развела понятия: КБ (килобайт) — 1000 байт, КиБ (кибибайт) — 1024; дальше МБ и МиБ, ГБ и ГиБ. Разница растёт с каждой ступенью: диск на 1 ТБ — это $10^{12}$ байт, а система, считающая двоичными гибибайтами, покажет на нём $10^{12} / 2^{30} \approx 931$ «ГБ». Ничего не пропало: единицы разные. В этом курсе КБ — тысяча, КиБ — 1024.

Улика вторая: число в восьми клетках

В Python целые числа растут без предела: 2 ** 1000 из главы 0 печатает все свои 302 цифры. Это роскошь, которую Python оплачивает сам, склеивая большое число из многих кусков. Процессор так не умеет. Его регистры — ячейки фиксированной ширины: 8, 16, 32 или 64 бита. В восемь битов помещаются 256 разных значений, и если читать их как числа без знака, это числа от 0 до 255. А как быть с отрицательными?

Первая мысль — отдать старший бит под знак: 0 — плюс, 1 — минус, остальные семь — модуль числа. Так делали в некоторых ранних машинах, но у этого способа два изъяна. Нулей становится два, $+0$ и $-0$, и сравнивать их приходится особо. Хуже того, ломается сложение: схема, которая складывает биты, должна сначала смотреть на знаки и для разных знаков вычитать. Почти все машины сегодня используют другой способ.

Вспомним одометр старой машины из главы 11. Если от 000 отмотать назад одну единицу, получится 999. Значит, на трёхзначном одометре число 999 ведёт себя как $-1$: прибавьте к нему единицу — и получится 0. Восьмибитный регистр — такой же одометр, только двоичный: после 11111111 идёт 00000000. Договоримся считать числа со старшим битом 1 отрицательными: 11111111 — это $-1$, 11111110 — $-2$, и так до 10000000, которое равно $-128$. Это дополнительный код: отрицательное число $-x$ записывается в $n$ битах как $2^n - x$. В восьми битах помещаются числа от $-128$ до $127$.

Метод to_bytes кладёт целое в заданное число байтов, int.from_bytes читает обратно, а signed говорит, читать ли старший бит как знак. Один и тот же байт 11001000 — это 200 без знака и $-56$ со знаком: биты не знают, что они значат, это решает программа, которая их читает. Запомните эту мысль, она будет главной уликой всей главы.

Формулу $2^n - x$ выбрали ради сложения: с ней оно работает без всяких поправок на знак. Сложим 5 и $-3$ столбиком, как числа без знака: 00000101 + 11111101 = 1 00000010. Девятый бит не помещается в регистр и отбрасывается, остаётся 00000010, то есть 2. Схема сложения не знает про знаки, и ей не надо знать. Есть и короткий рецепт, как получить $-x$: переверните все биты числа $x$ и прибавьте единицу. Проверьте на пятёрке: 00000101 → 11111010 → 11111011, как в выводе ячейки. Попробуйте сами.

Регистр из лампочек. Нажимайте на биты — внизу то же самое значение прочитано по-разному: как число без знака, как число в дополнительном коде, в шестнадцатеричной записи, а для одного байта — ещё и как буква в трёх кодировках. «+1» у края показывает переполнение, «инвертировать и +1» — смену знака. Режим float32 разберём в следующем разделе.

Клип корейского певца PSY «Gangnam Style» вышел летом 2012 года и стал первым видео на YouTube, которое посмотрели миллиард раз. В начале декабря 2014 года YouTube написал в своём блоге в Google+, что никогда не думал, что видео посмотрят больше раз, чем помещается в 32-битное целое со знаком, — 2 147 483 647, — и что из-за PSY пришлось перейти на 64-битное. Новый предел — $2^{63} - 1$, около девяти квинтиллионов.

Газеты написали, что «Gangnam Style» сломал счётчик. На деле ничего не сломалось: представитель YouTube объяснил журналистам, что счётчик перевели на 64 бита за несколько месяцев до того, как клип подошёл к пределу, а пост был шуткой. Но шутка удалась, потому что опасность реальна: если 32-битный счётчик со знаком перевалит через край, за 2 147 483 647 последует $-2\,147\,483\,648$.

Самый известный будущий край — проблема 2038 года. Во многих системах время хранится как число секунд, прошедших с полуночи 1 января 1970 года по Гринвичу, и долго это число было 32-битным со знаком.

19 января 2038 года в 03:14:07 по Гринвичу такой счётчик дойдёт до предела, а через секунду станет отрицательным — и часы прыгнут в 13 декабря 1901 года. Современные системы давно перешли на 64-битное время, его хватит на сотни миллиардов лет. Но старые устройства, файлы и базы данных с 32-битными полями будут жить и в 2038 году, и их ищут уже сейчас — так же, как в конце 1990-х искали двузначные годы перед 2000-м.

Улика третья: плавающая запятая

В главе 2 выяснилось, что 0.1 + 0.2 не равно 0.3: одна десятая в двоичной системе — бесконечная дробь, и машина хранит её с обрезанным хвостом. Теперь можно посмотреть, где именно хвост обрезан. Дробное число в Python занимает 64 бита и устроено как запись в научном формате — $-2{,}5 = -1{,}25 \cdot 2^1$, только по основанию 2. Биты делятся на три поля: один бит знака, одиннадцать битов порядка (это степень двойки) и пятьдесят два бита мантиссы, то есть цифр после запятой. Первую цифру мантиссы хранить не нужно: у двоичного числа в такой записи она всегда 1. Порядок хранится со сдвигом: к истинному порядку прибавлено 1023, чтобы обойтись без знака. Такие числа называют числами с плавающей запятой: запятая «плавает», её место задаёт порядок.

Модуль struct упаковывает число в байты так, как его хранит машина: ">d" значит 64-битное дробное, старшим байтом вперёд. Потом мы разбираем 64 бита на поля сдвигами и масками: >> сдвигает биты вправо, & оставляет только те, что отмечены единицами в маске. Это побитовые операции, и в следующих главах они станут нашими руками.

У 0.1 мантисса — повторяющееся 1001, обрезанное на 52-м бите и округлённое вверх: последние биты 1010, а не 1001. Поэтому вместо одной десятой хранится дробь $\frac{3602879701896397}{36028797018963968}$, чуть большая. Метод hex показывает то же короче: мантиссу шестнадцатеричными цифрами и порядок после буквы p. И здесь видна вся разгадка главы 2: у суммы 0.1 + 0.2 мантисса кончается на 4, а у 0.3 — на 3. Они отличаются всего на единицу в последнем, пятьдесят втором бите. Этого хватает, чтобы == сказал «нет».

Из устройства следуют и другие странности. Мантисса — 52 бита, поэтому между соседними дробными числами есть промежуток, и он растёт вместе с числом: около единицы он $2^{-52} \approx 2{,}2 \cdot 10^{-16}$, а около $10^{16}$ — уже 2, и 2.0**53 + 1 неотличимо от 2.0**53. Самый большой порядок зарезервирован под особые значения: бесконечности, которые получаются при переполнении, и NaN — «не число», результат операций вроде $\infty - \infty$. NaN не равно даже самому себе. Самый маленький порядок отдан нулю и совсем крошечным числам, а то, что ещё меньше, обращается в ноль. И нулей два, $+0$ и $-0$: они равны при сравнении, но знак у них разный.

До середины 1980-х каждая фирма считала дроби по-своему: свои размеры полей, свои правила округления, своё поведение при переполнении. Одна и та же программа на разных машинах давала разные ответы, и переносить численные программы было мучением. В 1977 году в комитет Института инженеров электротехники и электроники (IEEE), который взялся за общий стандарт, пришёл Уильям Кэхэн из Калифорнийского университета в Беркли. Он к тому времени консультировал Intel, проектировавшую математический сопроцессор 8087, и вместе со своим аспирантом Джеромом Куненом и Гарольдом Стоуном предложил проект, который в итоге и победил. Стандарт IEEE 754 вышел в 1985 году. Бесконечности, NaN, два нуля, округление к ближайшему — всё это его решения, продуманные так, чтобы ошибка сразу была видна и программа не выдавала молча мусор. В 1989 году Кэхэн получил премию Тьюринга; его называют отцом плавающей запятой.

Вернитесь к регистру из лампочек и переключите его в режим float32. Это 32-битная версия того же формата: 1 бит знака, 8 битов порядка и 23 бита мантиссы. Её используют там, где точность не так важна, как скорость и память, — в графике и в нейросетях. Если вписать в поле 0.1, появится знакомый повторяющийся хвост, только короче.

Улика четвёртая: таблица на 128 строк

С числами разобрались, теперь буквы. Буква в машине — это номер в договорной таблице, такой же, как азбука Морзе из главы 8: отправитель и получатель заранее согласились, какой код что значит. Таблицу соответствия символов и чисел называют кодировкой. Самая известная — ASCII, американский стандартный код обмена информацией. Его первую версию утвердили в 1963 году, строчные буквы появились в редакции 1967-го. В ASCII 128 кодов, то есть семь битов: управляющие символы вроде перевода строки, цифры, знаки препинания и латинские буквы.

Таблицу составляли с умыслом. Цифры стоят с кода 0x30, и числовое значение цифры записано в её младших четырёх битах. Заглавная A — 1000001, строчная a — 1100001: строчная отличается от заглавной ровно одним битом, шестым справа. Оператор ^ — исключающее ИЛИ — переворачивает этот бит, и Hello превращается в hELLO. Регистр меняется одной операцией, и составители таблицы на это рассчитывали.

Восьмой бит в ASCII не нужен. Многие линии связи того времени его вообще не передавали или использовали для проверки ошибок: электронная почта долго гарантировала доставку только семи битов из восьми. Запомним это — третье письмо уже ждёт.

Улика пятая: восьмой бит

Русских букв в ASCII нет. Но у байта восемь битов, и вторая половина таблицы, коды от 128 до 255, свободна. Каждая страна заняла её своими буквами — и каждая по-своему. В СССР в 1974 году приняли стандарт КОИ-8, «код для обмена информацией, 8 бит». Его авторы расставили русские буквы во второй половине таблицы не по алфавиту: каждая стоит напротив похожей по звучанию латинской, только с переменой регистра. Строчная «п» — 0xD0, а без восьмого бита это 0x50, заглавная латинская P. Если линия теряет восьмой бит, русский текст превращается в читаемый транслит: «Привет» — pRIWET.

Два письма раскрыты. Третье прошло через линию, которая срезала восьмой бит, и для КОИ-8 это почти не беда: оператор | 0x80 возвращает бит всем буквам, и текст читается снова. Первое письмо записали в КОИ-8, а прочли таблицей Latin-1 — западноевропейской, где в верхней половине стоят буквы с диакритикой. Байт 0xCB в КОИ-8 — «к», в Latin-1 — Ë. Так и вышло «ËÁËÏÊ-ÔÏ»: это «какой-то», каждый байт которого прочитан чужой таблицей. Лечение в две строки: encode("latin-1") возвращает байты, какими они были, а decode("koi8_r") читает их как надо. Во всех кракозябрах нужно одно и то же: понять, какой таблицей прочли, и какой надо было.

Беда в том, что таблиц было много. В MS-DOS русские буквы жили в кодировке CP866, «альтернативной», в Windows — в CP1251, в Unix и в почте — в КОИ-8, у компьютеров Apple — своя. Одно и то же слово в разных таблицах — разные байты:

Четвёртое письмо раскрыто тоже: его написали в Windows, в CP1251, а прочли как КОИ-8. Обе таблицы кириллические, поэтому вместо букв — тоже буквы, только чужие, а заглавные и строчные поменялись местами. Если буквы русские, а в слова они не складываются и регистр скачет, подозревайте именно эту пару. Каждое сочетание «записали в — прочли как» оставляет свой почерк. Изучите его в лаборатории.

Лаборатория кракозябр. Слева — «испортить»: впишите текст и выберите, в какой кодировке его записали и какой прочли; внизу — таблица всех сочетаний сразу. Справа — «починить»: выберите письмо из дела и подберите пару; когда текст станет русским, письмо засчитывается. Пятое письмо придётся чинить дважды, а шестое… попробуйте.

Улика шестая: один номер на всех

Двести пятьдесят шесть мест на все языки мира не хватит, даже если таблиц много: в одном байте не уместить вместе русский и греческий, а китайских иероглифов — десятки тысяч. В конце 1980-х инженеры Xerox и Apple начали работу над общей таблицей, где у каждого символа любой письменности свой номер. Так появился Юникод; первая версия вышла в 1991 году. Номер символа в Юникоде называют кодовой точкой и пишут так: U+0416 — «Ж». Именно эти номера возвращает ord, и строка в Python — последовательность кодовых точек. Мест в таблице больше миллиона, а занято в версии 18.0, вышедшей в сентябре 2026 года, 172 808: все алфавиты, иероглифы, математические знаки, ноты, древние письменности и эмодзи.

Номера раздали, но их ещё нужно как-то записать в байты. Самый прямой путь — четыре байта на символ, UTF-32. Но английский текст при этом раздувается вчетверо, и ни одна старая программа такие файлы не прочтёт. Первые реализации брали по два байта, и до сих пор строки внутри Windows, Java и JavaScript хранятся в UTF-16, где частые символы занимают два байта, а редкие — четыре. Победил третий способ.

Кен Томпсон и Роб Пайк из Bell Labs работали над операционной системой Plan 9 и уже перевели её на Юникод, но способ записи, которым пользовались, им не нравился. Однажды под вечер Пайку позвонили — по его воспоминаниям, кажется, из IBM: участники комитета консорциума X/Open просили оценить их проект записи Юникода. Пайк перечислил, чего ждёт от такой кодировки, и проекту не хватало как минимум одного: подхватить поток байтов с середины. Томпсон и Пайк решили, что сделают лучше. Вечером они пошли ужинать в закусочную в Нью-Джерси, и там, на бумажной салфетке под тарелкой, Томпсон придумал, как раскладывать биты. Пайк вспоминал, что Кен проектировал, а он болел за него. Вернувшись в лабораторию, они рассказали о схеме в X/Open и услышали, что она лучше их собственной, — а как быстро её удастся сделать? Они пообещали, что к понедельнику — дню голосования, как помнил Пайк, — у них будет работающая система, и к пятнице Plan 9 уже работал на новой кодировке, и только на ней.

Эту историю Пайк записал в письме 2003 года. Ужин был, по его словам, кажется, в среду, а в архиве Томпсона потом нашёлся файл с первым описанием кодировки, датированный 2 сентября 1992 года, — это как раз среда. Кодировку назвали UTF-8.

UTF-8 устроена так. Символы ASCII, кодовые точки до 127, занимают один байт — тот же, что в ASCII: любой старый английский текст уже записан в UTF-8. Остальные занимают от двух до четырёх байтов, и первые биты каждого байта говорят, что это за байт:

0xxxxxxx — символ из одного байта, ASCII;
110xxxxx — начало символа из двух байтов, 1110xxxx — из трёх, 11110xxx — из четырёх;
10xxxxxx — продолжение: такие байты идут после начального.

Биты кодовой точки разливаются по местам, отмеченным x. Кириллица живёт в кодовых точках от U+0400 до U+04FF, ей хватает 11 битов, и каждая русская буква занимает два байта — вот почему «кот» стал шестью байтами.

Кодировка вышла на редкость удачной. По любому байту видно, начало это символа или середина, поэтому, попав в поток с середины, программа пропускает байты 10xxxxxx и через три байта самое большее находит начало следующего символа. Ни один многобайтовый символ не содержит внутри байтов ASCII, и поиск / или \n старыми программами ничего не ломает. Ни один код не служит началом другого — это префиксный код, как у Хаффмана, только длину символа задают не частоты, а размер номера. А сортировка строк байт за байтом даёт тот же порядок, что сортировка по кодовым точкам. По данным W3Techs, сегодня в UTF-8 записаны 99 процентов сайтов.

Символ в байтах. Впишите любой текст. Для каждой кодовой точки: её номер, двоичная запись и то, как её биты разливаются по шаблону UTF-8 — цвет показывает, какой бит куда попал. Внизу — сколько байтов занимает текст в UTF-8, UTF-16 и UTF-32 и сколько символов насчитает Python.

Строки Python сами по себе не хранят UTF-8. Внутри строка — массив кодовых точек одинаковой ширины: по байту, если все символы из Latin-1, по два, если есть кириллица, и по четыре, если попался эмодзи. Взвесьте их весами sys.getsizeof из главы 14: строка из тысячи a весит 1041 байт, из тысячи ж — 2058, из тысячи смайликов U+1F600 — 4060. А len считает кодовые точки, которые не всегда совпадают с тем, что человек называет символом.

Семья на экране — один значок, а для Python это пять кодовых точек: мужчина, женщина и девочка, склеенные невидимым соединителем U+200D. Похожая склейка объясняет загадку прошлой главы. Букву «й» Юникод разрешает записать двумя способами: одной кодовой точкой U+0439 или двумя — «и» и отдельной «краткой» U+0306, которая садится на предыдущую букву. Ударение в «сто́ит» — такой же отдельный значок U+0301. Чтобы сравнивать и искать такие строки, их приводят к одной форме — нормализуют: unicodedata.normalize("NFC", s) склеивает всё, что можно, в цельные символы, "NFD" — наоборот, раскладывает. Правило на каждый день: текст, пришедший извне, перед поиском и сравнением нормализуйте.

Развязка

Теперь у детектива есть всё. Во втором письме подозрительно много «Р» и «С», и это почерк UTF-8, прочитанной как CP1251. Русская буква в UTF-8 — два байта, и первый почти всегда 0xD0 или 0xD1, а в CP1251 это как раз «Р» и «С». Каждая русская буква превращается в пару, где первая — «Р» или «С», а вторая — что угодно. Пятое письмо — тот же почерк, только дважды: его испортили, а кто-то по дороге принял испорченный текст за нормальный и сохранил в UTF-8 ещё раз. Чинить надо в обратном порядке, слой за слоем.

Пять дел закрыты. Шестое закрыть нельзя. Его записали в CP1251, а прочли как UTF-8 — но байты CP1251 почти никогда не складываются в правильные последовательности UTF-8: 0xDD обещает начало двухбайтового символа, а следующий байт не начинается с 10. Программа, которая читала письмо, молча заменила каждый непонятный байт знаком U+FFFD — ромбом с вопросом. Сами байты при этом выброшены, и в файле остались только одинаковые ромбы: три байта ef bf bd на каждый. Информация уничтожена, и никакая перекодировка её не вернёт. Можно лишь угадать, что три ромба — это «Это», по длине слов.

Кракозябры — это байты, прочитанные не той таблицей. Пока байты целы, текст можно спасти: encode той кодировкой, какой его неправильно прочли, и decode той, какой его записали. Чтобы спасать не пришлось, указывайте кодировку явно везде, где текст превращается в байты и обратно: open(path, encoding="utf-8") в Python, <meta charset="utf-8"> в HTML, кодировку в настройках базы данных. До версии 3.15 open без encoding берёт кодировку из настроек системы, и на Windows с русскими настройками та же программа читает тот же файл как CP1251. В 3.15, выход которой намечен на октябрь 2026 года, по умолчанию будет UTF-8, но программы живут долго, и явное encoding не помешает никогда.

Эпилог: картинки и звук

Если буква — число, то и всё остальное тоже. Картинка на экране — сетка точек, пикселей, а цвет каждой — три числа от 0 до 255: сколько в ней красного, зелёного и синего. Фотография 4000 на 3000 пикселей — 36 миллионов байт, если хранить её как есть. Чёрно-белой картинке хватает одного бита на точку: восемь точек строки — один байт. Так же, по восемь в байте, хранит свои биты рабочий фильтр Блума из главы 26: бит номер $i$ лежит в байте i // 8, а сдвиг и маска достают его, не трогая соседей. Нарисуйте что-нибудь.

Экран 8 × 8: каждая строка — один байт, левая точка — старший бит. Нажимайте на клетки и смотрите, как меняются байты справа; можно и наоборот — вписать байт. Так будет устроен экран учебного компьютера, который мы начнём собирать в следующей главе.

Звук — это давление воздуха, которое меняется во времени. Микрофон превращает его в напряжение, а преобразователь много раз в секунду измеряет напряжение и записывает число. На компакт-диске таких измерений 44 100 в секунду, каждое — 16 бит, и каналов два: 176 400 байт в секунду, около десяти мебибайт на минуту музыки.

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

Задачи

Четыре задачи: два перевода, раскладка символа в байты и детектив, который раскрывает дела без вас.

Напишите to_binary(n) и to_hex(n): двоичную и шестнадцатеричную запись целого n ≥ 0 строкой, без ведущих нулей, шестнадцатеричные цифры строчными: to_binary(10) — "1010", to_hex(255) — "ff", у нуля обе записи — "0". Встроенными bin, hex, format и форматом {n:b} не пользуйтесь — тесты это проверяют. В заготовке to_binary почти готова, но в ней две ошибки.

Запустите to_binary(6) и to_binary(0). Остатки от деления на 2 — это цифры с конца: первый остаток — последняя цифра. А у нуля цикл не выполнится ни разу.

Шестнадцатеричная запись — тот же алгоритм с делением на 16. Остаток от 0 до 15 превращается в цифру по строке "0123456789abcdef": DIGITS[r]. Можно написать одну функцию to_base(n, base) и вызвать её дважды.

Это «лесенка» деления из мастерской «Царицы наук»: каждое деление с остатком отщепляет младшую цифру. Цифры выходят с конца, поэтому их надо развернуть. Обратный путь, из записи в число, — схема Горнера: value = value * base + digit, как в многочленном хеше из главы 16.

Напишите to_twos(n, bits) — запись целого n в дополнительном коде строкой ровно из bits нулей и единиц: to_twos(-5, 8) — "11111011". Если число не помещается в bits бит со знаком, то есть не лежит между $-2^{bits-1}$ и $2^{bits-1} - 1$, бросьте ValueError. И обратную функцию from_twos(s): строка из нулей и единиц, прочитанная как число в дополнительном коде, — from_twos("10000000") равно $-128$.

Вспомните определение: отрицательное $-x$ хранится как $2^{bits} - x$. Значит, к отрицательному n достаточно прибавить $2^{bits}$, и останется записать неотрицательное число в bits цифр, с ведущими нулями.

Обратно: int(s, 2) читает строку как число без знака. Если старший бит s[0] — единица, число отрицательное, и из него надо вычесть $2^{len(s)}$.

Цикл на bits шагов сам даёт ведущие нули. Функции from_twos ширина отдельно не нужна, её задаёт длина строки. Поэтому "1" и "11" обе означают $-1$: дописывание единиц слева значение не меняет. Так процессор и расширяет байт со знаком до 32 бит — копирует старший бит влево.

Напишите utf8_encode(text) — байты UTF-8 строки, как text.encode("utf-8"), но самостоятельно: по кодовой точке каждого символа решите, сколько нужно байтов, и разлейте её биты по шаблону из раздела про Юникод. Верните bytes. Метод encode и готовые кодеки не годятся — тесты это проверяют. Тесты проверяют и края диапазонов: U+007F, U+0080, U+07FF, U+0800, U+FFFF, U+10000 и последнюю кодовую точку U+10FFFF, а последний тест раскладывает 300 тысяч символов «Войны и мира» и даёт на это три секунды.

Границы: до 0x80 — один байт, до 0x800 — два (11 битов), до 0x10000 — три (16 битов), дальше — четыре (21 бит).

Последние шесть битов числа — cp & 0b111111, следующие шесть — cp >> 6 & 0b111111. Байт продолжения — 0b10000000 | шесть_битов. Начальный байт двухбайтового символа — 0b11000000 | cp >> 6.

В Python сдвиги >> выполняются раньше, чем &, а & — раньше |, поэтому скобки здесь не нужны, хотя и не помешали бы. Четыре ветки — вот и вся UTF-8. Декодер устроен зеркально: по первым битам начального байта он узнаёт длину, проверяет, что дальше идут байты 10xxxxxx, и собирает кодовую точку сдвигами влево. Как раз эту проверку провалили байты шестого письма.

Напишите fix(text), которая раскрывает дело без подсказки. На вход — русская фраза, которую записали в одной кодировке (UTF-8, CP1251 или КОИ-8), а прочли другой (CP1251, КОИ-8, Latin-1, CP1252, CP866 или UTF-8); иногда UTF-8, прочитанную как CP1251, испортили так дважды, а иногда текст не испорчен вовсе. Верните исходную фразу. Python называет эти кодировки "utf-8", "cp1251", "koi8_r", "latin-1", "cp1252", "cp866". Тесты чинят письма из главы и 300 фраз «Войны и мира», в каждой не меньше двадцати символов; на 300 фраз дано десять секунд.

Перебирайте: для каждой пары «прочли как» — «записали в» попробуйте text.encode(прочли).decode(записали). Некоторые пары бросят UnicodeError — значит, это точно не они, пропускайте. Не забудьте вариант «ничего не делать».

Из всех кандидатов выберите самый «русский». Вспомните частоты букв из главы 8: в русском тексте больше всего «о», «е», «а», «и», «н», а «ъ», «ф», «щ» редки. Начислите очки за частые буквы и штраф за символы, которых в русском тексте не бывает, и за заглавные посреди слова — ими выдаёт себя путаница CP1251 и КОИ-8.

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

Детектив работает по-сыщицки: перебирает подозреваемых и проверяет, у кого алиби не сходится. Кандидатов всего шестнадцать, и обычно больше половины из них отсекает UnicodeError. Оценка по частотам букв — самая простая модель языка; она уверенно отличает русский текст от кракозябр на фразах, но может ошибиться на одном коротком слове, где статистике не на что опереться. Программы-угадыватели кодировок, вроде той, что встроена в браузеры, смотрят ещё и на частоты пар букв. Функция candidates — генератор из главы 10: варианты выдаются по одному, и держать их списком не нужно.

Куда дальше

Дело закрыто, и все улики сошлись в одну: сами по себе биты ничего не значат, смысл им задаёт договор — таблица кодировки, формат IEEE 754, дополнительный код. Но кто-то ведь эти биты складывает, сдвигает и переворачивает: ^ менял регистр буквы, & и >> вырезали поля дробного числа. Python просит об этом процессор, процессор — схемы внутри себя, и где-то в кремнии есть устройство, которое получает два бита и выдаёт их сумму. Как кусок кремния складывает два бита? Следующая глава соберёт ответ из выключателей — и заодно первые детали учебного компьютера, на котором мы потом запустим собственные программы.