Binary & XOR

Bits, , and Hamming distance — the alphabet of coding theory.

The idea

A bit is a $0$ or a $1$, and a bitstring is a finite sequence of bits. Bitstrings are the alphabet of coding theory, which uses three operations on them throughout.

A bitstring names a number in base two: the rightmost bit counts $1$s, the next counts $2$s, then $4$s, $8$s, doubling to the left, so $1011$ stands for $8 + 0 + 2 + 1$. Since each of $n$ bits takes two values independently, there are $2^{n}$ bitstrings of length $n$.

XOR, written $\oplus$, combines two bits and returns $1$ exactly when they differ: $0 \oplus 0 = 0, \qquad 0 \oplus 1 = 1, \qquad 1 \oplus 0 = 1, \qquad 1 \oplus 1 = 0.$ On two bitstrings of the same length it acts position by position. This table is addition modulo $2$, so $a \oplus a = 0$ for every bitstring $a$: XORing with the same string twice restores the original.

The Hamming distance $d(x, y)$ between two bitstrings of the same length is the number of positions where they differ. Since $x \oplus y$ carries a $1$ in exactly those positions, $d(x, y)$ equals the number of $1$s in $x \oplus y$, called its weight.

Ways to work on it

• Walkthrough. Binary to decimal and back, XOR, and Hamming distance.
• Practice. Random 4-bit pair — XOR and distance.
• Hardest. Three 6-bit strings — compute a b, then a b c, and its weight.

Not sure where to start? Take the ten-question placement test.