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

На циферблате часов написано IX, в начале главы книги — XIV, а в памяти компьютера — 1001. Всё это числа, просто записанные на разных «языках». И запись 101 не всегда означает «сто один»: в десятичной системе это сто один, а в двоичной — 5. Чтобы узнать значение числа, нужно знать, в какой системе счисления оно записано. На этом уроке разберём, как устроены системы счисления, как переводить числа из любой системы в десятичную и из десятичной в двоичную и как решать задачи «сосчитай нули и единицы», которые часто встречаются в заданиях ГЭЦ.

Непозиционные системы: римские цифры

Самая простая непозиционная система — счёт палочками: ||||| = 5. Самая известная — римские цифры: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. В числе XX оба X означают 10: цифра не становится в 10 раз больше, если стоит левее. Правила такие: цифры обычно пишут от больших к меньшим и складывают; меньшая цифра перед большей вычитается (только в парах IV, IX, XL, XC, CD, CM); одна и та же цифра подряд пишется не больше трёх раз, а V, L и D вообще не повторяются.

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

В позиционной системе у каждой цифры два свойства: её собственное значение и разряд, в котором она стоит. Количество цифр системы — её основание (b). В системе с основанием b используются цифры 0, 1, …, b − 1, а веса разрядов растут справа налево: 1, b, b², b³, … Основание пишут маленьким нижним индексом: 352₆, 1101₂. В задачах системы часто называют по основанию: «2-ичная», «8-ричная», «16-ричная». В любой системе само основание записывается как 10: 10₂ = 2, 10₆ = 6. Цифры могут обозначаться и буквами: в наборе {0, 1, 2, k, m} 5 цифр, значит, это 5-ричная система (k = 3, m = 4); такие задачи подробно разобраны на уроке «Системы счисления: задачи с неизвестным основанием».

Из развёрнутой записи следуют два полезных вывода. У наибольшего k-значного числа все цифры равны b − 1: прибавив 1, получим единицу и k нулей, то есть bᵏ. Наименьшее k-значное число — единица и k − 1 нулей, то есть bᵏ⁻¹.

Из десятичной в двоичную и обратно

В двоичной системе всего две цифры — 0 и 1, а веса разрядов — степени двойки. Именно в ней работает компьютер: один разряд — это один бит. Если знать наизусть таблицу ниже, любые задачи на системы счисления решаются быстрее.

1. 1
   Раздели

   Раздели число на 2, запиши неполное частное и остаток (0 или 1).

2. 2
   Повтори

   Снова дели частное на 2, пока частное не станет равным 0.

3. 3
   Прочитай снизу вверх

   Выпиши остатки от последнего к первому: первый остаток — младший разряд.

4. 4
   Проверь

   Сложи веса разрядов, где стоят единицы, — должно получиться исходное число.

Дробные числа

Разряды после запятой имеют веса b⁻¹, b⁻², b⁻³, …; в двоичной системе это ½ = 0,5, ¼ = 0,25, ⅛ = 0,125, 1/16 = 0,0625. Чтобы перевести десятичную дробь в двоичную, дробную часть последовательно умножают на 2: целая часть каждого произведения (0 или 1) — очередная цифра, а дробную часть снова умножают. На этот раз цифры читают сверху вниз. Целая часть переводится отдельно, делением.

Сколько цифр, нулей и единиц в двоичной записи

В заданиях ГЭЦ часто спрашивают: сколько цифр в двоичной записи числа, сколько в ней единиц и нулей? Переводить число целиком не нужно — достаточно записать его как сумму различных степеней двойки. Каждая степень даёт одну единицу, старшая степень определяет длину записи, а во всех остальных разрядах стоят нули.

То же самое умеет считать программа: число делится на 2, и на каждом шаге проверяется остаток. В письменном задании экзамена число вводится с клавиатуры, и первая строка программы — n = int(input()); здесь, чтобы программа работала в браузере, взято n = 300. Более сложные случаи (квадраты, 2ⁿ − 2ᵐ) разобраны на уроке «Системы счисления: задачи с неизвестным основанием».

n = 300
ones = 0
zeros = 0
while n > 0:
    if n % 2 == 1:
        ones = ones + 1
    else:
        zeros = zeros + 1
    n = n // 2
print(ones, zeros)

4 5

Дальше: на уроке «Восьмеричная и шестнадцатеричная системы счисления» научимся коротко записывать двоичные числа, а на уроке «Арифметические действия в различных системах счисления» — считать в этих системах столбиком.