One's and Two's Complement

A memory cell only knows 0 and 1. There is no physical minus sign. So how does a computer store a number like $-25$? The answer is two’s complement, the encoding that virtually every modern CPU (and every C compiler we care about) uses for signed integers. This note explains it from scratch. You only need Binary Number System as background.

The Problem

With $n$ bits we have $2^n$ patterns. If we only ever stored plain binary (called unsigned), every pattern would mean a value from $0$ to $2^n-1$, and negative numbers would be impossible.

Idea: sacrifice the leftmost bit (the MSB) to act as a sign bit, and design a rule so that the remaining bits encode the magnitude of negative values in a clever way.

One’s Complement

The one’s complement of a binary number is obtained by flipping every bit: every 0 becomes 1 and every 1 becomes 0:

$$x+\overline{x}=\underset{n}{\underbrace{11\dots 1}}=2^n-1⟹\overline{x}=(2^n-1)-x$$

Legend: what each symbol means

Symbol	Meaning
$x$	Some number, written as an $n$-bit pattern
$\overline{x}$	The pattern $x$ with every bit flipped. This bar is the standard math symbol for “the flip of”. So $\overline{x}$ is the one’s complement
$11\dots 1$	The all-ones pattern ($n$ ones in a row)
$2^n-1$	The value of all-ones, from the “all ones trick” in Binary Number System > Counting and the All Ones Trick
$⟹$	”which means” / “therefore”: the right part follows from the left part

Why the equation is true, in words: a bit and its flip always add up to 1 (0+1 = 1, 1+0 = 1). So column by column, $x$ plus its flip gives 1 in every position, the all-ones pattern. Rearranging that fact (“take $x$ away from all-ones”) gives the right-hand side: the flip of $x$ equals $(2^n-1)-x$.

Check it with numbers

$x=25$, $n=8$: flipping the bits should give the same answer as subtracting:

$$\overline{25}=(2^8-1)-25=255-25=230=11100110_2$$

And indeed 0001 1001 flipped bit-by-bit is 1110 0110. ✓ Both roads lead to the same pattern.

One's complement of 25

 +25:   0001 1001
 flip:  1110 0110   ← one's complement

Historically, “negative $x$” was stored as the one’s complement of $x$. But this has an ugly flaw: it produces two zeros.

 +0:   0000 0000
 -0:   1111 1111   ← same value, different pattern!

Two patterns for zero wastes one pattern, forces hardware to special-case zero, and makes arithmetic awkward. This is why nobody uses it in practice. Instead we take one more step.

Two’s Complement

The two’s complement of $x$ is its one’s complement plus one:

$$-x\equiv 2^n-x(\mathrm{mod}{2}^n)$$

Legend: what each symbol means

Symbol	Meaning
$-x$	The $n$-bit pattern we use to represent the negative of $x$ (not a new pattern, a reinterpretation)
$\equiv$	“is the same thing as”
$2^n-x$	The subtraction: subtract $x$ from the total pattern count $2^n$
$(\mathrm{mod}{2}^n)$	“modulo $2^n$”: if the result needs more than $n$ bits, throw the extra bits away. With only $n$ bits there are just $2^n$ patterns, so anything past $2^n$ wraps around, like a clock: 13 o’clock is 1 o’clock

In words: to negate $x$, compute $2^n-x$. The wrap-around rule is what makes this legal. The pattern for $2^n-x$ and the pattern we call $-x$ are the same $n$-bit object.

Check it with numbers

$x=25$, $n=8$:

$$-25\to 2^8-25=256-25=231=11100111_2=0xE7$$

Same pattern as the flip-and-add-1 recipe below. Subtracting from $2^n$ and “flip then add 1” are two routes to the same destination.

Recipe to negate a number

1. Write the number in binary (positive, plain binary).
2. Flip every bit → one’s complement.
3. Add 1 → two’s complement.

Worked example: store $-25$ in one byte

Step 1: magnitude in binary

$$25=16+8+1=2^4+2^3+2^0=00011001_2$$

Step 2: one’s complement (flip all bits)

 0001 1001  →  1110 0110

Step 3: add 1

   1110 0110
 +         1
 -----------
   1110 0111   ← two's complement of 25

So $-25$ is stored as 1110 0111, which in hex is 0xE7.

The recipe also works in reverse. Flipping the bits of 1110 0111 and adding 1 gives back 0001 1001 ($+25$). Negation is its own inverse.

Reading a stored byte back

Given a pattern, how do we know which number it represents?

• MSB = 0: the number is non-negative. Just read it as plain binary.
• MSB = 1: the number is negative. Its value is $\text{pattern}-2^n$.

In one formula, for an $n$-bit pattern $b_{n-1}{b}_{n-2}\dots b_1{b}_0$:

$$v=-b_{n-1}\cdot 2^{n-1}+\sum _{i=0}^{n-2}{b}_i\cdot 2^i$$

Legend: what each symbol means

Symbol	Meaning
$v$	The signed value the pattern represents
$b_{n-1}$	The MSB (leftmost bit), the sign bit
$-b_{n-1}\cdot 2^{n-1}$	The MSB’s column, counted as negative. If the sign bit is 0 this term is $0$; if it’s 1 it contributes $-2^{n-1}$
$b_i\cdot 2^i$	Every other column, the ordinary “bit times its weight” from Binary Number System > Key Formulas, all positive
${\sum }_{i=0}^{n-2}$	”add up all those ordinary columns”, from position 0 to $n-2$ (everything except the sign bit)

In words: read the pattern exactly like plain binary, except the leftmost column has a minus sign in front of it.

Reading 1110 0111 back, column by column

$$v=\underset{-128}{\underbrace{-1\cdot 2^7}}+\underset{64}{\underbrace{1\cdot 2^6}}+\underset{32}{\underbrace{1\cdot 2^5}}+0+0+\underset{4}{\underbrace{1\cdot 2^2}}+\underset{2}{\underbrace{1\cdot 2^1}}+\underset{1}{\underbrace{1\cdot 2^0}}$$ $$v=-128+64+32+4+2+1=-25$$

Same answer as the shortcut “MSB is 1, so subtract $2^8$”: $231-256=-25$. Exactly the $-25$ we stored.

Why Computers Use Two’s Complement

1. Only one zero. 0000 0000 is the only zero, so no pattern is wasted.
2. Subtraction becomes addition. $a-b$ can be computed as $a+(-b)$ using the same adder circuit the CPU already has, so no separate subtractor is needed.
3. No exceptions. Adding works identically whether the operands are positive or negative (any carry out of the MSB is simply discarded).

   25:  0001 1001      (0x19)
 + -25:  1110 0111      (0xE7)
  -----------------  ┐
        1 0000 0000   ┘ discard the 9th bit
   =      0000 0000   = 0 ✓

Extremes Worth Memorizing

Working these out with the recipe makes the signed range intuitive:

Value	Pattern (byte)	Hex	Why
$-1$	1111 1111	0xFF	All magnitude bits set, the “last” step before wrapping to 0
$-128$	1000 0000	0x80	Sign bit set, all magnitude bits zero, the most negative byte
$+127$	0111 1111	0x7F	Sign bit clear, all magnitude bits set, the largest positive byte

$$-128:10000000_2-2^8=128-256=-128$$

Legend: the pattern 1000 0000 read as plain binary is $128$. Since its MSB is 1 we subtract $2^8=256$ (the “reading it back” rule), and $128-256=-128$. This is why all-zeros-magnitude lands at the most negative value, not at zero.

Key Formulas

Operation	Formula (for $n$ bits)	In plain words
Negate $x$	$2^n-x$	Subtract $x$ from the total pattern count. Any overflow past $n$ bits wraps away
One’s complement	$(2^n-1)-x$	Subtract $x$ from all-ones, which is the same as flipping every bit
Value of a pattern	$-b_{n-1}\cdot 2^{n-1}+{\sum }_{i=0}^{n-2}{b}_i\cdot 2^i$	Read it like plain binary, but the leftmost column counts negative
Signed range	$-2^{n-1}$ to $2^{n-1}-1$	Half the patterns go to $0\cdots +2^{n-1}-1$, the other half to $-1\cdots -2^{n-1}$
Unsigned range	$0$ to $2^n-1$	All $2^n$ patterns used as plain binary magnitudes

Related: Char Data Type shows these formulas in action on the char data type.