# XOR

Exclusive OR, or XOR, is a logical operator that evaluates to True when either but not both of its operands are True. XOR is usually denoted with the ⊕ symbol.

The XOR truth table is

p q p ⊕ q
False False False
False True True
True False True
True True False

XOR may be expressed with AND ($$\wedge$$), OR ($$\lor$$), and NOT ($$\lnot$$) as the following.

$$p\oplus q = (p \lor q) \wedge \lnot(p \wedge q)$$

## Computer Science

C, Python, and many other programming languages use ^ for the bitwise XOR.

a b a ^ b
0 0 0
0 1 1
1 0 1
1 1 0

XOR is often used in cryptography. One-time pad and AES use XOR.

### Single Number

Suppose an array of numbers has every element repeated twice except one. XOR can easily find the non-repeated number.

def find_single_number(numbers):
to_return = 0
for number in numbers:
to_return ^= numbers


This algorithm follows from the fact that n ^ n = 0, n ^ 0 = n, and XOR is commutative and associative. For example:

[2, 5, 2, 3, 5]  # only 3 isn't repeated.

0 ^ 2 ^ 5 ^ 2 ^ 3 ^ 5
= 0 ^ (2 ^ 2) ^ (5 ^ 5) ^ 3
= 0 ^ 0 ^ 0 ^ 3
= 3


### Missing Number

Suppose an array contains $$n$$ distinct numbers taken from 0, 1, 2, ..., n and we'd like to find the missing number. XOR can be used to 'cancel-out' numbers until we are left with the missing number.

def find_missing_number(numbers):
to_return = len(numbers)
for index, number in enumerate(numbers):
to_return ^= number ^ index


This algorithm follows from the fact that n ^ n = 0, n ^ 0 = n, and XOR is commutative and associative. For example:

[3, 2, 5, 1, 0]  # 4 is missing from the sequence

5 ^ (0 ^ 3) ^ (1 ^ 2) ^ (2 ^ 5) ^ (3 ^ 1) ^ (4 ^ 0)
= (0 ^ 0) ^ (1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 3) ^ 4 ^ (5 ^ 5)
= 0 ^ 0 ^ 0 ^ 0 ^ 4 ^ 0
= 4


### Swap

XOR may be used to swap numbers without using extra memory.

def swap(a, b):
a ^= b
b ^= a
a ^= b
return a, b