Счёт: от зарубок до битов

Пастуху с тридцатью овцами хватает палки и ножа. Утром овца выходит из загона — на палке появляется зарубка. Вечером стадо возвращается, и пастух ведёт пальцем по зарубкам: одна овца, одна зарубка. Зарубки и овцы кончились одновременно — все дома; остались лишние зарубки — кого-то пора искать. Считать при этом не нужно вовсе, достаточно сопоставлять.

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

Витрина у входа

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

Цифра и число — разные вещи, как буква и слово. Цифр в нашей системе десять, от 0 до 9, а чисел бесконечно много: 7 — однозначное число, записанное одной цифрой, 365 — трёхзначное, записанное тремя. Дальше мы увидим системы, где цифр две, двадцать и шестьдесят.

Зал первый: зарубки

Самый старый экспонат — обломок малой берцовой кости павиана с 29 насечками. Его нашли в пещере Бордер-Кейв в горах Лебомбо, на границе ЮАР и Эсватини; радиоуглеродные датировки дают ему около 43 тысяч лет. Лунный месяц длится примерно 29,5 суток, поэтому кость любят называть древнейшим календарём. Это догадка: кость сломана, так что неизвестно, сколько насечек на ней было сначала, и неизвестно, что ими отмечали.

Кость из Ишанго на востоке нынешней Демократической Республики Конго моложе: ей около 20 тысяч лет. Насечки на ней собраны в три столбца. В одном — группы из 11, 13, 17 и 19 зарубок, все простые числа между 10 и 20. В другом — 11, 21, 19 и 9, то есть $10 + 1$, $20 + 1$, $20 - 1$ и $10 - 1$. Соблазнительно увидеть здесь теорию чисел каменного века, и некоторые исследователи её видят. Другие считают, что насечки просто не давали рукоятке скользить в ладони. Спор не решён, и честнее всего относиться к обеим костям как к загадкам.

Бесспорно другое. Зарубка — самая простая система счисления: одна черта на один предмет. Правило у неё ровно одно, поэтому ею пользуются до сих пор. Когда при подсчёте голосов вы ставите палочки и перечёркиваете каждую пятую, вы работаете в первом зале нашего музея.

Недостаток зарубок виден сразу: длина записи равна самому числу. Тысяча — это тысяча черт. Их долго наносить, легко ошибиться на одну, а отличить на глаз 1000 зарубок от 1001 невозможно. Первое, что приходит в голову, — завести особый знак для целой пачки. Так и поступили египтяне.

Зал второй: Египет

В египетской иероглифической записи у каждой степени десяти свой знак. Единица — вертикальная черта, десять — путы для скота, похожие на подкову, сто — свёрнутая верёвка, тысяча — цветок лотоса, десять тысяч — поднятый палец, сто тысяч — головастик, миллион — бог бесконечности Хех с воздетыми руками. Число пишут, повторяя знаки столько раз, сколько нужно: 365 — это три верёвки, шесть пут и пять черт.

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

На церемониальной булаве фараона Нармера, вырезанной около 3100 года до н. э., записан отчёт о победе: 120 000 пленных, 400 000 быков и 1 422 000 коз. Цифры, скорее всего, преувеличены, зато запись коротка: коз — один Хех, четыре головастика, два пальца и два лотоса, всего девять знаков. Для круглых чисел египетская запись очень экономна. Миллион у египтян — один знак, у нас — семь цифр.

Теперь запишите по-египетски 999 999. Девять головастиков, девять пальцев, девять лотосов, девять верёвок, девять пут и девять черт: 54 знака. Длина записи равна сумме цифр числа, и в худшем случае на каждую степень десяти уходит по девять значков. Считать столбиком тоже не выйдет. Сложить два таких числа — значит ссыпать знаки в одну кучу и обменивать каждые десять одинаковых на один следующий. Это работает, но медленно.

Зал третий: Вавилон

В Месопотамии писали заострённой палочкой по сырой глине, и рисовать лотосы там было неудобно. Вавилонские писцы обходились двумя оттисками: вертикальным клином (единица) и угловым (десяток). Из них, как египтяне из черт и пут, складывали числа от 1 до 59: 23 — это два угловых клина и три вертикальных.

Дальше начинается то, чего у египтян не было. Число 60 вавилонянин писал тем же знаком, что и 1, — одним вертикальным клином, только левее. Значение знака зависит от места: крайняя правая группа — единицы, следующая — шестидесятки, дальше $60 \cdot 60 = 3600$ и так далее. Это первая известная нам позиционная система, около четырёх тысяч лет назад она уже была в ходу. Основание у неё — 60. Число 365 на вавилонской табличке — шесть клиньев, промежуток и ещё пять клиньев: $6 \cdot 60 + 5$. Посмотрите на витрину у входа: оно показано там именно так.

За позиционность вавилоняне заплатили неоднозначностью. Нуля у них долго не было: если разряд пуст, писец оставлял промежуток, а промежуток на глине легко не заметить. Позже появился особый знак-заполнитель, но ставили его, как правило, только между цифрами, а в конце числа — нет. Поэтому один клин мог означать и 1, и 60, и 3600, и даже $\frac{1}{60}$: знака, отделяющего целую часть от дробной, тоже не было. Что имел в виду автор, читатель угадывал по смыслу задачи.

Почему шестьдесят, точно никто не знает. Зато понятно, чем это основание удобно: у числа 60 двенадцать делителей — 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 и 60. Половина, треть, четверть, пятая и шестая часть шестидесяти — целые числа, и доли в такой системе записываются легко. Шестидесятеричный счёт пережил Вавилон на тысячелетия: через греческих астрономов он дошёл до нас в виде 60 минут в часе, 60 секунд в минуте и 360 градусов в окружности.

Часы на вашем экране — живая вавилонская табличка. Запись 2:05:30 означает два часа, пять минут и тридцать секунд, то есть $2 \cdot 3600 + 5 \cdot 60 + 30 = 7530$ секунд. Три разряда, основание 60 и даже ноль в пустом месте, которого так не хватало вавилонянам.

Сколько секунд длится промежуток 1:01:01?

Три разряда по основанию 60: $1 \cdot 3600 + 1 \cdot 60 + 1 = 3661$.

Зал четвёртый: Рим

Римские цифры знакомы всем по циферблатам и номерам веков: I — 1, V — 5, X — 10, L — 50, C — 100, D — 500, M — 1000. Это снова аддитивная система, но с хитростью: меньший знак перед большим вычитается. IV — это $5 - 1$, IX — $10 - 1$, XC — $100 - 10$. Так запись становится короче: 1999 — это MCMXCIX, семь знаков вместо двадцати восьми египетских. Самое большое число, которое записывается по обычным правилам, — MMMCMXCIX, то есть 3999.

Сами римляне правило вычитания соблюдали не строго. Ворота Колизея пронумерованы с IIII вместо IV, так что ворота 44 подписаны XLIIII. Привычка дожила до наших дней: на многих часах с римским циферблатом четыре часа обозначены IIII, хотя девять — IX.

Попробуйте сложить столбиком XLVIII и LXXIV. Ничего не выйдет: знаки не стоят друг под другом по разрядам, а одна и та же буква в одном месте прибавляется, в другом вычитается. Римляне и не пытались так считать. Считали они на абаке — доске с линиями, по которым передвигали камешки. Камешек по-латыни — calculus; отсюда наши «калькуляция» и «калькулятор». Каждая линия абака отвечает за свой разряд: единицы, десятки, сотни. Набралось десять камешков на одной линии — их убирают и кладут один на следующую.

Получается, что позиционная система у римлян была, только не на письме, а на доске. Считали камешками, цифрами записывали готовый ответ: $48 + 74 = 122$, CXXII. Чтобы перенести доску на бумагу, не хватало одного — знака для пустой линии. Пока его нет, «три сотни, пусто, пять» и «тридцать пять» на письме неразличимы.

Первая редакция «Книги абака» Леонардо Пизанского, о которой пойдёт речь через два зала, датирована 1202 годом. Запишите это число римскими цифрами.

$1202 = 1000 + 100 + 100 + 1 + 1$, то есть M, C, C, I, I — MCCII.

Зал пятый: майя

По другую сторону океана, без всякой связи с Вавилоном и Индией, к позиционной записи пришли майя. Считали они двадцатками, видимо по числу пальцев на руках и ногах. Цифры от 0 до 19 складывались из точек и черт: точка — единица, черта — пятёрка, так что 13 — это две черты и три точки над ними. Разряды писали столбиком снизу вверх: внизу единицы, над ними двадцатки, выше — четырёхсотки.

Главный экспонат этого зала — ракушка. Так майя обозначали пустой разряд, и знак этот встречается в их надписях не позже IV века нашей эры. Знак для пустого места появлялся в разных концах света: у поздних вавилонян, в Индии, у майя, — и майя точно пришли к нему сами. Причина каждый раз одна: в позиционной записи пустой разряд должен быть виден.

В календаре у майя была поправка: третий разряд равнялся не $20 \cdot 20 = 400$, а $18 \cdot 20 = 360$, почти длине года. Поэтому в датах так называемого длинного счёта разряды — это 1, 20, 360, 7200 и 144 000 дней. Двадцатеричные следы остались и в Европе: по-французски 80 — quatre-vingts, «четыре двадцатки».

Зал шестой: Индия и ноль

Запись, которой мы пользуемся сегодня, сложилась в Индии в первом тысячелетии нашей эры: основание 10, девять цифр для значений от 1 до 9 и отдельный знак для пустого разряда. В храме в Гвалиоре есть надпись 876 года: в ней указаны размеры сада, 270 на 187 хаст (хаста — локоть), и сказано, что сад даёт храму 50 гирлянд в день. Ноль в числах 270 и 50 высечен кружком. Это древнейший ноль, высеченный в камне в самой Индии. Но в Камбодже есть плита почти на двести лет старше, 683 года, и в дате 605 на ней ноль изображён точкой. Плита пропала в годы красных кхмеров, и в 2013 году её заново отыскал в хранилище древностей математик Амир Акзель.

Индийские цифры переняли учёные арабского мира. Около 825 года Мухаммад ибн Муса аль-Хорезми написал книгу об индийском счёте. Арабский оригинал не сохранился, зато дошёл латинский перевод, начинавшийся словами «Dixit Algorizmi» — «Сказал аль-Хорезми». Из искажённого имени автора получилось слово «алгоритм».

В Европу новые цифры принёс Леонардо Пизанский, которого позже прозвали Фибоначчи. «Книгу абака» (1202) он начинает с главного:

Девять индийских знаков суть 9 8 7 6 5 4 3 2 1. С этими девятью знаками и со знаком 0, который арабы называют зефиром, записывается любое число.

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

Что же такого в этой записи? Возьмём 2026. Двойка слева означает две тысячи, ноль — отсутствие сотен, следующая двойка — два десятка, шестёрка — шесть единиц:

$$2026 = 2 \cdot 1000 + 0 \cdot 100 + 2 \cdot 10 + 6 = 2 \cdot 10^3 + 0 \cdot 10^2 + 2 \cdot 10^1 + 6.$$

Каждая цифра умножается на степень десяти, и какая это степень, решает только место цифры. Ноль держит место пустого разряда: без него 2026 превратилось бы в 226. А сама десятка ничем не выделена — на её месте может стоять любое целое число, большее единицы.

Цифры числа, от старшей $a_n$ до младшей $a_0$. Каждая — целое число от $0$ до $b - 1$, и старшая не равна нулю, иначе её можно просто стереть. Основание — целое число, не меньшее двух. Черта сверху и индекс внизу говорят: это запись по основанию $b$, а не произведение цифр. Вес разряда: единица, $b$, $b^2$ и так далее. Разряды нумеруют справа налево начиная с нуля, и вес нулевого разряда $b^0 = 1$. Пример: $\overline{365}_{10} = 3 \cdot 10^2 + 6 \cdot 10 + 5 = 365$, а $\overline{365}_{8} = 3 \cdot 64 + 6 \cdot 8 + 5 = 245$. Цифры те же, основания разные — и числа разные.

Почему цифр должно быть ровно $b$? Если разрешить цифру, равную основанию или большую, у одного числа появятся несколько записей. Заведите в десятичной системе отдельную цифру для двенадцати — и 22 можно будет записать двумя способами: «2 2» (два десятка и две единицы) и «1 12» (десяток и двенадцать единиц). Если цифр меньше $b$, некоторые числа не запишутся вовсе. Ровно $b$ цифр от $0$ до $b - 1$ дают каждому натуральному числу ровно одну запись. Это теорема, и мы докажем её в следующем зале.

Позиционная запись дала то, ради чего всё затевалось, — счёт столбиком. Когда вы складываете 58 и 67, в разряде единиц получается 15: пять пишем, один переносим в десятки. Это ровно то, что делал римлянин на абаке, когда менял десять камешков на один. В любом основании $b$ правило то же: $b$ единиц одного разряда — одна единица следующего.

Обратите внимание: «10» в системе с основанием $b$ всегда означает само число $b$ — одна единица второго разряда и ноль единиц первого. Будь у людей по четыре пальца на руке, мы писали бы «10», имея в виду восемь, и считали бы такую систему единственно естественной.

А теперь о длине. Трёх десятичных цифр хватает на все числа до 999, шести — до 999 999. Каждая новая цифра увеличивает запас чисел в десять раз, а новая зарубка — всего на одно число. То же верно в любом основании.

Для десятичной системы это знакомые $999 = 10^3 - 1$ и $999\,999 = 10^6 - 1$. Миллион зарубок и семь цифр — вот и вся разница между первым залом и шестым.

Мастерская: любое основание

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

Из системы с основанием $b$ — в десятичную

Этот путь прокладывает сама формула: умножаем каждую цифру на вес её разряда и складываем. Например, $\overline{1011}_2 = 1 \cdot 8 + 0 \cdot 4 + 1 \cdot 2 + 1 = 11$. Для длинных чисел удобнее идти слева направо: берём старшую цифру, умножаем на основание, прибавляем следующую цифру, снова умножаем — и так до конца. Для $\overline{1011}_2$: $1$, потом $1 \cdot 2 + 0 = 2$, потом $2 \cdot 2 + 1 = 5$, потом $5 \cdot 2 + 1 = 11$. Этот приём называют схемой Горнера, и он ещё встретится нам в главе о многочленах.

Из десятичной — в систему с основанием $b$

Обратный путь — деление с остатком. Разделим 37 на 2: получится 18 и остаток 1. Этот остаток и есть последняя цифра двоичной записи. Почему? Потому что $37 = 2 \cdot 18 + 1$, а все разряды, кроме младшего, вместе дают число, кратное двум; остаток может взяться только из младшего разряда. Оставшиеся цифры — двоичная запись числа 18. Делим дальше, пока частное не станет нулём, и читаем остатки снизу вверх:

$$37 \xrightarrow{:2} 18 \;(1) \xrightarrow{:2} 9 \;(0) \xrightarrow{:2} 4 \;(1) \xrightarrow{:2} 2 \;(0) \xrightarrow{:2} 1 \;(0) \xrightarrow{:2} 0 \;(1), \qquad 37 = \overline{100101}_2.$$

Проверим: $32 + 4 + 1 = 37$. Первый остаток даёт последнюю цифру, последний остаток — первую. Если прочитать остатки сверху вниз, получится $\overline{101001}_2 = 41$ — на этом спотыкаются чаще всего.

Почему лесенка никогда не подводит

Лесенка выглядит как фокус: делим, делим, переписываем остатки задом наперёд — и получаем запись. Докажем, что она не подводит никогда, а заодно и обещанное в прошлом зале: у каждого натурального числа в каждой системе запись ровно одна. Всё держится на делении с остатком.

Идея: разрезать числовую прямую на отрезки длины $b$ и посмотреть, в какой из них попало $n$.

Отметим на прямой числа, кратные $b$: $0$, $b$, $2b$, $3b$ и так далее. Они растут без конца и режут прямую вправо от нуля на отрезки длины $b$, которые идут подряд, без пропусков и наложений. Договоримся, что левый конец относится к отрезку, а правый — уже к следующему. Точка $n$ попадает ровно в один такой отрезок: от $qb$ включительно до $(q+1)b$, не включая его. Ровно в один — потому что отрезки не перекрываются и не оставляют дыр. Номер этого отрезка $q$ и есть неполное частное: от нуля до $qb$ укладывается ровно $q$ шагов длины $b$. Остаток $r = n - qb$ — расстояние от начала отрезка до точки $n$. Оно не меньше нуля, потому что $n \ge qb$, и меньше длины отрезка, потому что $n < (q+1)b$. Значит, $0 \le r \le b - 1$ и $n = bq + r$. Другой пары не бывает. Если $n = bq' + r'$ и $0 \le r' \le b - 1$, то $n$ лежит в отрезке от $q'b$ до $(q'+1)b$, а такой отрезок один. Значит, $q' = q$, и тогда $r' = n - bq = r$.

Идея: связывать камешки в пачки по $b$, пачки — в связки по $b$ пачек и так далее. Каждый раз несвязанными остаётся меньше $b$ штук — это и есть очередная цифра.

Выложим $n$ камешков и будем связывать их в пачки по $b$ штук. Свяжем столько пачек, сколько получится. Несвязанных камешков останется от $0$ до $b - 1$: будь их $b$ или больше, из них вышла бы ещё одна пачка. По лемме о делении с остатком пачек ровно $q_0$, а несвязанных камешков ровно $a_0$, где $n = b q_0 + a_0$. Это последняя цифра. Теперь так же поступим с пачками: свяжем их в связки по $b$ пачек, в каждой связке $b \cdot b = b^2$ камешков. Несвязанных пачек снова от $0$ до $b - 1$ — это цифра $a_1$, и $q_0 = b q_1 + a_1$. Продолжаем, пока на очередном уровне штук не окажется меньше $b$: тогда связывать дальше нечего, и число штук на этом уровне — старшая цифра. Она не ноль: на новый уровень мы переходим, только если на предыдущем было не меньше $b$ штук, а из них получилась хотя бы одна связка. (Если с самого начала $n < b$, связывать нечего вовсе, и запись состоит из одной цифры $n$.) На каждом уровне штук хотя бы в $b$ раз меньше, чем на предыдущем, так что остановка наступит за конечное число шагов. Сложив камешки по уровням, получаем $n = \dots + a_2 b^2 + a_1 b + a_0$: запись существует. Запись одна. Возьмём любую запись $n$ цифрами от $0$ до $b - 1$. Все её разряды, кроме последнего, — целые пачки, то есть в сумме число, кратное $b$, а последняя цифра меньше $b$. Значит, $n = b \cdot (\text{число пачек}) + a_0$ с $0 \le a_0 \le b - 1$, и по лемме $a_0$ обязано быть остатком от деления $n$ на $b$, а число, записанное остальными цифрами, — неполным частным $q_0$. К $q_0$ применяем то же рассуждение, и так цифра за цифрой: каждая определена однозначно.

Идея: подставить каждую строку лесенки в предыдущую — и позиционная запись появится сама.

Строки лесенки — это равенства $n = b q_0 + r_0$, $q_0 = b q_1 + r_1$, $q_1 = b q_2 + r_2$, …, $q_{k-1} = b \cdot 0 + r_k$, и в каждом по лемме остаток от $0$ до $b - 1$. Лесенка конечна: пока число не ноль, его неполное частное от деления на $b \ge 2$ строго меньше самого числа, а бесконечно убывать натуральные числа не могут. Подставим второе равенство в первое и раскроем скобки: $n = b(b q_1 + r_1) + r_0 = q_1 b^2 + r_1 b + r_0$. Подставим третье: $n = q_2 b^3 + r_2 b^2 + r_1 b + r_0$. Дойдя до последней строки, где частное равно нулю, получим $n = r_k b^k + \dots + r_1 b + r_0$. Это запись $n$ в системе с основанием $b$: все $r_i$ от $0$ до $b - 1$, а старшая цифра $r_k = q_{k-1}$ не ноль, ведь на ноль мы бы уже остановились. По теореме запись единственна, значит, лесенка выдаёт именно её. Первый остаток стоит при $b^0$ — это последняя цифра, последний остаток стоит при $b^k$ — первая. Отсюда правило «читать снизу вверх».

Какое число в восьмеричной системе идёт сразу после $\overline{17}_8$?

$\overline{20}_8$ $\overline{18}_8$ $\overline{110}_8$ $\overline{1A}_8$

В восьмеричной системе цифры от 0 до 7, цифры 8 в ней нет. После семи единиц разряд переполняется, как у нас после девяти: $\overline{17}_8 + 1 = \overline{20}_8$. В десятичной записи это $15 + 1 = 16$.

Запишите число 100 в восьмеричной системе.

$100 = 8 \cdot 12 + 4$, $12 = 8 \cdot 1 + 4$, $1 = 8 \cdot 0 + 1$. Остатки снизу вверх: $\overline{144}_8$. Проверка: $1 \cdot 64 + 4 \cdot 8 + 4 = 100$.

Последний зал: два знака

Самая короткая позиционная система — двоичная: основание 2, цифры 0 и 1. Готфрид Вильгельм Лейбниц подробно разобрал её в рукописи 1679 года и опубликовал в 1703-м статью «Объяснение двоичной арифметики». Незадолго до этого иезуит Иоахим Буве прислал ему из Китая 64 гексаграммы «Книги перемен» — фигуры из шести сплошных и прерванных черт, — и Лейбниц увидел в них двоичные числа от 0 до 63. Сама идея была известна и до него: Томас Хэрриот пробовал двоичную запись в начале XVII века, но в рукописях, которые долго никто не читал.

Людям двоичная запись неудобна: 2026 в ней выглядит как 11111101010, одиннадцать цифр. Зато для машины она идеальна. Цифру 0 или 1 может хранить всё, у чего есть два состояния: ток есть или нет, участок намагничен в одну сторону или в другую, на диске ямка или гладкое место. Два состояния легко различить даже сквозь помехи, а десять уровней напряжения путались бы куда чаще.

В восьми битах помещается $2^8 = 256$ разных значений: от $\overline{00000000}_2 = 0$ до $\overline{11111111}_2 = 255$. Длинные цепочки нулей и единиц читать тяжело, поэтому программисты разбивают их на четвёрки и каждую четвёрку пишут одной шестнадцатеричной цифрой: это 0–9 и буквы A–F для значений от 10 до 15. Байт — ровно две такие цифры. Цвет #FF8800 на веб-странице — три байта: красный канал $\overline{FF}_{16} = 255$ включён на полную, зелёный $\overline{88}_{16} = 136$ — наполовину, синего нет. Получается оранжевый.

Старая шутка: почему программисты путают Хеллоуин (31 октября, по-английски Oct 31) и Рождество (25 декабря, Dec 25)?

Потому что $\overline{31}_8 = 25$ Потому что $\overline{31}_{16} = 25$ Потому что $\overline{31}_2 = 25$

Oct — сокращение не только от October, но и от octal, «восьмеричный»; Dec — от decimal, «десятичный». Проверим: $\overline{31}_8 = 3 \cdot 8 + 1 = 25$. В шестнадцатеричной системе $\overline{31}_{16} = 49$, а записи $\overline{31}_2$ не бывает: в двоичной системе нет цифры 3.

У двоичной записи есть трюк, который любят показывать фокусники: задуманное число от 1 до 63 отгадывается по шести ответам «да» или «нет». Проверьте на себе.

Шесть карточек — шесть разрядов. На карточке, которая начинается с восьмёрки, собраны все числа, у которых в разряде восьмёрок стоит единица. Говоря «есть», вы сообщаете значение этого бита. Шесть бит задают число от 0 до 63 однозначно, как шесть черт гексаграммы у Лейбница. Ноль на карточки не попал: у него все шесть бит нулевые.

Какое самое большое число можно записать десятью битами?

Десять единиц: $\overline{1111111111}_2$. Прибавим единицу — все разряды переполнятся, и получится $\overline{10000000000}_2 = 2^{10} = 1024$. Значит, десять единиц — это $1024 - 1 = 1023$. Так же в десятичной системе самое большое трёхзначное число $10^3 - 1 = 999$.

Снова в египетском зале

Вернёмся к папирусу Ринда с новыми глазами. Умножали египтяне удвоением. Чтобы умножить 13 на 21, писец составлял два столбца: слева удваивал единицу, справа — число 21, и останавливался, когда левое число перерастало 13.

Потом он отмечал чертой строки, в которых левые числа дают в сумме 13: $13 = 8 + 4 + 1$. Сумма отмеченных правых чисел и есть ответ: $168 + 84 + 21 = 273$. Весь расчёт — удвоения и одно сложение, таблицу умножения помнить не нужно.

Почему способ работает для любых чисел и при чём здесь двоичная система?

Идея: произведение — площадь прямоугольника, а удвоения писца — площади полос, на которые этот прямоугольник можно разрезать.

Произведение $a \cdot b$ — площадь прямоугольника со сторонами $a$ и $b$: он складывается из $a \cdot b$ единичных квадратиков. Режем ширину $a$ на куски длиной в степени двойки, каждый раз беря самый большой кусок, который помещается в оставшуюся ширину, — так же, как писец выбирает строки снизу вверх. Кусок длиной $1$ помещается всегда, пока ширина не кончилась, поэтому разрезана будет вся ширина. Каждая степень берётся не больше одного раза: если бы после куска $2^k$ осталось не меньше $2^k$, то до него было бы не меньше $2^{k+1}$, и мы взяли бы кусок $2^{k+1}$. Значит, $a$ — сумма различных степеней двойки. Это и есть его двоичная запись, а по теореме о единственности записи другой нет. Каждый кусок — полоса шириной $2^k$ и высотой $b$, её площадь $2^k \cdot b$. Именно это число стоит в правом столбце писца: удвоить $b$ ровно $k$ раз — значит умножить его на $2 \cdot 2 \cdot \ldots \cdot 2 = 2^k$. Разрезание не меняет площади, поэтому $a \cdot b$ равно сумме площадей полос, то есть сумме отмеченных правых чисел. Для $13 \cdot 21$: $13 = 8 + 4 + 1 = \overline{1101}_2$ и $13 \cdot 21 = 168 + 84 + 21 = 273$. Отмеченные строки — единицы двоичной записи, пропущенные — нули.

Египетский писец записывал множитель в двоичной системе за три тысячи лет до Лейбница, сам того не подозревая.

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

Куда дальше

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

Теперь попробуйте вычислить $3 - 5$. Столбиком не выходит: из трёх единиц пять не вычесть, а занять не у кого. Пастух обещал соседу пять овец, а у него всего три. Сколько овец у него теперь? Среди натуральных чисел ответа нет. Нужны ноль как полноправное число и числа меньше нуля — и больше тысячи лет математики спорили, имеют ли такие числа право на существование. Этот спор — в главе 2.