XOR | это... Что такое XOR? (original) (raw)

Сложе́ние по модулю 2 (исключа́ющее «ИЛИ», XOR, «сумма по модулю 2») — ло­ги­чес­кая опе­ра­ция, по сво­ему при­ме­не­нию мак­си­маль­но при­бли­жен­ная к грам­ма­ти­чес­кой кон­струк­ции «либо … либо …».

Это бинарная инфиксная опе­ра­ция, то есть она имеет два опе­ранда и ста­вит­ся между ними. Чаще всего встре­ча­ют­ся сле­ду­ю­щие ва­ри­анты за­пи­си:
~a ^ ~b, ~a \oplus b, a \oplus_2 b, a + b, a +_2 b, a ~XOR~ b.

Содержание

Булева алгебра

В булевой алгебре сложение по модулю 2 — это функция двух переменных (они же — операнды операции). Переменные могут принимать значения из множества ~\{0, 1\}. Результат также принадлежит множеству ~\{0, 1\}. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений ~0, 1 может использоваться любая другая пара подходящих символов, например ~false, true или ~F, T или «ложь», «истина».

Правило: результат равен ~0, если оба операнда равны; во всех остальных случаях результат равен ~1.

Таблица истинности:

~a ~b ~a \oplus b
~0 ~0 ~0
~0 ~1 ~1
~1 ~0 ~1
~1 ~1 ~0

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

В языках C/C++ (а также Java, C#, Ruby, PHP, JavaScript и т. д.) эта операция обозначается символом «^», в языках Паскаль, Delphi, Ada - зарезервированным словом XOR, в языке ассемблера - одноименной логической командой. Сложение по модулю 2 выполняется для всех битов левого и правого операнда попарно. Например,

Выполнение операции XOR для значений логического типа (true, false) производится в разных языках программирования по-разному. Например в Delphi используется встроенный оператор XOR (пример: condition1 xor condition2). В языке C, начиная со стандарта С++ оператор «^» для логического типа bool возвращает результат согласно описанным правилам, для остальных же типов проихводится его побитовое применение. Перегрузка для стандартных типов невозможна, но операцию XOR над ними можно реализовать, исходя из принципа "исключающего ИЛИ". Выглядит это так:

(condition1 || condition2) && (condition1 != condition2)

(при этом нет разницы, применяются ли побитовые операторы & и |, или же логические && и ||)

Связь с естественным языком

Часто указывают на сходство между сложением по модулю 2 и конструкцией «либо … либо …» в естественном языке. Составное утверждение «либо A, либо B» считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно. Это в точности соответствует определению операции в булевой алгебре, если «истину» обозначать как 1, а «ложь» как 0.

Эту операцию нередко сравнивают с дизъюнкцией потому, что они очень похожи по свойствам, и обе имеют сходство с союзом «или» в повседневной речи. Сравните правила для этих операций:

  1. A \lor B истинно, если истинно ~A или ~B, или оба сразу.
  2. A \oplus B истинно, если истинно ~A или ~B, но не оба сразу.

Операция \oplus исключает последний вариант («оба сразу») и по этой причине называется исключающим «ИЛИ». Операция \lor включает последний вариант («оба сразу») и по этой причине иногда называется включающим «ИЛИ». Неоднозначность естественного языка заключается в том, что союз «или» может применяться в обоих случаях.

См. также

Wikimedia Foundation.2010.