Исключающее или что значит

Основные логические операции. AND, NOT, OR и XOR (исключающее или)

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

Как известно, минимальной единицей измерения информации является бит, который хранит одно из 2-х значений: 0 (False, ложь) либо 1 (True, истина). Таким образом, битовая ячейка может одновременно находиться лишь в одном из двух возможных состояний.

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

Логическая операция AND (и)

AND обозначается знаком & .

Оператор AND выполняется с 2-мя битами, возьмём, к примеру, a и b. Результат выполнения операции AND равен 1, если a и b равняются 1. В остальных случаях результат равен 0. Например, с помощью AND вы можете узнать, чётное число или нет.

Посмотрите на таблицу истинности операции AND:

Логическая операция OR (ИЛИ)

Оператор OR также выполняется с 2-мя битами (a и b). Результат равен 0, если a и b равны 0, иначе он равен 1. Смотрим таблицу истинности.

Логическая операция XOR (исключающее ИЛИ)

Оператор XOR обозначается ^ .

XOR выполняется с 2-мя битами (a и b). Результат выполнения операции XOR (исключающее ИЛИ) равен 1, когда один из битов b или a равен 1. В остальных ситуациях результат применения оператора XOR равен 0.

Таблица истинности логической операции для XOR (исключающее ИЛИ) выглядит так:

Используя XOR (исключающее ИЛИ), вы можете поменять значения 2-х переменных одинакового типа данных, не используя временную переменную. А ещё, посредством XOR можно зашифровать текст, например:

String msg = «This is a message»; char[] message = msg.toCharArray(); String key = «.*)»; String encryptedString = new String(); for(int i = 0; i

Согласен, XOR — далеко не самый надёжный метод шифрования, но это не значит, что его нельзя сделать частью какого-либо шифровального алгоритма.

Логическая операция NOT (НЕ)

Это побитовое отрицание, поэтому выполняется с одним битом и обозначается ~ .

Результат зависит от состояния бита. Если он в нулевом состоянии, то итог операции — единица и наоборот. Всё предельно просто.

Эти 4 логические операции следует запомнить в первую очередь, т. к. с их помощью можно получить практически любой возможный результат. Также существуют такие операции, как > (побитовый сдвиг вправо).

Чем отличается логическое ИЛИ от исключающее ИЛИ?

В целом это можно описать следующими таблицами истинности:

Таблица истинности для логического ИЛИ:
A B A or B
0 0 0
0 1 1
1 0 1
1 1 1

Таблица истинности для исключающего ИЛИ:
A B A xor B
0 0 0
0 1 1
1 0 1
1 1 0

Если на пальцах объяснять, то логическое ИЛИ будет истиной, когда хотя бы один из операндов — истина. Исключающее ИЛИ будет истиной, если операнды не равны, и ложью, если операнды равны.

Уроки 21 — 24
Логика и компьютер. Логические операции. Диаграммы Эйлера-Венна
§18. Логика и компьютер. §19. Логические операции. §20. Диаграммы

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

Рис. 3.6

Рис. 3.6

Операции «исключающее ИЛИ» соответствует русская пословица «Либо пан, либо пропал», где выполнение обоих условий одновременно невозможно. Операция «исключающее ИЛИ» в алгебре логики обозначается знаком ⊕, в языке Паскаль — хоr (А хоr В), а в языке Си — знаком ^ (А ^ В). Эту операцию можно представить через базовые операции (НЕ, И, ИЛИ) следующим образом:

А ⊕ В = А • В + А • В .

Пока мы не можем вывести это равенство, но можем доказать его (или опровергнуть, т. е. доказать, что оно неверное). Для этого достаточно для всех возможных комбинаций А и В вычислить значения выражения, стоящего в правой части равенства, и сравнить их со значениями выражения А ⊕ В для тех же исходных данных. Поскольку провести такие вычисления в уме достаточно сложно, сначала вычислим значения А , В , А • В и А • В , а потом уже А • В + А • В . В таблице истинности появятся дополнительные столбцы для промежуточных результатов (рис. 3.7).

Рис. 3.7

Рис. 3.7

Легко видеть, что выражение А • В + А • В совпадает с А ⊕ В для всех комбинаций значений. Это значит, что равенство доказано.

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

А ⊕ В = (А + В) mod 2.

Здесь mod обозначает операцию взятия остатка от деления. Из таблицы истинности видно, что А ⊕ В = 1 тогда и только тогда, когда А ≠ В.

Операция «исключающее ИЛИ» обладает интересными свойствами. По таблице истинности несложно проверить, что

А ⊕ 0 = А, А ⊕ 1 = А , А ⊕ А = 0.

Для доказательства этих равенств можно просто подставить в них А = 0 и А = 1. Теперь докажем, что

(А ⊕ В) ⊕ В = А. (1)

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

Формулу (1) можно использовать для шифрования данных. Пусть А и В — двоичные коды одинаковой длины. Чтобы зашифровать данные (А), используя ключ В, надо применить операцию «исключающее ИЛИ» отдельно для каждого разряда А и В. Для расшифровки ещё раз применяется «исключающее ИЛИ» с тем же ключом В. Нужно отметить, что такой метод шифрования очень нестойкий: для достаточно длинных текстов его легко «взломать» частотным анализом.

Следующая страница Импликация

Cкачать материалы урока

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

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

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

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

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

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

		$~a \oplus b$

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

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

если
a =
b =
то
a ^ b =

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

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

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

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

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

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

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

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

См. также

Битовые операции
Деление по модулю
Алгоритм обмена при помощи исключающего ИЛИ

Wikimedia Foundation . 2010 .