Побитовые AND, OR, XOR, NOT

Начнём с честного вопроса: мы только что научились укладывать числа в биты – зачем теперь эти биты трогать по отдельности? Разве недостаточно обычной арифметики?

Разберём задачу, где обычной арифметики действительно не хватает.

Представьте настройки в приложении: восемь переключателей – уведомления, тёмная тема, автосохранение, звук и так далее. Каждый – «включено / выключено», то есть ровно один бит информации. Можно завести восемь отдельных переменных. Но в уроке 5.1 мы выяснили: даже одно значение «да/нет» занимает в памяти целый байт, потому что байт – минимальная адресуемая порция. Восемь переключателей – восемь байтов, из которых по делу используется восемь битов, а 56 пропадают впустую.

А можно сложить все восемь переключателей в одно число: бит 0 – уведомления, бит 1 – тёмная тема, бит 2 – автосохранение… Тогда все настройки – это один байт, который целиком помещается в одну переменную, одним числом сохраняется в файл и одним числом передаётся по сети. Такое число называют набором флагов, и встречается оно всюду.

Но чтобы с ним работать, нужны инструменты: как узнать, включён ли конкретный переключатель, не трогая остальные? Как включить один, оставив прочие как были? Обычные +, −, * тут не годятся – они смешивают разряды между собой (при сложении бывает перенос). Нужны операции, которые работают с каждым битом независимо от соседей. Это и есть побитовые операции.

Флаги в одном числе – не учебный пример, а рабочая практика. Побитовые операции встречаются как минимум в пяти областях:

• Форматы файлов и сетевые протоколы. Заголовок PNG-файла, TCP-пакет, кадр Wi-Fi – везде поля упакованы в биты, потому что каждый лишний байт умножается на миллиарды передач. Чтобы прочитать такое поле, его нужно «вырезать» из числа побитово. Маска подсети из блока 14 – это буквально операция AND над IP-адресом.
• Права доступа и настройки систем. В Unix-подобных системах права на файл – девять битов: чтение, запись, выполнение для владельца, группы и остальных. Записывают их восьмеричным числом вроде 755 – и это ровно та причина, по которой восьмеричная система оказалась удобной (урок 2.3): три бита прав идеально укладываются в одну восьмеричную цифру.
• Работа с устройствами. Регистр контроллера – это набор битов, где один бит включает питание, другой – режим прерываний. Записать туда «своё» значение целиком нельзя: соседние биты нужно сохранить нетронутыми. Только побитовые операции.
• Скорость. Процессор выполняет побитовую операцию над всеми битами машинного слова разом, за один такт: одна инструкция обрабатывает 64 «да/нет» одновременно. На этом основаны битовые множества – способ хранить множество чисел так, что объединение и пересечение считаются несколькими инструкциями вместо цикла по элементам.
• Криптография и контроль ошибок. Операция XOR лежит в основе шифра Вернама (Гилберт Вернам, патент 1919 года) и входит почти в любой современный шифр и алгоритм хеширования. Бит чётности, которым в старых кодировках защищали каждый символ, тоже считается побитово – к нему мы вернёмся в блоке 7.

И одна честная оговорка, чтобы не возникло перекоса. Программируя на Python, вы вполне можете написать полезную программу и ни разу не встретить & или ^: список и словарь удобнее набора флагов, а память современного компьютера не заставляет экономить каждый бит. Побитовые операции – это не «более правильный» способ писать код. Это язык, на котором описаны форматы данных, устройство процессора и половина алгоритмов, которые вы встретите дальше. Не зная его, вы не сможете прочитать чужое решение – даже если своё написали бы иначе.

Ничего принципиально нового изобретать не придётся. Все четыре операции этого урока – старые знакомые из алгебры логики (уроки 3.2 и 3.3), просто применённые к числам.

Побитовая операция применяет логическую операцию к каждой паре битов двух чисел по отдельности: нулевой бит с нулевым, первый с первым, и так далее. Разряды не влияют друг на друга – переноса, как при сложении, здесь не бывает.

При этом 1 играет роль «истина», 0 – «ложь». То есть одна побитовая операция над 64-битными числами – это 64 независимых логических операции, выполненных за один раз.

Отсюда сразу видно, чем & отличается от and, – а это самая частая путаница в теме:

Отсюда и разница между первыми двумя строками с начала урока: 5 and 3 – это логика над числами целиком (5 – истина, значит результат определяет второй операнд, 3), а 5 & 3 – логика над битами: 0101 и 0011 дают 0001, то есть 1.

Побитовое И (AND, оператор &) даёт в каждом разряде 1 тогда и только тогда, когда в этом разряде обоих чисел стоят единицы.

Таблица истинности – ровно та же, что в уроке 3.2:

Посчитаем 12 & 10 в столбик. Записываем оба числа в восьми битах и идём по разрядам сверху вниз:

  00001100   (12)
& 00001010   (10)
= 00001000   (8)

Единица осталась только в разряде с весом 8 – единственном, где единицы были у обоих чисел. Заметьте: никакого переноса в соседний разряд, в отличие от сложения; каждый столбик считается сам по себе.

Три свойства, которые стоит запомнить (проверить каждое можно по таблице):

• x & 0 = 0 – ноль гасит бит;
• x & 1 = x (для одного бита) – единица оставляет бит как есть;
• значит, x & 11111111 = x, а x & 00000000 = 0.

Из них следует главное практическое применение: И работает как фильтр. Где в «шаблоне» стоит 1 – бит проходит, где 0 – обнуляется. Такой шаблон называют маской, и весь урок 6.3 будет посвящён приёмам работы с ней.

Самый ходовой частный случай – проверка чётности. Число чётно тогда, когда его младший бит равен нулю (вспомните веса разрядов из урока 2.4: все разряды, кроме нулевого, дают чётный вклад). Значит, x & 1 равно 1 у нечётных чисел и 0 у чётных: 6 & 1 → 0, 7 & 1 → 1.

И то же в другую сторону: -5 & 0xFF даёт 251 – это ровно тот пример из урока 5.2, где маска & 0xFF показывала восьмибитный дополнительный код. Теперь понятно, что там происходило: маска из восьми единиц отфильтровала младший байт, отбросив всё остальное.

Побитовое ИЛИ (OR, оператор |) даёт в каждом разряде 1, если хотя бы в одном из чисел в этом разряде стоит единица.

Те же 12 и 10:

  00001100   (12)
| 00001010   (10)
= 00001110   (14)

Свойства зеркальны свойствам И:

• x | 0 = x – ноль не меняет бит;
• x | 1 = 1 – единица включает бит принудительно.

Отсюда применение: ИЛИ объединяет наборы флагов. Если в одном числе включены настройки A и C, а в другом – B, то | даст число со всеми тремя. Именно так собираются наборы опций во множестве библиотек: флаг_A | флаг_B | флаг_C – привычная запись, которую вы наверняка ещё встретите.

Напомню про приоритет из блока 3: логическое И «сильнее» ИЛИ (аналог умножения и сложения), и у побитовых версий приоритет устроен так же – & считается раньше |. К приоритетам вернёмся отдельно.

Побитовое исключающее ИЛИ (XOR, оператор ^) даёт в каждом разряде 1, если биты различны, и 0, если одинаковы.

Отличие от обычного ИЛИ – ровно одна строка, последняя: «оба сразу» здесь не считается. Название на русском – исключающее ИЛИ, «или то, или другое, но не оба».

  00001100   (12)
^ 00001010   (10)
= 00000110   (6)

У этой операции есть второе имя – сложение по модулю 2. Оно точное: 0+0=0, 0+1=1, 1+0=1, а 1+1=2, что по модулю 2 даёт 0 – в точности таблица выше. То есть XOR – это сложение битов без переноса в старший разряд.

Важно не спутать с оператором возведения в степень: в Python степень – это **, а ^ означает именно XOR и ничего больше. В математической записи для той же операции используют знак $\oplus$.

XOR – самая интересная из четырёх операций, потому что у неё есть свойство, которого нет у И и ИЛИ:

• x ^ 0 = x – ноль ничего не меняет;
• x ^ x = 0 – число, применённое к самому себе, обнуляется;
• x ^ 11111111 = инверсия x – единица переворачивает бит.

А из первых двух следует то, ради чего XOR попал во все шифры:

(x ^ k) ^ k = x – применив XOR с одним и тем же числом дважды, мы получаем исходное значение.

Проверить это можно и по таблице, и в интерпретаторе: (5 ^ 3) ^ 3 даёт 5. Никакая другая из наших операций так не умеет – после & или | часть информации теряется безвозвратно.

Отсюда простейший шифр: возьмём текст, возьмём ключ и применим XOR к каждому символу. Получится шифровка; применим XOR с тем же ключом ещё раз – вернётся исходный текст. Одна и та же процедура и шифрует, и расшифровывает. Именно эту идею предложил Гилберт Вернам ещё в 1917 году (патент 1919-го) для телеграфных сообщений – и если ключ по-настоящему случаен, не короче сообщения и используется однократно, такой шифр математически невзламываем. Все три условия на практике выполнить трудно, поэтому в чистом виде шифр Вернама почти не применяют, но XOR как строительный кирпич остался в основе современной криптографии.

К обратимости XOR мы вернёмся в уроке 6.4 – там она даст красивый фокус с обменом значений двух переменных без третьей.

Первые три операции брали два числа. Четвёртая – унарная, она работает с одним:

Побитовое НЕ (NOT, оператор ~) переворачивает каждый бит числа: нули становятся единицами, единицы – нулями.

Для восьмибитного числа это выглядит просто:

~ 00000101   (5)
= 11111010

Ничего особенного тут не происходит: биты просто перевернулись. Но набор битов 11111010 можно прочитать двумя способами – как беззнаковое число это 250, а как знаковое, в дополнительном коде из урока 5.2, это −6. Сами биты одни и те же, разное только чтение. Python на print(~5) выбирает второе и выводит −6.

Разберём это превращение по шагам. Инвертировать все биты n-битного числа x – то же самое, что вычесть его из числа «все единицы», то есть из $2^n - 1$:

инверсия $x = (2^n - 1) - x$

А знаковое чтение в дополнительном коде из значения $\ge 2^{n-1}$ вычитает $2^n$. Для нашего примера: 255 − 5 = 250, затем 250 − 256 = −6. Общая формула получается короткой и от разрядности не зависит:

~x = −x − 1

Проверьте на любых числах: ~0 → −1, ~(-1) → 0, ~5 → −6, ~(-6) → 5. Инверсия – операция обратная сама себе, поэтому применённая дважды она возвращает исходное число.

И почему у Python получилось именно так, а не 250. В уроке 5.1 мы отмечали: тип int в Python не имеет фиксированной ширины. Значит, у числа 5 нет «ровно восьми битов» – слева у него бесконечная цепочка нулей, и инверсия превращает её в бесконечную цепочку единиц. А бесконечная цепочка единиц слева – это в точности запись отрицательного числа в дополнительном коде. Отсюда правило: в Python результат ~ для неотрицательного числа всегда отрицателен.

Если нужна инверсия внутри конкретной разрядности – придётся ограничить её маской: ~5 & 0xFF даёт те самые 250. То есть маска не «исправляет» результат, а прямо говорит: меня интересуют только младшие восемь битов.

Последнее: не путайте ~ с not. Оператор not – логический, он работает с истинностью значения целиком и возвращает True/False; ~ работает с битами и возвращает число. not 5 даёт False, ~5 даёт −6.

Сводная таблица – то, что стоит держать перед глазами при решении задач:

А ниже – те же четыре операции живьём. Переключатель меняет операцию, биты в строках a и b кликабельны, значения можно вводить и числом. Главное, что стоит заметить: столбики независимы – наведите на любой разряд, и виджет покажет, как получился именно его бит, не заглядывая в соседние.

Что стоит попробовать:

• Нажмите пресет «маска младших разрядов»: b из четырёх единиц с операцией & оставляет от числа a ровно младшую половину, остальное обнуляет. Это и есть фильтр из урока 6.3, вживую.
• Оставьте b из всех единиц и сравните & с ^: в первом случае a не меняется вовсе, во втором – переворачивается целиком.
• Возьмите b = 1 и меняйте a: младший разряд результата и есть ответ на вопрос о чётности.
• Переключитесь на ~ – строка b исчезнет (операция унарная), а под результатом появится и восьмибитное значение, и то, что напечатает Python.

Соберём результаты для одной пары чисел в таблицу – так разница между операциями видна в одном месте:

Полезная проверка, которую видно прямо в таблице: (a & b) + (a ^ b) = 8 + 6 = 14 = a | b. Это не совпадение – И собирает разряды, где единицы у обоих, XOR – где ровно у одного, а вместе они дают все разряды, где единица есть хоть где-то.

Побитовые операторы стоят в таблице приоритетов Python на неожиданном месте, и это источник ошибок. Порядок от сильного к слабому:

1. ~, унарный минус
2. *, /, //, %
3. +, −
4. <<, >> (сдвиги – урок 6.2)
5. &
6. ^
7. |
8. сравнения: <, >, ==, !=
9. not, and, or

Из этого списка следуют два практических вывода.

Арифметика связывает сильнее побитовых операций. Выражение mask & a + b означает mask & (a + b), а вовсе не (mask & a) + b. Такую ошибку глазами не поймать – программа не падает, просто считает не то. Скобки здесь стоит ставить всегда, даже когда они формально не нужны: (mask & a) + b читается однозначно.

А вот со сравнениями Python как раз безопасен – и это стоит знать, потому что в других языках не так. Запись x & 1 == 0 в Python разбирается как (x & 1) == 0, то есть работает ожидаемо. В C, C++ и Java приоритеты противоположные: там & слабее ==, и то же выражение превращается в x & (1 == 0) – классическая ловушка, на которой спотыкались поколения программистов. Разработчики Python сознательно исправили этот порядок. Но привычка ставить скобки в таких проверках остаётся хорошей: (x & 1) == 0 одинаково верно читается и человеком, и на любом языке.

Чтобы проверять всё сказанное самому, нужен способ увидеть биты, а не десятичное значение. Их два.

Первый – функция bin(): она возвращает строку с двоичной записью и приставкой 0b. Ведущих нулей в ней нет, поэтому bin(12) даёт 0b1100, а не 0b00001100.

Второй нужен как раз тогда, когда нули важны – например, чтобы сравнить два числа столбик в столбик. Это форматирование:

print(f'{12:08b}')   # 00001100

Читается запись так: взять значение перед двоеточием и вывести его в двоичной системе (b), дополнив нулями (0) до восьми знаков (8). Замените b на x – получите шестнадцатеричную запись, замените 8 на 16 – получите шестнадцать разрядов. Подробно про такие строки – в блоке 8; пока достаточно уметь ими пользоваться, дальше в уроках блока эта запись встретится не раз.