оператора XOR

XOR

Да приемем, че р и q са булеви променливи. Също така да предположим, че p1, p2, ... pN са булеви променливи. Нека ^ е оператора XOR.
В този случай, ние предполагаме, че р и q са булеви стойности и се предполага, че ^ е обикновен XOR не побитово XOR. По-късно,  ще го използваме като побитово XOR.
р ^ q е истина, ако точно един от двата операнда p или q е истина. Това е традиционното определение за XOR.
p1 ^ p2 ^ ... ^ pN е истина  ако броят на променливите със стойността истина е нечетно число (и е невярно, ако броят на променливи със стойност истина е четно). Това определение игнорира променливи, на които e присвоено false.
Това може да изглежда странно с оглед на XOR. Все пак, ако смятате, че XOR е асоциативен (той е), това е просто продължение на първото определение на XOR.
Това определение има смисъл, ако прочетете Следващото определение:
p1 ^ p2 ^ ... ^ pN е същото като добавяне на mod 2. Ако Pi е истина, все едно е равно 1, в противен случай го третираме като 0. Тогава, XOR операцията е еквивалентна на:
     p1 ^ p2 ^ ... ^ pN == (p1 + p2 + ... + Pn) % 2
Така, XOR приложен върху куп от булеви променливи, е същото като сумиране на всички стойности на променливите (където истина е 1 и неистина  е 0) и разделяне на mod 2. Спомнете си, че разделянето на mod 2 е един от начините да се определи дали дадено число е четно или нечетно.  Тъй като само променливи, които имат стойност 1 допринасят за сумата, това определя колко променливи имат стойност 1.

Проверка за четност

Хората често използват XOR като средство за правене на Проверка за четност. Един bitstring има нечетен паритет, ако броя на 1-ци в низа е нечетен. Има четен паритет, ако броят на 1-ци е четен. Ако XOR-ваме битовете заедно, можем да кажем дали bitstring има нечетен или четен паритет .
Това често може да се използва за проверка на данните, изпратени през мрежата, където има някаква вероятност, някой бит да се повреди. Например, да предположим, че изпращаме N байта през мрежата от едно място до друго място.
Как може да се определи дали байтовете са изпратени правилно? Единият начин е да се използва един вид контролна сума, която използва XOR. Всеки байт може да бъде написан като b₇b₆...b₀. За всеки байт, XOR-ваме всички битове в позиция b_i.
Ако N е 10, а ние пращаме 10 байта, тогава създаваме 11 байт, където b_i  е XOR е  i^th bit на всички 10 байта. Този 11 байт се нарича контролна сума. Този контролна сума също се изпраща по мрежата.
В края на местоназначението, където се получават данните, може да се извърши независима проверка на контролната сума отново, и да се види, дали новополучената контролна сума съответства на изпратената контролна сума. Ако е така, тогава имате някаква увереност, че няма повредени байтове . Ако сумите не са еднакви, тогава мрежата е повредела някои байт и може да се наложи да изпрати отново данните.
Ясно е, че системата може да има грешки. Например, ако два бита бъдат обърнати, да речем, бит три от байтове 4 и 5, тогава контролна сума би била същата,все едно не са били обърнати, но пак ще има грешки. Въпреки това, тази проверка уловя някои грешки.

Свойства на XOR

Ето няколко полезни свойства на XOR. Това се отнася за обикновен XOR и побитов XOR.
х ^ 0 = x
XOR  с 0 ви дава същито число. По този начин, 0 е идентичността на XOR.

х ^ 1 = ~ x
XOR с 1 дава отрицанието на бита. Отново, това идва от таблицата на истината. За побитово XOR, свойството е  малко по-различно:  x ^ ~ 0 = ~ х. Това е, ако XOR всички с 1, резултатът ще бъде побитово отрицание на х.

х ^ х = 0
XOR х със себе си дава 0. Това е така, защото x е 0 или 1, 0 ^ 0 = 0 и 1 ^ 1 = 0.

XOR е асоциативен.
(х ^ y) ^ z = x ^ (y ^ z).
Можете да проверите това чрез използване на истината таблица.

XOR е комутативен.
х ^ y = y ^ х.
Можете да проверите това чрез използване на истината таблицa.

Побитови XOR

Свойства на XOR се прилагат и за побитово XOR. Да предположим, х и у са 32 битови думи. След това, х ^ y е същато като 32 XOR-а паралелно на масив от 32 булеви.

Размяна на 2 числа без временна променлива

Ето един от тези мозъчни закачки, които можете да дадете на вашите приятели програмисти. Един от класическите проблеми който всеки програмист трябва да бъде в състояние да реши е да се разменят две числа без временна променлива. Ето как изглежда това в C#.
  temp = x ;
  x = y ;
  y = temp ;
За да се разменят се въвежда временна променлива. Името й не трябва да бъде temp,  но въпреки това е допълнителна временна променлива.
Сега да ги разменим без временна променлива.
Как може да се направи това? Ако си мислите "може би мога да използвам побитово XOR", сте прави! Ако сте настроен приключенски, можете да помислите за това как да направите това сами, но ако ли не, отговора е следния.
  х = х ^ y;
  y = x ^ y;
  х = х ^ y;
Как може да се убедим, че това работи?
Ключът е в това да се следи първоначалната стойност на х и у. Нека А да бъде оригиналната стойност на х (това е стойността на x, точно преди тези три реда код). По същия начин, нека B е първоначалната стойност на у.
Ние можем да коментираме всеки ред код, за да видим какво се случва.

   / / x == A, y == B
  х = х ^ 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 свойстото)
  х = х ^ y;
   / / x == (A ^ B) ^ A
   / /   == (A ^ A) ^ B       (от асоциативност ​​/ комутативност)
   / /   == 0 ^ B                 (от z ^ z == 0 свойстото)
   / /   == B                       (от z ^ 0 == Z свойстото)
   / / y == A
След като втората операция е изпълнена, y = A. След третата операция , х = B.
Сега се оказва, че може да направи подобен трик с изваждане вместо XOR. Правейки размени с XOR е малко по-безопасно, отколкото размяна с изваждане, защото изваждане може да предизвика препълване. Въпреки това, обикновено overflow се случва по "добър начин", и израза все още може да работи.

Писане на побитово XOR без ^

Да предположим, че искаме да изпълним побитово XOR, но нямаме ^ оператор. Какво трябва да направим? С побитово AND (&) и побитово OR (|), можем да направим това:
 x ^ y == (~x & y) | (x & ~y)
Това е стандартната дефиниция на XOR, както е описана в логическите книги, отнасящи се за побитови операции .

Обобщение

XOR е интересен оператор. С него можем да направим проверка за паритет и размяна, без временни променливи.

източник :
http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/xor.html