= Exclusive or toggles and parity
For <bits> $x_1,\ldots,x_n$, repeated <exclusive or> computes the <parity> of the number of ones:
$$
x_1\oplus\cdots\oplus x_n=\left(\sum_{i=1}^n x_i\right)\bmod2.
$$
An <induction> proves this: the first <bit> gives its own <parity>, and appending a zero preserves it while appending a one changes it. The <binary string> $10110$ has three ones, so its <parity bit> is one. Append that <parity bit> to obtain $101101$, whose six <bits> have even <parity>. Flipping the second <bit> produces $111101$ and changes the combined <exclusive or> to one, detecting an error. Flipping the third <bit> as well produces $110101$, with four ones and combined <exclusive or> zero: an even number of flips can escape this check.
For three inputs, repeated <exclusive or> means an odd number of true inputs, rather than exactly one: $1\oplus1\oplus1=1$. The “exactly one” description applies to the two-input <exclusive or>. This distinction matters when translating a requirement that exactly one option be selected into a program condition.
Back to article page
