Побитовая операция XOR¶

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

¶Определение и таблица истинности

Операция XOR является одной из базовых логических операций наряду с AND (конъюнкция), OR (дизъюнкция) и NOT (отрицание). Для двух входных битов (A и B) результат вычисляется по следующему правилу:

В алгебре логики операция XOR обозначается символом ⊕ (знак плюс в кружке) или символом ≠ (неравенство). В языках программирования обычно используется знак ^ (циркумфлекс).

¶Математические свойства

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

• Коммутативность: A ⊕ B = B ⊕ A.
• Ассоциативность: (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C).
• Наличие нейтрального элемента: A ⊕ 0 = A.
• Наличие обратного элемента: A ⊕ A = 0.
• Самодвойственность: A ⊕ B = ¬(A ⊕ B) (отрицание результата равно результату при отрицании обоих операндов).

Из этих свойств следует, что XOR является обратимой операцией: если C = A ⊕ B, то A = C ⊕ B и B = C ⊕ A. Это свойство лежит в основе многих криптографических и алгоритмических приёмов.

¶Применение в программировании

¶Шифрование и криптография

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

¶Проверка чётности и контрольные суммы

XOR используется для вычисления простейших контрольных сумм. Например, при передаче данных по последовательному интерфейсу (RS-232) часто применяется XOR-сумма всех байтов сообщения для обнаружения ошибок. В RAID-массивах (уровень 5) данные на дисках распределяются так, что один из дисков хранит XOR-сумму остальных, что позволяет восстановить данные при отказе одного диска.

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

Благодаря обратимости XOR, можно обменять значения двух переменных без использования дополнительной памяти:

`` a = a ^ b b = a ^ b a = a ^ b ``

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

¶Поиск уникального элемента

В задачах, где требуется найти элемент, встречающийся нечётное число раз среди массива, где все остальные элементы встречаются чётное число раз, используется XOR всех элементов. Результат будет равен искомому элементу, так как все парные элементы обнулятся (A ⊕ A = 0).

¶Применение в цифровой электронике

¶Схемотехника

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

¶Генерация псевдослучайных чисел

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

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

Несмотря на широкое применение, XOR имеет ограничения. В криптографии использование XOR без дополнительных мер (например, без обеспечения случайности ключа) приводит к уязвимостям. При повторном использовании одного и того же ключа для разных сообщений (атака «two-time pad») злоумышленник может восстановить оба сообщения. В схемотехнике реализация XOR на КМОП-транзисторах требует большего числа транзисторов (обычно 8–12), чем для AND или OR (4–6), что увеличивает площадь кристалла и энергопотребление.

¶Интересные факты

• В языке программирования C и многих других языках оператор ^ обозначает побитовое XOR, а не возведение в степень (для этого используется pow()).
• В некоторых архитектурах процессоров (например, x86) инструкция XOR используется для быстрого обнуления регистра, так как она короче и быстрее, чем инструкция MOV с нулём.
• Операция XOR является единственной бинарной логической операцией, которая является одновременно ассоциативной, коммутативной и обратимой.

¶Источники

• Таненбаум Э., Остин Т. «Архитектура компьютера». — 6-е изд. — СПб.: Питер, 2013.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ». — 3-е изд. — М.: Вильямс, 2013.
• Шнайер Б. «Прикладная криптография». — 2-е изд. — М.: Триумф, 2002.
• ГОСТ 28147-89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования».
• Стандарт IEEE 754-2019 «Standard for Floating-Point Arithmetic» (раздел о контрольных суммах).