11 мин чтенияпоразрядные операциимаскиXORсдвигизадание 13задание 14задание 15КЕГЭ
Поразрядные операции и маски
Операции &, |, ^, ~, сдвиги, установка и сброс битов, проверка степени двойки и подсчёт единиц; применение в заданиях 13–15 (маски сетей и параметры логических формул).
Открываем тему…
Битовые операции и их таблицы
Поразрядная операция применяется к двоичным записям чисел отдельно в каждом разряде. В Python это операторы &, |, ^, ~, << и >>. Задания КЕГЭ с масками (расчёт адреса сети, проверка делимости, формулы вида (x & A) ≠ 0) решаются рассуждением о конкретных битах, а не перебором значений.
- x & y (поразрядное И): в разряде 1, только если в обоих числах 1. Используется для «вырезания» бит, проверки флага, получения адреса сети.
- x | y (поразрядное ИЛИ): в разряде 1, если хотя бы в одном числе 1. Используется для установки бит.
- x ^ y (исключающее ИЛИ, XOR): в разряде 1, если биты различны. Свойства: x ^ x = 0, x ^ 0 = x, операция коммутативна и ассоциативна.
- x << k умножает на 2^k, x >> k — целочисленное деление на 2^k.
- Проверка бита: (x >> i) & 1. Установка: x | (1 << i). Сброс: x & ~(1 << i). Инверсия: x ^ (1 << i).
- Число x (x > 0) является степенью двойки тогда и только тогда, когда x & (x − 1) = 0; выражение x & (x − 1) сбрасывает младшую единицу.
Примеры
ПримерИ, ИЛИ и исключающее ИЛИ
Вычислите 53 & 46, 53 | 46 и 53 ^ 46.
Решение
Двоичные записи: 53 = 110101₂, 46 = 101110₂. По разрядам:
И: 110101 & 101110 = 100100₂ = 36;
ИЛИ: 110101 | 101110 = 111111₂ = 63;
XOR: 110101 ^ 101110 = 011011₂ = 27.
Связь: a + b = (a ^ b) + 2·(a & b). Проверка: 27 + 2·36 = 99 = 53 + 46.
Python: print(53 & 46, 53 | 46, 53 ^ 46).
ПримерСдвиги
Чему равно значение выражения (37 << 3) >> 2?
Решение
37 << 3 = 37·8 = 296. Затем 296 >> 2 = 296 // 4 = 74. Эквивалентно 37·2 = 74. Сдвиг влево на k в двоичной записи дописывает k нулей справа, сдвиг вправо отбрасывает k младших бит; при >> остаток теряется.
ПримерУстановка и сброс бит
В числе 100 установите бит 3 и сбросьте бит 5 (биты нумеруются с нуля справа). Какое число получится?
Решение
100 = 1100100₂ (биты 6, 5 и 2 равны 1). Установка бита 3: 100 | (1 << 3) = 100 | 8 = 108 = 1101100₂. Сброс бита 5: 108 & ~(1 << 5) = 108 & ~32 = 76 = 1001100₂.
Эквивалентная запись: x = (100 | 8) & ~32 → 76. Бит 5 был единичным, поэтому действительно изменился; если бы он уже был нулём, сброс ничего бы не изменил.
ПримерСтепени двойки через x & (x − 1)
Сколько чисел от 1 до 1000 являются степенями двойки? Как проверить это поразрядно?
Решение
Число x > 0 — степень двойки, если в двоичной записи ровно одна единица, то есть x & (x − 1) = 0 (вычитание единицы превращает младшую единицу в 0, а все нули правее неё — в 1).
print(sum(1 for x in range(1, 1001) if x & (x - 1) == 0))
Ответ: 10 (числа 1, 2, 4, …, 512 = 2⁰…2⁹).
ПримерПоразрядная конъюнкция и параметр A
Обозначим x & y поразрядную конъюнкцию. Для какого наименьшего натурального A формула (x & A = 0) → ((x & 12 ≠ 0) → (x & 21 = 0)) тождественно истинна?
Решение
Формула ложна, когда x & A = 0, x & 12 ≠ 0 и x & 21 ≠ 0 одновременно. Выпишем единичные биты масок: 12 = 1100₂ (биты 2 и 3), 21 = 10101₂ (биты 0, 2, 4). Условия x & 12 ≠ 0 и x & 21 ≠ 0 одновременно выполняются, например, при x = 4 (бит 2 попадает в обе маски), x = 9 (биты 3 и 0), x = 24 (биты 3 и 4). Для каждого такого x нужно, чтобы x & A ≠ 0, то есть в A должен быть общий бит с x. Для x = 4 нужен бит 2; для x = 9 — бит 0 или бит 3; для x = 24 — бит 3 или бит 4.
Минимальное A, удовлетворяющее всем трём требованиям (бит 2 и один из {0, 3} и один из {3, 4}): биты 2 и 3, A = 4 + 8 = 12. Проверка перебором по x до 4095 подтверждает ответ 12.
for A in range(1, 100):
if all(x & A != 0 or x & 12 == 0 or x & 21 == 0 for x in range(1, 4096)):
print(A)
break
ПримерАдрес сети: IP & маска
Узел имеет IP-адрес 192.168.37.201 и маску 255.255.240.0. Найдите адрес сети.
Решение
Адрес сети получается поразрядным И адреса и маски в каждом байте. Первые два байта маски равны 255, поэтому 192.168 сохраняются. Третий байт: 37 & 240 = 00100101₂ & 11110000₂ = 00100000₂ = 32. Четвёртый: 201 & 0 = 0.
Адрес сети: 192.168.32.0. Число адресов в сети 2^12 = 4096 (в маске 255.255.240.0 нулевых бит: 4 + 8 = 12). Это же вычисление на Python: print(37 & 240).
ПримерЧисло единиц в записи значения выражения
Сколько единиц содержится в двоичной записи числа 2⁵⁰ − 1 − 2²⁰?
Решение
Число 2⁵⁰ − 1 записывается 50 единицами (биты 0…49). Вычитание 2²⁰ сбрасывает бит 20, который был единичным, поэтому остаётся 49 единиц.
print(bin(2**50 - 1 - 2**20).count('1')) # 49
Тот же приём работает и в задании 14: блоки единиц удобно описывать как 2^a − 1, а отдельные «дырки» — вычитанием степеней двойки.
ПримерНечётный элемент по XOR
В списке 5, 7, 5, 9, 7, 9, 4 каждое число, кроме одного, встречается чётное число раз. Найдите число, которое встречается нечётное число раз.
Решение
Так как x ^ x = 0 и XOR коммутативен, пары одинаковых чисел взаимно уничтожаются: 5 ^ 7 ^ 5 ^ 9 ^ 7 ^ 9 ^ 4 = 4. На Python:
from functools import reduce
print(reduce(lambda a, b: a ^ b, a))
Ответ: 4. Такой подход использует O(n) времени и O(1) памяти.