Исключающее ИЛИ

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

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

Логическая операция «исключающее ИЛИ» обозначается символом ⊕ (в математике), символом ^ (в языках программирования, например, C, C++, Java), или словом XOR (в ассемблере, Verilog, VHDL). В русскоязычной литературе также встречается обозначение + в кружке или ≠ (знак неравенства).

Таблица истинности для двух входов (A и B) и выхода (Y):

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

Свойства

Исключающее ИЛИ обладает рядом алгебраических свойств, которые делают его удобным для практического применения:

• Коммутативность: A ⊕ B = B ⊕ A.
• Ассоциативность: (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C).
• Дистрибутивность: (A ⊕ B) & C = (A & C) ⊕ (B & C) — дистрибутивность относительно конъюнкции (AND).
• Наличие нейтрального элемента: A ⊕ 0 = A.
• Наличие обратного элемента: A ⊕ A = 0.
• Инволютивность: (A ⊕ B) ⊕ B = A (повторное применение XOR с тем же операндом возвращает исходное значение).

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

История

Понятие исключающего ИЛИ восходит к работам древнегреческих философов-стоиков, которые различали «дизъюнкцию» (обычное ИЛИ) и «антидизъюнкцию» (исключающее ИЛИ). В формальной логике операция была систематически описана в XIX веке, в частности, в работах Джорджа Буля и Августа де Моргана. Однако широкое практическое применение она получила только с развитием цифровой электроники в середине XX века. Первые электронные схемы, реализующие XOR, появились в 1940-х годах в составе вычислительных машин, таких как ENIAC, для выполнения арифметических операций.

Реализация в цифровых схемах

В цифровой электронике элемент XOR (логический вентиль) строится на базе комбинации базовых логических элементов: И (AND), ИЛИ (OR) и НЕ (NOT). Типичная схема на два входа реализуется по формуле:

A ⊕ B = (A & ¬B) | (¬A & B)

На практике для построения XOR-вентилей часто используются транзисторные схемы на основе пропускных вентилей (transmission gates) или комплементарные МОП-схемы (CMOS). В современных интегральных микросхемах (например, в ПЛИС и микропроцессорах) элемент XOR является стандартным библиотечным элементом.

Применение

Арифметика и вычислительная техника

• Сложение двоичных чисел: XOR является основой для построения полусумматора и полного сумматора — базовых блоков арифметико-логических устройств (АЛУ) процессоров. Результат сложения двух битов без учёта переноса вычисляется именно через XOR.
• Генерация псевдослучайных чисел: Регистры сдвига с линейной обратной связью (LFSR) используют XOR для формирования последовательностей битов, которые применяются в генераторах случайных чисел, шифровании и тестировании.
• Проверка чётности: XOR всех битов в блоке данных даёт бит чётности, используемый для обнаружения одиночных ошибок в системах хранения и передачи данных (например, в памяти типа ECC).

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

• Шифрование: Свойство инволютивности XOR лежит в основе шифра Вернама (одноразовый блокнот) и многих поточных шифров (например, RC4, Salsa20). В этих алгоритмах открытый текст объединяется операцией XOR с ключевой последовательностью (гаммой). Расшифровка производится повторным применением XOR той же гаммы.
• Хеширование: XOR используется в некоторых криптографических хеш-функциях и контрольных суммах (например, CRC) для смешивания данных.

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

• Обмен значений: Классический трюк для обмена значениями двух переменных без использования временной переменной:

``c a = a ^ b; b = a ^ b; a = a ^ b; `` Этот метод основан на свойстве инволютивности.

• Маскирование битов: XOR позволяет инвертировать определённые биты в числе. Например, x ^ 0xFF инвертирует младший байт числа x.
• Поиск уникального элемента: В массиве, где каждый элемент, кроме одного, встречается дважды, операция XOR всех элементов даст уникальный элемент. Этот алгоритм используется в задачах на собеседованиях и в некоторых структурах данных.

Сетевые технологии

• Зеркалирование (RAID 5): В дисковых массивах RAID 5 для обеспечения отказоустойчивости используется XOR-сумма. Данные на одном диске могут быть восстановлены с помощью XOR данных на оставшихся дисках.

Связь с другими логическими операциями

Исключающее ИЛИ может быть выражено через другие базовые операции:

• Через конъюнкцию, дизъюнкцию и отрицание: A ⊕ B = (A ∨ B) ∧ ¬(A ∧ B)
• Через отрицание эквивалентности: A ⊕ B = ¬(A ↔ B)
• Через импликацию: A ⊕ B = (A → ¬B) ∧ (¬A → B)

В свою очередь, из XOR и константы 1 можно получить отрицание: ¬A = A ⊕ 1. Комбинируя XOR с AND, можно реализовать любую булеву функцию, однако базис {XOR, AND} не является функционально полным (в отличие от {AND, OR, NOT} или {NAND}).

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

• В языке ассемблера x86 инструкция XOR reg, reg (например, XOR EAX, EAX) является стандартным и наиболее быстрым способом обнуления регистра, так как она не зависит от предыдущего значения регистра и имеет короткий машинный код.
• В квантовых вычислениях аналогом XOR является гейт CNOT (Controlled NOT), который переворачивает кубит цели, если управляющий кубит находится в состоянии 1.
• Операция XOR используется в алгоритме поиска пути в лабиринте (например, в алгоритме Тремо), где каждый пройденный коридор отмечается маркером, а повторное прохождение снимает маркер, что эквивалентно применению XOR.

Источники

1. Клини С. К. Введение в метаматематику. — М.: Иностранная литература, 1957. — Глава 3.
2. Хоровиц П., Хилл У. Искусство схемотехники. — 7-е изд. — М.: Мир, 2003. — Том 1. — Глава 4.
3. Кнут Д. Э. Искусство программирования. — 3-е изд. — М.: Вильямс, 2000. — Том 2. — Раздел 3.2.2.
4. Шнайер Б. Прикладная криптография. — 2-е изд. — М.: Триумф, 2002. — Глава 2.
5. Таненбаум Э., Остин Т. Архитектура компьютера. — 6-е изд. — СПб.: Питер, 2013. — Глава 3.