Системы счисления

bin, oct, hex

Для трёх систем в Python есть готовые функции. Они выдают запись числа строкой, и в начале строки стоит приставка, которая показывает систему:

n = 2026
print(bin(n))    # двоичная
print(oct(n))    # восьмеричная
print(hex(n))    # шестнадцатеричная

Приставки 0b, 0o, 0x нам почти никогда не нужны. Отрезаем их срезом из прошлой темы:

n = 2026
b = bin(n)[2:]
print(b)
print('Единиц:', b.count('1'))
print('Цифр:', len(b))

Запомни связку bin(n)[2:]. Она нужна в №5 почти в каждой задаче.

int: из любой системы в десятичную

int умеет не только превращать строку в число. Если вторым аргументом указать основание, он прочитает запись в этой системе:

print(int('11111101010', 2))
print(int('7EA', 16))
print(int('2210001', 3))
print(int('Z', 36))      # основание до 36: цифры 0–9 и буквы A–Z

Это работает для любого основания от 2 до 36, большими или маленькими буквами, неважно. Обратно в произвольную систему готовой функции нет, её напишем сами в следующем разделе.

Свой перевод в любую систему

Помнишь из темы 3, как разбирать число на цифры через % 10 и // 10? Для любой системы всё то же самое, только вместо 10 основание k. Остаток это очередная цифра, только идут они с конца, поэтому приписываем каждую слева.

n = 2026
k = 7
digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
s = ''
while n > 0:
    s = digits[n % k] + s    # очередную цифру ставим СЛЕВА
    n //= k
print(s)

Зачем строка digits? Для систем больше 10 остаток может быть, например, 12, а цифра должна быть буквой C. digits[12] как раз и есть 'C'.

Проверим себя обратным переводом:

print(int('5623', 7))

Получили 2026, значит, перевод верный. Это хорошая привычка: перевёл в систему, переведи обратно через int.

Пример как в №14

Сколько цифр 2 в троичной записи числа 9¹⁰⁰ + 3⁵⁰ − 2?

n = 9 ** 100 + 3 ** 50 - 2
s = ''
while n > 0:
    s = str(n % 3) + s     # для k ≤ 10 хватит str
    n //= 3
print(s.count('2'))

Python считает такие огромные числа точно, поэтому на ЕГЭ это решается за минуту.

Неизвестная цифра x

Второй тип задач №14: в записи числа одна цифра неизвестна и обозначена x. Нужно найти x, при котором выполнено условие. Решение: перебираем все возможные цифры, подставляем в строку и читаем её через int.

Пример. В записи 1x2₉ + x13₉ цифра x одна и та же. При каком x сумма делится на 11?

digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for x in range(9):                     # в девятеричной цифры от 0 до 8
    c = digits[x]
    a = int('1' + c + '2', 9)          # склеили запись и прочитали
    b = int(c + '13', 9)
    if (a + b) % 11 == 0:
        print(x, a + b)

Ответ x = 2. Цифра x меньше основания, поэтому range(9), а не range(10).

IP-адреса и маски

IP-адрес это четыре числа от 0 до 255 через точку, например 192.168.1.10. Каждое число это 8 двоичных разрядов, всего 32. Маска выглядит так же, 255.255.255.224, и в двоичной записи это сначала единицы, потом нули. Единицы маски отмечают часть адреса, общую для всей сети.

Считать это руками долго, а в Python есть модуль ipaddress:

from ipaddress import ip_network

net = ip_network('192.168.1.0/255.255.255.224')
print(net.num_addresses)      # сколько адресов в сети
print(net.network_address)    # адрес сети
print(net.netmask)            # маска

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

from ipaddress import ip_network

net = ip_network('10.8.0.0/255.255.248.0')
k = 0
for ip in net:
    if bin(int(ip)).count('1') <= 4:   # не больше 4 единиц в записи адреса
        k += 1
print(k)

Если дан адрес узла и маска, а сеть нужно найти, пишут strict=False:

from ipaddress import ip_network

net = ip_network('172.16.170.33/255.255.248.0', strict=False)
print(net.network_address)

strict=False разрешает дать адрес узла, а не сети. Без этого Python выдаст ошибку, что у адреса установлены биты справа от маски.

Сломай код

ValueError: такой цифры нет

print(int('19', 8))

invalid literal for int() with base 8: в восьмеричной системе нет цифры 9. Если такое случилось при переборе x, проверь границу range.

Тихая ошибка: забыли отрезать 0b

n = 5
print(len(bin(n)))       # хотели узнать число разрядов
print(bin(n).count('0'))

Вышло 5 разрядов и 2 нуля, а у числа 5 в двоичной записи 101 три разряда и один ноль. Лишние символы дала приставка 0b. Нужно bin(n)[2:].

Тихая ошибка: цифры в обратном порядке

n = 6
s = ''
while n > 0:
    s = s + str(n % 2)    # приписали справа
    n //= 2
print(s)

Вышло 011, а 6 в двоичной это 110. Остатки идут с последней цифры, поэтому их приписывают слева: s = str(n % 2) + s.

Тихая ошибка: hex и большие буквы

print(hex(255)[2:].count('F'))

Вышло 0, хотя в записи ff две F. hex пишет буквы маленькими. Нужно .count('f') или .upper().count('F').

Где пригодится на ЕГЭ

Задача про адреса из раздела 5, «сколько адресов сети с условием на двоичную запись», это типичный вопрос про маски. Попробуй сам: