Записи чисел, биты и текстовые шаблоны

В задачах ЕГЭ одно и то же число встречается в разных записях: 47 и двоичное 101111 — одно число. Нужно переводить запись в число и обратно, считать единицы двоичной записи и проверять, подходит ли запись под маску вроде 1?2*. Число и его запись — разные вещи: Python переводит одно в другое, работает с отдельными двоичными разрядами и проверяет запись по шаблону.

Двоичная запись устроена так же, как десятичная из урока о числах, только веса разрядов другие. Начнём с перевода числа 47.

Запись числа зависит от основания, а int(text, base) переводит запись в число. «Двоичным» или «десятичным» бывает не число, а его запись. В записи с основанием base разряды справа налево имеют веса 1, base, base ** 2 и так далее. Например, 1011 в двоичной записи — это 1 · 8 + 0 · 4 + 1 · 2 + 1 · 1 = 11:

print(int("1011", 2))print(int("101111", 2))print(int("FF", 16))print(bin(47), oct(47), hex(255))print(bin(47)[2:])

int(text, base) разбирает запись в заданном основании. bin, oct и hex строят двоичную, восьмеричную и шестнадцатеричную записи с префиксами 0b, 0o, 0x; срез [2:] убирает префикс у неотрицательного числа.

Как получается сама запись? Последний разряд — остаток n % 2, остальные разряды хранит n // 2 — так же в уроке о while снимали десятичные цифры через % 10 и // 10. Пройди перевод 47 по шагам:

Для любого основания то же: остаток n % base — новая цифра слева, дальше n // base. Подробно перевод разобран в теме 14.

format(n, "b") даёт двоичную запись без префикса, а format(n, "08b") — дополненную нулями слева до восьми знаков:

print(format(47, "b"))print(format(5, "08b"))print(format(255, "x"))

Битовые операции работают с каждым двоичным разрядом отдельно. Бит — двоичный разряд. Операция сравнивает биты, стоящие друг под другом, и соседние разряды на результат не влияют. Возьмём a = 6, то есть двоичное 110, и b = 3, то есть 011.

a = 6b = 3print(a & b, a | b, a ^ b, a << 1, a >> 1)print((47).bit_count(), (47).bit_length())

Сдвиг влево на k разрядов — умножение на 2 ** k, вправо — целочисленное деление на 2 ** k.

n.bit_count() считает единицы в двоичной записи модуля числа. n.bit_length() даёт число разрядов без ведущих нулей. У 47 = 101111 пять единиц и шесть разрядов. Скобки вокруг 47 нужны, чтобы точку не приняли за дробную часть числа.

Маска fnmatch проверяет запись целиком: ? — один символ, * — любая последовательность. В записи числа ? — ровно одна цифра, а * — сколько угодно цифр, в том числе ни одной. Функция fnmatchcase из модуля fnmatch проверяет, подходит ли строка под маску целиком:

from fnmatch import fnmatchcase print(fnmatchcase("102", "1?2*"))print(fnmatchcase("15200", "1?2*"))print(fnmatchcase("12", "1?2*"))

В первом случае * пустая; в последнем на месте ? нет символа: после 1 сразу 2, и маске не хватает символа.

Проверь маску на своих записях: схема показывает, какие цифры заняли ? и *, а если запись не подходит — говорит об этом.

Типичная задача: найти числа до 10 000, кратные 7, чья запись подходит под маску, и для каждого — частное от деления на 7. Перебираем кандидатов и проверяем запись:

from fnmatch import fnmatchcase answers = []for n in range(7, 10_000, 7):    if fnmatchcase(str(n), "1?2*"):        answers.append((n, n // 7))print(answers[:5])

Срез [:5] показывает первые пять ответов. Граница исключает 10 000, а перебор по возрастанию даёт ответы уже по порядку. ? нельзя заменить пустотой; * может означать ноль символов — этот случай легко забыть при ручном построении кандидатов.

Регулярное выражение — другой язык шаблонов, со своими правилами. Модуль re проверяет и ищет по нему текст. В нём * не значит «любой текст»: это повторение предыдущего элемента ноль или более раз. Основные записи — выбери запись, чтобы увидеть, какие строки она описывает целиком:

[0-9]

подходят "7"; не подходят "a"одна ASCII-цифра

[ABC]

подходят "B"; не подходят "D"один символ из набора

.

подходят "?"; не подходят ""любой символ, обычно кроме перевода строки

X*

подходят "", "XXX"; не подходят "XY"ноль или более повторений X

X+

подходят "XXX"; не подходят ""одно или более повторений

X?

подходят "", "X"; не подходят "XX"ноль или одно повторение

X{3}

подходят "XXX"; не подходят "XX"ровно три повторения

X{2,4}

подходят "XX", "XXXX"; не подходят "X"от двух до четырёх повторений

A|B

подходят "A"; не подходят "AB"одно из двух

(AB)+

подходят "ABAB"; не подходят "ABA"группа: повторяется целиком

Эквивалент маски 1?2* для десятичных записей — 1[0-9]2[0-9]*:

import re pattern = r"1[0-9]2[0-9]*"print(re.fullmatch(pattern, "15200") is not None)print(re.fullmatch(pattern, "12") is not None)

Шаблон пишут сырой строкой r"…": в ней обратная косая черта остаётся сама собой. fullmatch требует совпадения со всей строкой; search ищет где угодно; match — только с начала, но не обязательно до конца. Успех возвращается объектом совпадения, неуспех — None.

Объект совпадения знает найденный текст и его место. re.finditer перебирает все совпадения по очереди:

import re for m in re.finditer(r"[0-9]+", "a12b345c6"):    print(m.group(), m.start(), m.end())

group() — найденный текст, start() — индекс его начала, end() — индекс сразу после конца, как граница среза: "a12b345c6"[4:7] — это "345". re.findall возвращает список найденных строк, но, как и count, без перекрытий: пересекающиеся фрагменты им не посчитать.