# 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.

\begin{equation} p\oplus q = (p \lor q) \wedge \lnot(p \wedge q) \end{equation}## 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 return to_return

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 return to_return

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