5 / 63 · Concept

XOR and XNOR: equality, difference and parity

Distinguish two-input XOR from multi-input parity, and explain the limits of error detection.

A gate that asks whether two bits differ

XOR outputs 1 when its two inputs differ; XNOR outputs 1 when they are equal.

a\oplus b=\overline a b+a\overline b,\qquad \overline{a\oplus b}=ab+\overline a\,\overline b

OR and XOR agree for 00, 01 and 10, but differ for 11. The XOR symbol adds a curved line in front of the OR symbol. XNOR also has an output inversion^{Inversion The NOT operation, which changes 0 to 1 and 1 to 0. A bar over an expression applies NOT to the entire expression beneath it. Learn more} bubble.

Compare OR and XOR for 11

XOR · Truth table
a	b	y
0	0	0
0	1	1
1	0	1
1	1	0

With three or more inputs, it does not mean “exactly one”

XOR is associative, so $a\oplus b\oplus c$ can be evaluated in sequence. Its result is 1 when an odd number of inputs are 1. The result for 111 is also 1, so extending “exactly one input is 1” to multiple inputs is incorrect.

A full adder's sum output is this three-input parity^{Parity A value indicating whether the number of 1 bits is odd or even. A parity check detects an odd number of bit errors but can miss an even number.}; cout indicates that at least two inputs are 1. Set the inputs below to 111: sum=1 and cout=1, giving the integer sum $1+2\times1=3$ .

Three inputs: odd parity differs from majority

a + b + cin = sum + 2 × cout

Parity detects particular classes of errors

For data $d_3d_2d_1d_0=1011$ , the even-parity bit is $p=d_3\oplus d_2\oplus d_1\oplus d_0=1$ . XORing the data and p together gives 0. If an odd number of bits flip in transit, the total XOR changes to 1 and detects the error. An even number of flipped bits may go undetected, and a single parity bit cannot identify the error position.

Comparing two bit patterns for equality

To test whether vectors A and B are equal, OR together their bitwise XOR results:

equal=\overline{\bigvee_i(A_i\oplus B_i)}

If even one bit differs, the OR result is 1. Inverting the whole result gives 1 only when every bit agrees. An implementation that XORs all the mismatch bits instead lets two mismatches cancel each other.

Try it yourself

For A=1010 and B=1001, find the XOR bit pattern and equality result. What goes wrong if you reduce the XOR pattern with XOR again to decide “equal”?

Read the explanation

The XOR pattern is 0011 and equality is 0. The two mismatch bits cancel to 0 under XOR reduction, so inverting that result incorrectly reports equality=1. Reduce mismatch bits with OR.