Побитовое сложение по модулю 2

Побитовое сложение по модулю 2 (также известное как исключающее «ИЛИ», XOR, сложение по модулю два, побитовое XOR) — это бинарная логическая операция, результат которой равен 1 (истине) тогда и только тогда, когда количество истинных операндов нечётно. В случае двух операндов операция даёт 1, когда они различны, и 0, когда они одинаковы. Операция является фундаментальной для булевой алгебры, цифровой электроники и компьютерных наук, лежит в основе многих алгоритмов кодирования, криптографии и проверки целостности данных.

Определение и обозначения

Побитовое сложение по модулю 2 применяется к двоичным разрядам (битам) чисел одинаковой длины. Для каждого бита выполняется операция XOR, результат которой для пары битов (a, b) определяется следующей таблицей истинности:

В математике и программировании операцию обозначают символами: ⊕, XOR, ^, + (в кружке), mod 2 или + (в контексте поля Галуа GF(2)). В языках программирования, таких как C, C++, Java, Python, оператор побитового XOR — это ^ (например, a ^ b). В электронике для обозначения логического элемента XOR используется символ =1 или ⊕.

Свойства

Операция обладает рядом важных алгебраических свойств, которые делают её удобной для практического применения:

• Коммутативность: a ⊕ b = b ⊕ a.
• Ассоциативность: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c).
• Нейтральный элемент: a ⊕ 0 = a.
• Обратный элемент: a ⊕ a = 0. Каждый элемент является обратным самому себе.
• Идемпотентность отсутствует: a ⊕ a ≠ a (за исключением случая a = 0).
• Дистрибутивность относительно конъюнкции (AND): (a ⊕ b) & c = (a & c) ⊕ (b & c). Однако конъюнкция не дистрибутивна относительно XOR.
• Инволютивность: Применение XOR дважды с одним и тем же числом возвращает исходное значение: (a ⊕ b) ⊕ b = a. Это свойство лежит в основе простейших алгоритмов шифрования и обмена значениями.

Применение

Криптография

Побитовое XOR является основой многих симметричных шифров, включая шифр Вернама (одноразовый блокнот) и шифры, использующие гаммирование. В шифре Вернама открытый текст (P) объединяется с ключом (K) той же длины через XOR: C = P ⊕ K. Расшифровка выполняется повторным применением XOR: P = C ⊕ K. При условии, что ключ является истинно случайным, используется только один раз и хранится в секрете, такая система обеспечивает абсолютную криптостойкость (теорема Шеннона). В современных блочных шифрах (AES, ГОСТ 28147-89) XOR используется для смешивания данных с раундовыми ключами.

Алгоритмы проверки целостности

XOR применяется в простых контрольных суммах (checksums). Например, при вычислении чётности (parity bit) для обнаружения одиночных ошибок в передаче данных: бит чётности равен XOR всех битов передаваемого слова. В RAID-массивах (например, RAID 5) данные распределяются по дискам, а один диск хранит блок чётности, вычисленный как XOR всех блоков данных. Это позволяет восстановить информацию при выходе из строя одного диска.

Обмен значениями без временной переменной

Свойство инволютивности позволяет обменять значения двух переменных a и b без использования дополнительной памяти:

1. a = a ⊕ b
2. b = a ⊕ b (теперь b = a_исходное)
3. a = a ⊕ b (теперь a = b_исходное)

Этот трюк часто используется в низкоуровневом программировании и алгоритмах, хотя на современных процессорах он может быть менее эффективным, чем прямой обмен через регистр.

Графика и компьютерное зрение

В растровой графике операция XOR применяется для быстрого рисования и удаления объектов (например, при перемещении курсора мыши или выделении области). При повторном наложении того же изображения с помощью XOR исходное изображение восстанавливается, что позволяет реализовать «резиновые линии» и интерактивные инструменты без постоянного перерисовывания всего кадра.

Математика и теория кодирования

В теории кодирования XOR используется в линейных кодах (например, коды Хэмминга) для построения проверочных матриц и вычисления синдромов ошибок. В конечных полях Галуа GF(2) сложение по модулю 2 является основной операцией, на которой построены многие алгоритмы коррекции ошибок (коды Рида-Соломона, коды БЧХ).

Реализация в цифровой электронике

Логический элемент XOR (исключающее ИЛИ) является одним из базовых элементов цифровых микросхем. Он может быть реализован на транзисторном уровне (например, с помощью комплементарных МОП-транзисторов, CMOS) или собран из комбинации элементов И, ИЛИ, НЕ. В стандартных сериях микросхем (например, 74HC86, К155ЛП5) содержатся четыре двухвходовых элемента XOR в одном корпусе. В программируемых логических интегральных схемах (ПЛИС) элементы XOR являются частью логических ячеек.

Примеры

Пример 1 (побитовое XOR двух чисел):

Число A = 12 (двоичное 1100) Число B = 10 (двоичное 1010)

Результат: A ⊕ B = 1100 ⊕ 1010 = 0110 (десятичное 6)

Пример 2 (проверка чётности):

Пусть передаётся байт 10110110. Количество единиц — 5 (нечётное). Для обеспечения чётности (even parity) добавляется бит чётности, равный 1, чтобы общее число единиц стало чётным (6). Этот бит вычисляется как XOR всех битов данных: 1⊕0⊕1⊕1⊕0⊕1⊕1⊕0 = 1.

Критика и ограничения

Несмотря на широкое применение, побитовое XOR имеет ограничения. В криптографии шифры, основанные исключительно на XOR (без перемешивания и нелинейных преобразований), являются уязвимыми для атак с известным открытым текстом и статистического анализа. В качестве контрольной суммы XOR не способен обнаружить чётное количество ошибок в одном бите (например, две ошибки в одном разряде дадут нулевое изменение). Для надёжного обнаружения ошибок используются более сложные алгоритмы, такие как CRC (циклический избыточный код).

Источники

• Таненбаум Э., Уэзеролл Д. «Компьютерные сети» (раздел 3.2.2 — Контрольные суммы).
• Шнайер Б. «Прикладная криптография» (глава 2 — Шифр Вернама).
• Хоровиц П., Хилл У. «Искусство схемотехники» (том 1, глава 8 — Логические элементы).
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (глава 1 — Побитовые операции).
• ГОСТ 28147-89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования».