XOR

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

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

В математической логике XOR обозначается символом ⊕ (знак плюс в кружке) или оператором \(\veebar\). В программировании и электронике распространены обозначения ^ (в языках C, C++, Java, Python, Go), XOR (в ассемблере, VHDL, Verilog), ⊕ (в схемах и документации). В таблицах истинности для двух входов A и B результат C вычисляется по формуле:

Для более чем двух входов XOR возвращает 1, если количество единиц среди всех операндов нечётно. Это свойство называется «чётность» и широко используется в системах контроля ошибок.

История

Идея исключающего ИЛИ восходит к работам Джорджа Буля (середина XIX века), который формализовал алгебру логики. Однако явное выделение XOR как отдельной операции произошло позже, в контексте развития цифровых вычислительных машин. В 1930-х годах Клод Шеннон в своей магистерской диссертации «Символический анализ релейных и переключательных схем» показал, как операции булевой алгебры могут быть реализованы электрическими реле. XOR стал ключевым элементом для построения полусумматоров и сумматоров — базовых блоков арифметико-логических устройств (АЛУ) первых компьютеров.

В 1940–1950-х годах, с появлением транзисторной логики, XOR-вентили начали изготавливаться из дискретных компонентов. В интегральных схемах (например, серии 7400 ТТЛ) XOR-вентиль (микросхема 7486) стал стандартным элементом. С развитием программирования операция XOR была включена во все основные языки как побитовая и логическая операция.

Свойства и законы

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

• Коммутативность: \(A \oplus B = B \oplus A\).
• Ассоциативность: \((A \oplus B) \oplus C = A \oplus (B \oplus C)\).
• Идемпотентность не выполняется: \(A \oplus A = 0\) (в отличие от OR и AND).
• Нейтральный элемент: \(A \oplus 0 = A\).
• Обратный элемент: \(A \oplus A = 0\), то есть каждый элемент является обратным самому себе.
• Инволюция: \((A \oplus B) \oplus B = A\) — повторное применение XOR с тем же значением восстанавливает исходное.

Последнее свойство лежит в основе многих алгоритмов шифрования и обмена данными.

Применение

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

XOR является основой симметричного шифрования, в частности шифра Вернама (одноразового блокнота). Если имеется открытый текст \(P\) и ключ \(K\) той же длины, то шифротекст \(C = P \oplus K\). Расшифровка выполняется повторным XOR: \(P = C \oplus K\). При условии, что ключ является истинно случайным и используется однократно, шифр Вернама обладает абсолютной криптостойкостью (теорема Шеннона). На практике XOR используется во многих современных алгоритмах (AES, ChaCha20, RC4) как часть раундовых преобразований.

Цифровая электроника

XOR-вентили являются базовыми элементами для построения:

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

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

В программировании XOR применяется в нескольких типовых задачах:

• Обмен значениями без временной переменной: \(a = a \oplus b; b = a \oplus b; a = a \oplus b\). Этот трюк работает для целых чисел и байтов, но не рекомендуется для чисел с плавающей точкой и сложных объектов из-за возможных проблем с производительностью и читаемостью.
• Поиск уникального элемента: В массиве, где все элементы, кроме одного, встречаются дважды, можно найти одиночный элемент, применив XOR ко всем элементам. Результат будет равен искомому элементу.
• Графика: XOR-рисование (XOR-pen) используется в старых графических интерфейсах (например, в Windows 3.x, MS-DOS) для быстрого рисования и стирания курсоров или выделений без перерисовки фона. Повторное применение XOR возвращает исходное изображение.
• Хеширование: XOR используется в некоторых простых хеш-функциях (например, XOR всех байтов строки) и в криптографических конструкциях (например, в функции сжатия MD5, SHA-1).

Теория информации и кодирование

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

Реализация и схемотехника

В цифровой логике XOR-вентиль может быть построен из комбинации базовых вентилей AND, OR, NOT. Минимальная реализация на КМОП-транзисторах требует 8–10 транзисторов (в зависимости от топологии). В современных программируемых логических интегральных схемах (ПЛИС) и процессорах XOR-операция выполняется за один такт для всех разрядов регистра (например, 32-битная побитовая операция XOR).

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

XOR не является функционально полным набором (в отличие от NAND или NOR), то есть с помощью одного только XOR нельзя построить все возможные логические схемы — для этого требуются дополнительные вентили (например, константа 0 или NOT). Кроме того, при использовании XOR в криптографии с повторяющимся ключом (многоразовый блокнот) шифр становится уязвимым к частотному анализу и атакам на основе известного открытого текста.

В некоторых контекстах (например, в языках программирования с нестрогой типизацией) операция XOR может вести себя неочевидным образом, если операнды не являются булевыми или целыми числами (например, в JavaScript true ^ true даёт 0, а "1" ^ "2" — 3).

См. также

• Булева алгебра
• Логический вентиль
• Шифр Вернама
• Контрольная сумма
• Регистр сдвига с линейной обратной связью

Источники

• Шеннон, К. «Символический анализ релейных и переключательных схем» (1938).
• Вирт, Н. «Алгоритмы и структуры данных» (глава о битовых операциях).
• Таненбаум, Э. «Архитектура компьютера» (глава о цифровой логике).
• Шнайер, Б. «Прикладная криптография» (глава о симметричном шифровании).
• Стандарт IEEE 754-2008 (определение битовых операций).
• Документация по языку C (стандарт ANSI C, раздел об операторах).