Two's Complement Integers

A two's complement representation with $n$ bits assigns to each bit pattern $b_{n-1}b_{n-2}\cdots b_1b_0$ the integer value

Every bit contributes its ordinary positive binary weight except the most significant bit (MSB), called the sign bit, which contributes a negative weight $-2^{n-1}$. This single sign-flip on one weight is the entire definition — everything else in this article is a consequence of that formula. Two important ranges follow immediately. With $n$ bits, the representable values run from $-2^{n-1}$ (pattern $1000\ldots0$) to $2^{n-1}-1$ (pattern $0111\ldots1$). Unlike sign-magnitude encoding, there is exactly one representation of zero ($000\ldots0$), which removes an entire class of hardware special cases. This asymmetric range — one more negative number than positive — is the price paid for that convenience, and it is the source of the single dangerous edge case discussed later. The encoding is equivalent to arithmetic modulo $2^n$: an $n$-bit two's complement pattern represents the unique integer in $[-2^{n-1}, 2^{n-1}-1]$ that is congruent, mod $2^n$, to the pattern's unsigned binary value. This modular view is what justifies every hardware shortcut in the rest of the article: addition circuits can add bit patterns as if they were unsigned, because unsigned addition mod $2^n$ and signed addition mod $2^n$ are literally the same operation on the same bits — only the interpretation of the result differs.

Reading a two's complement number. Apply the weighted-sum formula directly. For $n=8$, the pattern `11111011` is

Negation ("two's complement" the verb). To negate a value $x$, invert every bit (forming the one's complement, $\bar{x} = 2^n - 1 - x$) and add 1:

Why this works: for any $n$-bit pattern $x$, its bitwise complement $\bar x$ satisfies $x + \bar x = 2^n - 1$ (each bit pair $b, \bar b$ sums to 1, contributing $2^i$ at every position). Adding 1 to both sides gives $x + (\bar x + 1) = 2^n \equiv 0 \pmod {2^n}$. So $\bar x + 1$ is, by definition, the additive inverse of $x$ modulo $2^n$ — exactly the negation we want under the modular interpretation above.

Subtraction via negation. Since $a - b = a + (-b)$, a subtractor is built from an adder plus a negation: compute $\bar b + 1$, then add to $a$. In hardware this is even cheaper: feed $b$ through inverters and set the adder's initial carry-in to 1, which supplies the "+1" for free while the inverters supply $\bar b$.

Sign extension. To widen an $n$-bit two's complement value to $m > n$ bits without changing its numeric value, replicate the sign bit into all new high-order positions:

Why this works: if $b_{n-1}=0$ (non-negative), the value is unchanged because leading zeros never change a binary value. If $b_{n-1}=1$, the old sign weight was $-2^{n-1}$; replicating $k$ extra 1-bits and moving the sign bit to position $m-1$ changes the total weight of the "1" bits from $-2^{n-1}$ to

a telescoping geometric sum that exactly reproduces the original sign weight. So the value is preserved either way.

Overflow detection. When adding two $n$-bit two's complement numbers, let $c_{n-1}$ be the carry into the sign bit position and $c_n$ be the carry out of it. Overflow occurs exactly when

Equivalently: overflow happens if and only if two operands with the same sign produce a result with the opposite sign (adding two positives can't overflow to a negative unless it wrapped; adding two numbers of different sign can never overflow, since the true sum lies between them). ``` // Two's complement core operations, n-bit words function VALUE(bits[0..n-1]): // bits[n-1] is sign bit v = -bits[n-1] 2^(n-1) for i in 0 .. n-2: v = v + bits[i] 2^i return v function NEGATE(bits[0..n-1]): for i in 0 .. n-1: bits[i] = NOT bits[i] // one's complement return ADD(bits, ONE) // add 1, mod 2^n function ADD(a[0..n-1], b[0..n-1]): carry = 0 for i in 0 .. n-1: sum_i = a[i] XOR b[i] XOR carry carry = (a[i] AND b[i]) OR (carry AND (a[i] XOR b[i])) result[i] = sum_i carry_out = carry // carry out of MSB, c_n return result, carry_out function SUBTRACT(a[0..n-1], b[0..n-1]): return ADD(a, NEGATE(b)) function ADD_WITH_OVERFLOW(a[0..n-1], b[0..n-1]): // track carry into MSB (c_{n-1}) and carry out of MSB (c_n) carry = 0 for i in 0 .. n-2: result[i] = a[i] XOR b[i] XOR carry carry = (a[i] AND b[i]) OR (carry AND (a[i] XOR b[i])) carry_into_msb = carry // c_{n-1} result[n-1] = a[n-1] XOR b[n-1] XOR carry_into_msb carry_out_msb = (a[n-1] AND b[n-1]) OR (carry_into_msb AND (a[n-1] XOR b[n-1])) // c_n overflow = (carry_into_msb XOR carry_out_msb) return result, overflow function SIGN_EXTEND(bits[0..n-1], m): // widen n bits to m > n bits new_bits = array of size m for i in 0 .. n-1: new_bits[i] = bits[i] for i in n .. m-1: new_bits[i] = bits[n-1] // replicate sign bit return new_bits ```

Time and space. Reading, negating, or adding an $n$-bit two's complement number takes $O(n)$ time on a bit-serial model (each bit is touched a constant number of times) and $O(n)$ space to store. In real hardware this $O(n)$ chain of carries is exactly the Ripple-Carry Adder's critical path, which is why faster adder designs (carry-lookahead, carry-select) exist — they reduce the depth of this dependency chain without changing the asymptotic bit count. Sign extension is $O(m-n)$ to fill the new positions — strictly speaking $O(1)$ additional hardware, since every new wire is simply tied to the same sign-bit wire, no computation required. Overflow detection is $O(1)$ given the two carry bits already produced by the adder — it is literally a single XOR gate.

Correctness of negation. This was proven above: $x + \bar x = 2^n - 1$ for any $n$-bit pattern (each of the $n$ bit-pairs contributes exactly $2^i$ to the sum, since $b_i + \bar b_i = 1$), so $\bar x + 1 \equiv -x \pmod{2^n}$. This is not a heuristic — it is an algebraic identity that holds for every bit pattern, including all-zeros ($x=0 \Rightarrow \bar x + 1 = 2^n \equiv 0$, correctly giving $-0=0$) and the boundary pattern discussed in the pitfalls below.

Correctness of unsigned-style addition on signed values. The deep reason two's complement works is that addition mod $2^n$ commutes with the encoding. If $x$ and $y$ are two's complement values represented by bit patterns $X, Y$, then the true sum $x+y$, reduced mod $2^n$ into the range $[-2^{n-1}, 2^{n-1}-1]$, is represented by the bit pattern $(X+Y) \bmod 2^n$ — the same bit pattern an unsigned adder would produce. Formally: the map from bit patterns to residues mod $2^n$ is a ring homomorphism, and two's complement is just a choice of representative (the "balanced" one, $[-2^{n-1}, 2^{n-1}-1]$) instead of the usual unsigned one ($[0, 2^n-1]$) for the same ring $\mathbb{Z}/2^n\mathbb{Z}$. Addition, subtraction, and multiplication in this ring are representative-independent, which is exactly why one adder circuit serves both signed and unsigned interpretations.

Correctness of overflow detection. Overflow means the true mathematical sum falls outside $[-2^{n-1}, 2^{n-1}-1]$ and so cannot be represented. A case analysis on the signs of the operands shows:

• Adding a non-negative and a non-positive number: the true sum lies between the two operands, both already in range, so it cannot overflow. This matches $c_{n-1}=c_n$ always in this case.
• Adding two non-negative numbers: overflow occurs iff the true sum reaches $2^{n-1}$ or more, which happens exactly when a carry is generated out of the sign bit while none was needed in sign-bit addition of two zero sign-bits ($c_{n-1}=0, c_n=1$).
• Adding two negative numbers (both sign bits 1): overflow occurs iff the true sum is less than $-2^{n-1}$, which happens exactly when the sign-bit addition ($1+1+c_{n-1}$) fails to generate a carry out despite two 1s ($c_{n-1}=1$ forces $c_n=1$ always here — the only way to get $c_{n-1}\ne c_n$ is $c_{n-1}=0,c_n=1$, which is exactly the underflow condition).

Working through all four sign combinations confirms $c_{n-1} \oplus c_n$ is true precisely on overflow and false otherwise — this is the standard proof presented in every computer-architecture treatment of the ALU's overflow flag, and it is why the flag costs one gate.

Tradeoffs. Two's complement is optimal for addition-based hardware reuse, but it is not symmetric: negation of the minimum value fails (see pitfalls), and right-shifting a negative number is not the same as dividing by a power of two in the naive sense (arithmetic shift rounds toward $-\infty$, not toward zero). Sign-magnitude, by contrast, negates trivially (flip one bit) but requires separate addition/subtraction logic and has two zeros — a worse tradeoff for hardware, which is precisely why two's complement won.

Compute $19 - 45$ in 8-bit two's complement and verify against ordinary arithmetic ($19-45=-26$).

Adding `00010011` (19) and `11010011` (−45) bit by bit, right to left, tracking carry: ``` 0 0 0 1 0 0 1 1 (19) + 1 1 0 1 0 0 1 1 (-45) ------------------- carry: 0 1 1 1 1 0 1 1 0 (c7 c6 c5 c4 c3 c2 c1 c0, generated right→left) sum : 1 1 1 0 0 1 1 0 ``` Let's carry this out carefully column by column (bit 0 is rightmost):

Result bits, MSB to LSB: `1 1 1 0 0 1 1 0` = `11100110`. Reading via the value formula: $-128 + 64+32+0+0+4+2+0 = -128+102 = -26$. ✓ Matches $19-45=-26$ exactly. Carry into sign bit $c_6 = 0$, carry out of sign bit $c_7 = 0$: they're equal, so no overflow — correct, since $-26$ is well within the 8-bit signed range $[-128,127]$.

A second case that exposes overflow. Compute $100 + 50$ in 8 bits (true answer $150$, which exceeds the 8-bit signed max of $127$): ``` 0 1 1 0 0 1 0 0 (100) + 0 0 1 1 0 0 1 0 (50) ```

Wait — recount carefully with 8 bits, bit 7 as sign: `100 = 01100100`, `50 = 00110010`.

Result: `1 0 0 1 0 1 1 0` = `10010110`. Carry into sign bit $c_6=1$, carry out of sign bit $c_7=0$: they differ, so overflow is correctly flagged. Reading the raw pattern as signed gives $-128+16+4+2=-106$, nonsense as "$100+50$" — exactly the garbage that motivates checking the overflow flag before trusting a signed sum.

Two's complement arithmetic predates electronic computers: mechanical calculating machines used "complement" tricks to turn subtraction into addition on adding machines long before transistors existed. Its formalization for binary electronic computers is closely tied to the design decisions behind the earliest stored-program machines.

Every general-purpose CPU — x86, ARM, RISC-V, MIPS, PowerPC — represents signed integers in two's complement in its registers and memory. The C, C++, Java, and Rust `int` types are defined (or, in practice, universally implemented) using two's complement semantics, including its wraparound behavior on overflow. Compilers rely on two's complement equivalence to translate `a - b` into `a + (~b + 1)`, reusing the same adder hardware described here — the same circuitry inside an Arithmetic Logic Unit handles addition and subtraction as one operation. Sign extension instructions (`sign extend byte`, `movsx`, etc.) exist in every instruction set specifically to implement the sign-replication rule from this article when a smaller signed type is promoted to a wider register. Overflow flags in condition-code registers, used by conditional branches after arithmetic instructions, are computed by exactly the $c_{n-1}\oplus c_n$ rule derived above. Cryptographic and checksum code that deliberately exploits modular wraparound (e.g., hash mixing functions) also depends on the modular-arithmetic identity underlying two's complement.

Ask the tutor: How does the same two's complement circuitry extend to building a full ripple-carry adder and subtractor in hardware?