Битовые логические операции

Урок о том, как те же И/ИЛИ/НЕ/исключающее-ИЛИ работают сразу над всеми битами числа и зачем это нужно для флагов и масок.

Битовые операции применяют логическую функцию к каждой паре соответствующих битов двух чисел независимо: & — И, | — ИЛИ, ^ — исключающее ИЛИ, ~ — НЕ.

Логические and/or отвечают на вопрос «истинно ли условие в целом». Битовые &/| работают тоньше: они берут двоичные записи чисел и применяют логику поразрядно. Один int при этом хранит десятки независимых «да/нет» — это компактный и быстрый способ работать с наборами признаков.

Зачем это нужно

Битовые операции — это упакованная логика. Вместо восьми переменных-флагов держат одно число, где каждый бит — отдельный признак: бит 0 — «прочитано», бит 1 — «важное», бит 2 — «архив» и так далее. Включать, выключать и проверять такие признаки удобно масками. Это основа прав доступа (Unix-режимы rwx), графики (каналы цвета), сетевых протоколов и многих задач ЕГЭ на системы счисления.

Четыре операции на разрядах

Возьмём два числа: $12 = 1100_2$ и $10 = 1010_2$. Применим к ним поразрядно все операции. Конъюнкция оставляет бит, только если он есть в обоих; дизъюнкция — если хотя бы в одном; XOR — если ровно в одном:

Разряд	8	4	2
12	1	1	0
10	1	0	1
`&` (И)	1	0	0
`\|` (ИЛИ)	1	1	1
`^` (XOR)	0	1	1

Читаем результаты как двоичные числа: $1000_2 = 8$, $1110_2 = 14$, $0110_2 = 6$. Проверим в Python и выведем двоичную запись через bin():

a, b = 12, 10
print("a =", a, "=", bin(a))
print("b =", b, "=", bin(b))
print("a & b =", a & b, "=", bin(a & b))   # И
print("a | b =", a | b, "=", bin(a | b))   # ИЛИ
print("a ^ b =", a ^ b, "=", bin(a ^ b))   # XOR

Вывод:

a = 12 = 0b1100
b = 10 = 0b1010
a & b = 8 = 0b1000
a | b = 14 = 0b1110
a ^ b = 6 = 0b110

Числа сошлись с таблицей. XOR полезен тем, что повторное применение возвращает исходное: $x \oplus k \oplus k = x$ — на этом строят простейшее обратимое преобразование.

Отрицание ~ и почему оно «отрицательное»

Оператор ~ инвертирует все биты. В Python целые знаковые и бесконечно «широкие», поэтому действует тождество

$$ \sim\! x = -x - 1 $$

for x in (0, 5, 12):
    print("~", x, "=", ~x, "  (проверка -x-1 =", -x - 1, ")")

Вывод:

~ 0 = -1   (проверка -x-1 = -1 )
~ 5 = -6   (проверка -x-1 = -6 )
~ 12 = -13   (проверка -x-1 = -13 )

Сдвиги как умножение и деление на степень двойки

Сдвиг влево x << n дописывает справа n нулей — это умножение на $2^n$. Сдвиг вправо x >> n отбрасывает n младших битов — это целочисленное деление на $2^n$:

$$ x \ll n = x\cdot 2^{n}, \qquad x \gg n = \left\lfloor \frac{x}{2^{n}} \right\rfloor $$

x = 12
print("12 << 1 =", x << 1, "=", bin(x << 1))   # ×2
print("12 << 2 =", x << 2, "=", bin(x << 2))   # ×4
print("12 >> 1 =", x >> 1, "=", bin(x >> 1))   # //2
print("12 >> 2 =", x >> 2, "=", bin(x >> 2))   # //4

Вывод:

12 << 1 = 24 = 0b11000
12 << 2 = 48 = 0b110000
12 >> 1 = 6 = 0b110
12 >> 2 = 3 = 0b11

Флаги и маски: главное применение

Маска — это число с единицей на нужном разряде: 1 << n даёт бит номер n. Три типовые операции с флагами:

Поставить бит: flags = flags | mask (ИЛИ всегда «зажигает»).
Проверить бит: flags & mask — ненулевое значение означает «бит установлен».
Снять бит: flags = flags & ~mask (И с инверсией маски «гасит» один разряд, не трогая остальные).

READ  = 1 << 0   # 0b001 = 1
WRITE = 1 << 1   # 0b010 = 2
EXEC  = 1 << 2   # 0b100 = 4

flags = 0
flags |= READ            # включаем чтение
flags |= WRITE           # включаем запись
print("после set:", bin(flags), "=", flags)

print("WRITE включён?", bool(flags & WRITE))
print("EXEC включён? ", bool(flags & EXEC))

flags &= ~WRITE          # снимаем запись
print("после снятия:", bin(flags), "=", flags)

Вывод:

после set: 0b11 = 3
WRITE включён? True
EXEC включён?  False
после снятия: 0b1 = 1

Одно число 3 = 0b011 закодировало «чтение + запись». Снятие WRITE оставило 0b001 — чистое «чтение». Так в одном int живёт целый набор настроек.

Как это работает

Процессор умеет применять логику к слову целиком за одну инструкцию: 64 бита обрабатываются параллельно. Поэтому &, |, ^ — одни из самых дешёвых операций. Важно отличать их от логических and/or: те работают с истинностью объекта в целом и используют короткое замыкание (см. первый урок раздела), а битовые всегда вычисляют оба операнда и идут по разрядам. Сравните: 4 and 2 даёт 2 (оба истинны как объекты, вернётся последний), а 4 & 2 даёт 0 (у $100_2$ и $010_2$ нет общих единичных битов). Это разные миры, и путать их — источник тонких багов.

Частые ошибки

Путают & и and. В условии if a & b вместо if a and b легко получить неожиданный результат: 2 & 1 == 0, хотя оба числа истинны. Для логики условий — and/or, для битов — &/|.
Забывают про приоритет. У &, |, ^ приоритет ниже, чем у сравнений. x & 1 == 0 читается как x & (1 == 0), то есть x & False. Пишите (x & 1) == 0.
Снимают бит через XOR вслепую. flags ^ mask переключает бит, а не гарантированно снимает: если он был выключен, XOR его включит. Для надёжного снятия — flags & ~mask.
Ждут «обнуления» от ~. ~x в Python не «маленькое положительное», а $-x-1$ из-за бесконечной знаковой разрядности; для работы в фиксированной ширине маскируйте результат, например ~x & 0xFF.

Итоги

&, |, ^, ~ — это И, ИЛИ, исключающее-ИЛИ и НЕ, применённые к каждому разряду по отдельности.
Сдвиги: x << n умножает на $2^n$, x >> n делит нацело на $2^n$.
Флаги: поставить — | mask, проверить — & mask, снять — & ~mask; один int хранит набор признаков.
Битовые операции — не то же, что and/or: они идут по битам и всегда вычисляют оба операнда.