Signed Number Representation

Unsigned binary encodes only non-negative integers. Processors also need negative values. Three classical encodings place a sign into a fixed-width bit pattern: sign-magnitude, ones' complement, and two's complement. Modern CPUs almost universally use two's complement because addition and subtraction use the same adder hardware and because it has a single zero.

This note fixes the encodings, their ranges, negation rules, and the overflow condition for two's-complement addition. Arithmetic circuits that implement them appear in Adders and Subtractors and Fixed-Point Arithmetic and Overflow.

All statements assume an $n$-bit word. Patterns are written with the MSB on the left. When a signed encoding is in force, the MSB is the sign bit (0 for non-negative, 1 for negative) in every scheme below, but the meaning of the remaining bits differs.

Example ($n = 8$): $-5$ is $10000101$.

Example ($n = 8$): $+5 = 00000101$, so $-5 = 11111010$.

Example ($n = 8$): $-5 = \overline{00000101}+1 = 11111010+1 = 11111011$. Decode: $251 - 256 = -5$.

Weighted-sign view. A two's-complement pattern $b_{n-1}b_{n-2}\ldots b_0$ has value

so the MSB carries weight $-2^{n-1}$ and every other bit its usual positive weight. Example: $1011 = -8 + 2 + 1 = -5$. The same view for ones' complement gives the MSB weight $-(2^{n-1} - 1)$: $1011 = -7 + 3 = -4$.

Shortcut for negation. Scanning from the LSB, copy every bit up to and including the first 1, then invert all bits to its left. For $22 = 0001\,0110$: copy $10$, invert the rest, giving $1110\,1010$.

An $n$-bit excess-$B$ code stores $v$ as the unsigned pattern $v + B$. The usual bias is $B = 2^{n-1}$: in 4-bit excess-8, $0000 = -8$, $1000 = 0$ and $1111 = +7$. Excess-$2^{n-1}$ is two's complement with the MSB inverted, so its patterns sort in the same order as their values. IEEE 754 exponents use a bias of $2^{k-1} - 1$ instead (127 for 8 bits), see Floating-Point Representation (IEEE 754).

Different count: negative values versus patterns with sign bit 1. In every scheme $2^{n-1}$ patterns have MSB 1. In two's complement all of them are negative values; in sign-magnitude and ones' complement one of them is $-0$, so only $2^{n-1} - 1$ distinct negative values exist.

Edge case. Negating $-2^{n-1}$ (the pattern $100\ldots 0$) overflows the representable range: there is no positive counterpart in $n$ bits. Hardware that must reject this case raises an overflow flag on negation.

Add the patterns as unsigned integers mod $2^n$. The same adder works for two positives, two negatives, or mixed signs. Interpretation of the result uses the two's-complement decode rule above.

Example ($n = 4$). $5 + (-3)$: $0101 + 1101 = 0010$ (carry out discarded), value $+2$.

Overflow means the true mathematical sum lies outside the representable range. Equivalently, for two's complement:

Mixed-sign addition never overflows in two's complement, because the magnitude of the sum is at most the larger magnitude, which already fit.

A circuit test: number the carries so that $c_{n-1}$ is the carry into the sign position (out of bit $n-2$) and $c_n$ the carry out of it. Then overflow $V = c_n \oplus c_{n-1}$.

Why the XOR works. Let the sign bits be $a, b$ and the sum bit $s = a \oplus b \oplus c_{n-1}$. If $a = b = 0$, then $c_n = 0$, and overflow (a negative result) happens exactly when $c_{n-1} = 1$. If $a = b = 1$, then $c_n = 1$, and overflow (a non-negative result) happens exactly when $c_{n-1} = 0$. If $a \ne b$, then $c_n = c_{n-1}$ and $V = 0$. In all cases $V = c_n \oplus c_{n-1}$.

The carry flag $C = c_n$ reports unsigned wrap-around; $V$ reports signed overflow. They are independent. In 4 bits:

$A - B$ is computed as $A + \overline{B} + 1$: invert $B$ and set the adder's carry-in to 1. Signed overflow in subtraction happens exactly when $A$ and $B$ have different signs and the result's sign differs from $A$'s.

Two's-complement addition example ($n = 4$). $5+6$: $0101+0110 = 1011$, which decodes as $-5$. Both operands were positive; the result is negative: overflow. Ordinary binary addition does not implement sign-magnitude arithmetic; use the separate sign/magnitude rules there.

Ones' complement. Add the patterns; if a carry leaves the MSB, add it back into the LSB (end-around carry).

Sign-magnitude. If the signs agree, add the magnitudes and keep the sign. If they differ, subtract the smaller magnitude from the larger and take the sign of the larger. This needs a magnitude comparator, which is the reason the scheme is not used for integers.

Pseudocode treats patterns as integers in $0..2^n-1$.

Sign of a pattern is its MSB. Best, average and worst case for these operations on an $n$-bit word are all $\Theta(n)$ gate delays in a ripple implementation, because the circuit is the same whatever the data; see Adders and Subtractors for carry-lookahead.

Two's complement identifies the ring $\mathbb{Z}/2^n\mathbb{Z}$ with signed representatives in $[-2^{n-1}, 2^{n-1}-1]$. Addition mod $2^n$ therefore coincides with signed addition whenever the mathematical sum lies in that interval. When it does not, the representative still exists in the ring, but it is not the mathematical sum: that mismatch is overflow.

Ones' complement addition requires an end-around carry: a carry out of the MSB is added back into the LSB. That extra step is why two's complement replaced it in ALUs.

$22 = 00010110$. Invert $11101001$; add 1 $\to 11101010$. Decode: $234 - 256 = -22$.

$27 = 0001\,1011$. Sign-magnitude sets the MSB: $1001\,1011$. Ones' complement inverts every bit: $1110\,0100$. Two's complement adds 1: $1110\,0101$. Check with the weighted-sign view: $-128 + 64 + 32 + 4 + 1 = -27$.

Unsigned 128; sign-magnitude $-0$; ones' complement $-127$; two's complement $-128$. Negating it in two's complement returns the same pattern ($0111\,1111 + 1 = 1000\,0000$) with $V = 1$.

Common misconceptions.