Вступление

В математике обычное ИЛИ (включающее, OR) встречается гораздо чаще исключающего (также называемого XOR).

Например, когда Вы пишете выражение pVq, которое читается ”p ИЛИ q”, это так называемое включающее ИЛИ. В этом случае это выражение ИСТИНА (true), если p = ИСТИНА или q = ИСТИНА, или и p = ИСТИНА и q = ИСТИНА.

Включающее ИЛИ используется в обычном понимании операции ИЛИ (OR), оно используется чаще в логике, нежели исключающее ИЛИ (XOR).

Зачастую мы используем логику исключающего ИЛИ в предложениях. Например, если человек говорит: «Этим летом я поеду в Лондон или в Париж», он таким образом говорит нам, что хочет поехать либо в Лондон, либо в Париж, но не в оба. Даже если его заявление не кажется нам неверным,если он съездит в оба эти города, скорее всего иметься в ввиду будет поездка только в один из этих городов.

 

Вы можете подумать, что XOR не является интересным оператором. Он похож на OR, почему он должен быть интереснее чем OR?

Но это так.

Сначала приведём таблицу истинности операции XOR для булевых переменных:

• • • • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

      • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

    • • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

      • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

  • • • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

      • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

    • • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

      • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

• • • • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

      • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

    • • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

      • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

  • • • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

      • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

    • • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

      • • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

        • x	y	x(+)y
          false	false	false
          true	false	true
          false	true	true
          true	true	false

 

 

Различные видения XOR

Мы можем увидеть XOR с различных сторон.

Предположим, что p и q — булевы переменные (переменные, которые могут принимать два взаимоисключающих значения (0 или 1, либо ИСТИНА И НЕИСТИНА, либо true и false)).

Также предположим, что p₁, p₂, p₃ … p_n – булевы переменные.

Обозначим (+) операцию XOR (обозначается плюсом в кружочке). Тут мы имеем ввиду операцию XOR над булевыми переменными,а не побитовую операцию XOR, речь о побитовой XOR пойдёт немного дальше.

Для операций над булевыми переменными мы увидим, что:

• p(+)q = true, если ТОЛЬКО ОДНА из переменных p и q равна true, это общепринятое определение XOR;

• p₁(+)p₂(+)...(+)p_n = true, если число переменных со значением true является нечётным, или равно false, если число переменных со значением true окажется чётным. Это как бы новое видение XOR, но еасли считать XOR ассоциативной операцией, то это является расширением предыдущего свойства.

• p₁(+)p₂(+)...(+)p_n это тоже самое как сложение по модулю 2. Т.е. Если трактовать, что true == 1, а false == 0, то:

p₁ (+) p₂(+) ... (+) p_n == ( p₁ + p₂ + ... + p_n ) % 2

Таким образом, применение XOR к булевым переменным эквивалентно представлению true=1, false =0, суммированию всех переменных и делению по модулю 2. Напомним, что деление по модулю 2 является одним из способов, чтобы определить, является ли число четным или нечетным. Сумма показывает сколько переменных имело значение 1.

Контроль чётности

Люди часто используют XOR в качестве инструмента контроля четности. Битовая строка является чётной, если содержит количество чисел 1, и является нечётной если количество единиц нечётное. Если вы выполните операцию XOR над всеми битами в строке, то можете сказать является строка чётной или нечётной.

Это может быть использовано для контроля передачи данных через сеть, когда передаваемые данные могут быть повреждены.

Например, Вы отсылаете N байт через сеть от источника к приёмнику. Как Вы можете определить, когда байты были переданы корректно? Один из путей — использование разновидности вычисления контрольной суммы с использованием XOR. Каждый байт может быть записан побитно как b₇b₆...b₀. Для каждого байта «ксорятся» биты в определённой позиции b_i.

Если число предаваемых байт N было равно 10, тогда последовательность дополняется 11-м байтом, в котором биты b_i получены с помощью операции XOR над i-ми битами всех 10-и байтов посылки. Этот одиннадцатый байт называется контрольной суммой (checksum). Контрольная сумма также отсылается через сеть. На приёмном конце, куда приходят данные Вы можете независимо выполнить вычисление контрольной суммы и сравнить её с переданным значением. Если значения совпали, то это значит, что данные были переданы верно, если не совпали — нужно передавать их заново. Очевидно, что такая система может иметь ошибки. Например, если два бита было перевёрнуто, скажем бит с номером 3 байтов 4-го и 5-го, то контрольная сумма будет такой же, как если бы данные не были повреждены. Тем не менее такая система позволяет отлавливать некоторые ошибки передачи.

 

Свойства XOR

Несколько свойств для обычного XOR над булевыми переменными и побитового XOR.

• x (+) 0 = x

“Ксоринг” с нулём даёт изначальное значение.

• x (+) 1 = \x

«Ксоринг» булевых переменных с единицей приводит к их инверсии (0 меняется на 1, а 1 на 0). В случае побитового XOR: x ^ ~0 = ~x, т. е. если переменную «проксорить» с числом,у которого все биты равны 1, но получим бит-инвертированное число.

• x (+) x = 0

Операция XOR между двумя одинаковыми переменными x даст 0. Это так, потому что x побитово состоит из нулей и единиц, а 0 (+) 0 = 0 как и 1 (+) 1 = 0.

• XOR ассоциативен, таким образом (x (+) y) (+) z = x (+) (y (+) z).

Вы можете проверить это, используя таблицу истинности.

• XOR коммутативен, т. е. x (+) y = y (+) x.

Вы также можете это проверить, используя таблицу истинности.

 

Побитовый XOR

Свойства XOR для булевых переменных распространяются на побитовый XOR. Пусть x и y — 32-х битные слова. Тогда они представимы массивами битов длиной 32 каждый, и операция XOR над числами x и y будет соответствовать параллельному побитовому XOR-у между соответствующими битами этих переменных.

 

Обмен значениями двух переменных без использования промежуточной

Это одна из головоломок, которую можно подкинуть другу. Обычно для обмена значениями двух переменных используется промежуточная переменная. Вот как это выглядит на Си:

temp = x ;

x = y ;

y = temp ;

 

Для обмена мы заводим переменную temp. Естественно, переменная не должна обязательно называться temp, тем не менее какая-нибудь промежуточная промежуточная переменная потребуется. Спросите друга, как решить эту задачу без использования «лишней» переменной. Т.е. если использовать только две переменные x и y. Как вы могли догадаться, это возможно с использованием операции XOR. Вы можете попробовать догадаться сами каким образом это делается. Ответ ниже:

x = x ^ y ;

y = x ^ y ;

x = x ^ y ;

Вы поняли как это работает? Возможно, нет. Давайте удостоверимся, что это работает.

Ключ к разгадке — отслеживать изменения значений x и y на каждом шаге.

Пусть исходное значение x равно A (изначальное значение перед выполнением этих трёх строк кода), условимся также, что исходное значение переменой y равно B.

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

// x == A, y == B

x = x ^ y ;

// x == A ^ B, y == B

y = x ^ y ;

// x == A ^ B

// y == (A ^ B) ^ B == A ^ (B ^ B) (согласно ассоциативному закону)

// == A ^ 0 (так как z ^ z == 0)

// == A (так как z ^ 0 == z)

x = x ^ y ;

// x == ( A ^ B ) ^ A

// == ( A ^ A ) ^ B (ассоциативность+коммутативность)

// == 0 ^ B (т. к. z ^ z == 0)

// == B (т.к. z ^ 0 == z)

// y == A

 

Таким образом, после выполнения второй строчки кода y = A. После выполнения третьей строчки кода x = B.

 

Кроме использования XOR для подобного трюка может быть использована операция вычитания, однако XOR несколько безопаснее, т. к. вычитание может приводить к переполнению, «оборачиванию». Например, если из восьмибитного беззнакового (unsigned) числа 2 вычесть 3, то получится 255.

 

Написание побитового XOR без операции ^

Предположим, что Вы хотите реализовать побитовое XOR, но нельзя использовать оператор ^. Что бы Вы сделали? Используя операции побитовое И (&) и побитовое ИЛИ (|), Вы можете сделать это.

x ^ y == (~x & y) | (x & ~y)

Это стандартное определение побитового XOR из книжки по логике.

 

 

Как видим, операция XOR — очень интересная операция.

 

Вольный перевод этого :)