Exclusive Disjunction

The exclusive disjunction or XOR of two operands is true when exactly one of them is true. Equivalently, true when the operands are different.

Image: XOR gate symbol, Public domain — exclusive-OR gate (ANSI/IEEE symbol).

$X$	$Y$	$X\oplus Y$
0	0	0
0	1	1
1	0	1
1	1	0

For more than two operands, XOR is true when an odd number of operands are true. That’s why it’s also called “parity”: $x_1\oplus x_2\oplus \dots \oplus x_n=1$ exactly when an odd number of the $x_i$ are $1$.

XOR is the negation of XNOR: same input pattern, complemented output. The corresponding hardware element is the XOR gate.

Where it shows up

XOR is the workhorse of binary arithmetic. The sum bit of a Half-adder is $A\oplus B$, exactly the XOR truth table. The sum bit of a Full-adder extends to $A\oplus B\oplus C_{in}$, again pure XOR.

XOR also appears whenever you want a controlled inverter: $X\oplus 1=\overline{X}$, but $X\oplus 0=X$. That’s how a 2’s-complement adder/subtractor uses XOR gates to optionally complement the second operand based on a Sub control bit.

Notation and identities

Symbol in electronics is $\oplus$. In formal logic, $\nleftrightarrow$ emphasizes XOR being the negation of $\leftrightarrow$.

In SOP form, $X\oplus Y=X\overline{Y}+\overline{X}Y$, true exactly when one variable is set and the other isn’t.

A three-variable identity that comes up in MUX-based logic synthesis:

$x_1(x_2\odot x_3)+\overline{x_1}(x_2\oplus x_3)=x_1\oplus x_2\oplus x_3$

where $\odot$ is the XNOR. The right-hand side is the parity of three variables. The left-hand side is exactly what a 2-to-1 MUX with select $x_1$, data inputs $x_2\odot x_3$ (line 1) and $x_2\oplus x_3$ (line 0) computes. So three-input parity can be built from one XOR + one XNOR + one MUX. Useful when MUXes are cheaper than wide XOR gates (typical in FPGA synthesis).

Useful properties of XOR:

• Self-inverse: $X\oplus X=0$
• Identity for $0$: $X\oplus 0=X$
• Commutative and associative — order doesn’t matter

These make XOR good for one-time-pad-style operations: $X\oplus K\oplus K=X$, so XORing twice with the same key recovers the original.