Системы счисления: позиционные системы и переводы

В редакторе кода цвет часто задают строкой #1A73E8 — это не заклинание, а число в шестнадцатеричной системе. Программисты живут в нескольких системах сразу: цвета и адреса памяти — в шестнадцатеричной, права доступа в Linux — в восьмеричной, а процессор понимает только двоичную. Без быстрых переводов между ними в 10 классе никуда: они спрятаны в половине задач ЕГЭ по информатике.

Позиционность и развёрнутая форма

Система счисления называется позиционной, если вес цифры зависит от её места: в числе 305 тройка означает триста, а в 350 — тридцать, хотя цифра одна и та же. Основание q — сколько цифр в алфавите системы: у десятичной их десять (0-9), у двоичной две (0 и 1), у шестнадцатеричной шестнадцать (0-9 и латинские A-F). Значение числа раскрывает развёрнутая форма: каждую цифру умножают на основание в степени её позиции. Так двоичное 1011 — это 8 + 0 + 2 + 1 = 11.

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

Мост 2-8-16: триады и тетрады

Мост между 2, 8 и 16 — группировка бит. Восемь — это 2 в кубе, поэтому двоичную запись режут на триады по 3 бита справа: 110110 превращается в 110 110, то есть 66 в восьмеричной. Шестнадцать — 2 в четвёртой: режут на тетрады по 4 бита и каждую заменяют одной hex-цифрой: 110110 — это 0011 0110, то есть 36 в шестнадцатеричной. В обратную сторону работает так же: каждую восьмеричную цифру разворачиваешь в триаду, каждую hex-цифру — в тетраду.

Сколько чисел помещается в разрядах

Разрядов в системе с основанием q хватает на q в степени n разных чисел: n позиций, на каждой q вариантов. Три двоичных разряда дают восемь чисел от 0 до 7, четыре разряда — шестнадцать от 0 до 15. Восемь бит, то есть один байт, хранят 256 значений — от 0 до 255; на это число опирается и кодирование символов, и яркость цветового канала из прошлого урока. Отсюда полезная привычка проверять ответ: если переведённое число вдруг вышло за пределы своей разрядной сетки, где-то по пути потерялся разряд — пересчитай остатки.

Степени двойки любят не зря: с их помощью процессор адресует память. Десять адресных линий дают 2 в десятой — 1024 разные ячейки, и именно поэтому память исторически меряют килобайтами по 1024 байта. Добавь одну линию — и объём адресуемой памяти удвоится. Так знание степеней двойки объясняет и размеры памяти, и записи вроде «адресного пространства 16 бит»: 2 в шестнадцатой — это 65 536 адресов.

Двоичные числа, которые стоит узнавать в лицо

Несколько двоичных записей встречаются в задачах так часто, что их полезно узнавать без перевода. Единица с нулями — это степень двойки: 100 — восемь, 10000 — шестнадцать, 1000000000 — 512. Сплошные единицы — это степень двойки минус один: 111 — семь, 1111 — пятнадцать, десять единиц подряд — 1023. Произвольное число раскладывают по степеням прямо в записи: 110000 — это 32 плюс 16, то есть 48. Такой взгляд сверху экономит минуты на контрольной: чтобы понять, что за число спрятано в записи, не нужно делить с остатками — достаточно сложить веса единичных разрядов.

Сложение столбиком в двоичной системе

• 0 + 0 = 0 — пишем ноль, переносить нечего.
• 0 + 1 = 1 — пишем единицу.
• 1 + 1 = 10 — пишем ноль, единицу несём в следующий разряд.
• 1 + 1 + 1 = 11 — пишем единицу и снова несём единицу.

Сложим так 1011 и 1101 — то есть 11 и 13. Справа налево: 1 + 1 = 10, пишем 0, несём 1; дальше 1 + 0 + 1 = 10, пишем 0, несём 1; дальше 0 + 1 + 1 = 10, пишем 0, несём 1; в последнем разряде 1 + 1 + 1 = 11 — пишем 11. Получилось 11000, и это правда 24. Перенос здесь работает как привычный «десяток в уме», только перенос происходит уже при двойке — на этом держится вся арифметика процессора.

Умножить двоичное число на два проще простого: допиши ноль справа. 101 — это пять, 1010 — десять, 10100 — двадцать. Деление на два — наоборот: срежь правый ноль, если он есть. Тот же фокус ты знаешь по десятичной системе — приписать ноль значит умножить на десять, — только здесь он работает с двойкой. Правило пригодится в проверках: перевёл число, умножил на два, дописал ноль — и сверил записи.

Цвета в hex: зачем программисту шестнадцатеричная запись

Вернёмся к строке #1A73E8 из начала урока и расшифруем её до конца. Пара 1A — это 1 · 16 + 10 = 26, пара 73 — это 7 · 16 + 3 = 115, пара E8 — это 14 · 16 + 8 = 232. Получились три числа — красный, зелёный и синий каналы цвета: #1A73E8 задаёт тот самый синий, каким обычно рисуют ссылки. Одна hex-цифра заменяет тетраду из четырёх бит, поэтому цвет удобно писать шестью знаками вместо 24 бит подряд. Теперь на вопрос «зачем программистам hex» у тебя есть ответ с числами, а не на веру.

Хорошая новость: считать hex в уме проще, чем кажется. Достаточно помнить, что каждая пара знаков — это байт, то есть число от 0 до 255: FF — максимум, 255, а 80 — половина, 128. Поэтому цвета часто читают «на глаз»: чем больше первая пара, тем краснее оттенок, чем больше третья — тем синее. #FF0000 — чистый красный, #FFFFFF — белый, потому что все три канала выкручены на максимум.

Разбор типовой задачи

Словарь урока

Основание q#

сколько цифр входит в алфавит системы

Разряд#

позиция цифры в записи числа

Развёрнутая форма#

сумма цифр, умноженных на степени основания

Триада#

группа из 3 бит — одна восьмеричная цифра

Тетрада#

группа из 4 бит — одна шестнадцатеричная цифра

Остаток от деления#

то, что не делится нацело; из остатков собирается новая запись

Как это спрашивают на контрольной

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

Все пять формулировок решаются двумя инструментами: делением с остатками и развёрнутой формой. Тетрады и триады — ускоритель, а не отдельный способ: они работают только потому, что 8 и 16 — степени двойки. Если задача требует показать решение, оставляй колонку остатков видимой: без неё проверяющий не отличит верный ход от угаданного ответа.

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