Арифметика в позиционных системах счисления

Калькулятор в телефоне складывает 7 и 8 и спокойно пишет 15. Процессор при этом работает с цепочками из нулей и единиц, где нет ни цифры 2, ни цифры 7, — только 0 и 1. Выходит, «пятнадцать» для компьютера выглядит как 1111. Арифметика в позиционных системах счисления — умение складывать, вычитать и проверять числа в любой такой системе: двоичной, восьмеричной, шестнадцатеричной. Без неё не прочитать ни один дамп памяти, ни один адрес в отладчике, а задачи на переводы и сложение стоят в ОГЭ и ЕГЭ по информатике каждый год. Сейчас разберём правила столбика, которые одинаково работают при любом основании, посмотрим, как числа укладываются в байты памяти, и научимся проверять себя переводом в десятичную систему — эта привычка ловит почти любую арифметическую ошибку.

Сложение в столбик: любое основание

Позиционная система задаётся основанием q — числом разных цифр в ней. В двоичной две цифры, в восьмеричной восемь, в шестнадцатеричной — десять привычных и шесть буквенных: A — это десять, B — одиннадцать и так до F, то есть пятнадцати. Сложение в столбик везде устроено одинаково: складываем разряды справа налево, и если сумма достигла основания, пишем остаток, а единицу переносим в старший разряд. В десятичной системе «десять» превращается в 1 и 0; в двоичной уже 1 + 1 даёт 10, потому что два — это основание. В восьмеричной перенос случается на семи: 6 + 5 = 13 восьмеричное, ведь одиннадцать — это восемь плюс три. В шестнадцатеричной граница ещё дальше: 9 + 8 = 11 шестнадцатеричное, а «F + 1 = 10» читается как «пятнадцать плюс один — шестнадцать». Правило одно, момент переноса в каждой системе свой: переполнение разряда наступает, когда сумма доросла до q.

Вычитание зеркально: если в разряде не хватает, занимаем у старшего, но заём стоит не десять, а основание системы. В двоичной заём превращает ноль в двойку, а не в «десять» — на этом спотыкается половина класса. Проведём 1101 − 0110. Младший разряд: 1 − 0 = 1. Второй: 0 − 1 не выходит, занимаем — получаем 2 − 1 = 1. Третий: единица уже уехала в заём, приходится занимать снова — и снова 2 − 1 = 1. Старший после заёма обнуляется. Ответ 0111, то есть семь. Проверка в десятичной: 13 − 6 = 7, всё сходится. Заметить каскадный заём — когда у старшего разряда и занимать нечего — важнее скорости: именно на двойном заёме теряют баллы на экзаменах.

Восьмеричная, шестнадцатеричная и память

Восьмеричная и шестнадцатеричная системы живут рядом с памятью компьютера не случайно. Байт — восемь бит — делится на две тетрады по четыре бита, а тетрада — это ровно одна шестнадцатеричная цифра: 0000 — нуль, 1001 — девять, 1111 — F. Поэтому любой байт записывается двумя hex-цифрами, и содержимое памяти выглядит компактно: FF — это 255, все восемь бит в единицах. С восьмеричной так же дружат триады — группы по три бита: три бита дают числа от 0 до 7, ровно цифры восьмеричной системы. В старые времена восьмеричную любили за короткую запись двоичных команд без букв; сейчас почти повсюду hex: он и в цветах веб-страниц, где #FF0000 означает красный, и в адресах памяти, и в MAC-адресах сетевых карт. Перевод между системами с «родственными» основаниями мгновенен: двоичное число просто режут на группы справа налево, а каждую группу заменяют одной цифрой.

Обратный перевод — из десятичной системы — делают делением с остатками: число делят на основание, записывают остаток, а частное делят снова, пока не получится нуль. Остатки, выписанные снизу вверх, и есть новая запись. Переведём 43 в двоичную: 43 делим на 2 — частное 21, остаток 1; 21 — частное 10, остаток 1; 10 — частное 5, остаток 0; 5 — частное 2, остаток 1; 2 — частное 1, остаток 0; 1 — частное 0, остаток 1. Читаем остатки снизу вверх: 101011. Проверка разложением: 32 + 8 + 2 + 1 = 43. В столбик при таком переводе удобно подписывать колонку остатков сбоку — потом просто переписать её в обратном порядке. Смешивать направления нельзя: разложение по степеням идёт «в десятичную», деление с остатками — «из десятичной».

Арифметика в hex — та же, только стол длиннее: после 9 идёт A, значит «9 + 1 = A», а «F + 1 = 10». Сложим 3A7 и 1B5: младшие 7 + 5 = 12 — это C; средние A + B = 10 + 11 = 21, а это 16 + 5, пишем 5 и переносим 1; старшие 3 + 1 плюс перенос — ровно 5. Ответ 55C. Проверим в десятичной: 3A7 = 3 · 256 + 10 · 16 + 7 = 935, 1B5 = 437, сумма 1372; и правда 55C = 5 · 256 + 5 · 16 + 12 = 1372. Такая арифметика нужна чаще, чем кажется: адреса и смещения в программах складывают в hex постоянно, и любая ошибка в букве-цифре сдвигает адрес на целый блок памяти.

Теперь представление чисел в памяти. Минимальная ячейка — байт: восемь бит, в которых помещаются 2 в восьмой степени, то есть 256 разных значений. Беззнаковый байт хранит числа от 0 до 255: например, 200 выглядит как 11001000 — это 128 + 64 + 8. Два соседних байта дают уже 65 536 значений, четыре байта — больше четырёх миллиардов. Восьмеричная и hex-записи — это не отдельные «машины счёта», а удобные маски поверх тех же бит: в памяти всегда лежат нули и единицы, а 11001000 мы лишь читаем как 310₈ или C8₁₆. Как в тот же байт попадает минус и почему у знаковых чисел диапазон несимметричен — тема отдельного урока про дополнительный код; для арифметики пока достаточно помнить: столбик в любой системе считает одинаково, меняется только основание.

Основание q#

число разных цифр системы: у двоичной 2, у восьмеричной 8, у hex 16

Разряд#

позиция цифры в записи; вес разряда — соответствующая степень основания

Перенос#

единица, уходящая в старший разряд, когда сумма доросла до основания

Заём#

единица, взятая у старшего разряда, когда в вычитании не хватает

Тетрада#

четыре бита — ровно одна шестнадцатеричная цифра

Триада#

три бита — ровно одна восьмеричная цифра

Подсказка: клавиши J — следующая тема, K — предыдущая, на телефоне: свайп влево/вправо — соседняя тема