Computer arithmetic: adders, carry lookahead and multiplication
The full adder with proof, ripple carry, carry lookahead, two's complement subtraction, overflow and flags, multipliers.
The arithmetic logic unit does its sums with logic gates. In Foundations of Computer Science we saw how numbers are represented in binary and in two’s complement; here we see how hardware adds, subtracts, detects errors and multiplies, and why the way carries propagate decides a processor’s speed.
The full adder
Adding two binary numbers column by column requires, for each bit, adding three digits: the two bits 
and 
and the carry 
from the previous column. The result is a sum bit 
and a carry 
for the next column.
Theorem.
![\[ S = A \oplus B \oplus C_{in},\qquad C_{out} = AB + C_{in}(A \oplus B) \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-c502b6f8f1a0d4e1f911e4bc5e463b1b_l3.png "Rendered by QuickLaTeX.com")
Proof. Check it on the truth table of the eight combinations. is 1 when the number of inputs at 1 is odd (1 or 3), which is the definition of the exclusive OR of three bits. is 1 when at least two inputs are 1: either and both are (
), or exactly one of them is (
) and is too. The two cases are disjoint and cover every possibility. ∎
Carry propagation
Placing 
full adders in a row, with each carry output connected to the next carry input, gives the ripple-carry adder. It is simple, but slow: the most significant bit is not valid until the carry has travelled the whole chain. If each stage adds a delay of two gates, a 64-bit adder accumulates 128, far too many for a processor running at a few gigahertz.
Carry lookahead
For each column two signals are defined that depend only on 
and 
:
![\[ g_i = A_iB_i\ \ \text{(generate)},\qquad p_i = A_i \oplus B_i\ \ \text{(propagate)} \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-16ef3c4a5df3c87654657ccf746ab037_l3.png "Rendered by QuickLaTeX.com")
The column generates a carry on its own if both bits are 1; it propagates the incoming one if exactly one is 1. So 
, and substituting:
![\[ c_2 = g_1 + p_1g_0 + p_1p_0c_0,\qquad c_3 = g_2 + p_2g_1 + p_2p_1g_0 + p_2p_1p_0c_0 \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-2a465c06c79c30c86c75b2b733778722_l3.png "Rendered by QuickLaTeX.com")
Each carry is computed directly from the inputs, with two levels of gates, without waiting for the previous ones. The gates become very wide as grows, so one works in groups of 4 bits and repeats the idea hierarchically: the delay grows as 
instead of . The adders of modern processors are variants of this idea (prefix adders, such as Kogge-Stone).
Subtraction and overflow
In two’s complement, 
is obtained by inverting all bits and adding 1. So
![\[ A - B = A + \overline{B} + 1 \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-f003a7f52b4fb2597d548ea787c8d30e_l3.png "Rendered by QuickLaTeX.com")
and the same adder also subtracts: just put XOR gates on the inputs (to invert them when needed) and set the initial carry 
to 1. This is one reason two’s complement has displaced every other representation of negative numbers.
Overflow. Adding two numbers of the same sign, the result can fall outside the representable range: with 8 bits, 
exceeds 127 and appears as −56. It is recognised because the sign of the result differs from that of both addends; in hardware, equivalently, the carry into the most significant bit differs from the carry out of it: 
.
The ALU reports the outcome of operations with a few status bits, the flags: Z (zero result), N (negative), C (carry, useful for unsigned numbers), V (overflow, for signed ones). The conditional branches of architectures that use them rely on these bits.
Multiplication
Binary multiplication is simpler than decimal: each partial product is either the multiplicand or zero, depending on the multiplier bit, shifted to the corresponding position. The partial products are then added.
- The slowest method, shift and add, uses a single adder for cycles.
- Tree multipliers add all partial products together with adders arranged in a tree (Wallace trees), and multiply two 64-bit numbers in a few clock cycles.
Division is harder and is done with iterative algorithms producing one or more quotient digits per cycle: that is why, in speed-critical programs, compilers replace divisions by constants with multiplications and shifts. Floating-point numbers (IEEE 754 standard, Numerical Analysis lesson) have a dedicated unit, which aligns the exponents, operates on the mantissas and normalises the result.
