Adding Numbers with Logic Gates

A computer adds two numbers one bit at a time, the way you add digits by hand, carrying when a column overflows. Each column is a full adder built from logic gates: the sum bit is an exclusive or, and the carry comes from AND and OR.

How it works

Boolean algebra: XOR, AND and the full adder

In one sentence

A full adder computes $s = a \oplus b \oplus c_{\text{in}}$ and $c_{\text{out}} = ab \vee c_{\text{in}}(a \oplus b)$ , the majority of its three inputs. A ripple-carry adder of $n$ full adders computes the $n$ -bit sum with carries $c_{i+1} = \lfloor (a_i + b_i + c_i)/2 \rfloor$ .

General formula

{\htmlData{sym=0}{s_i}} = {\htmlData{sym=1}{a_i}} \oplus {\htmlData{sym=2}{b_i}} \oplus {\htmlData{sym=3}{c_i}}, \qquad {\htmlData{sym=4}{c_{i+1}}} = {\htmlData{sym=1}{a_i}}{\htmlData{sym=2}{b_i}} + {\htmlData{sym=3}{c_i}}\,({\htmlData{sym=1}{a_i}} \oplus {\htmlData{sym=2}{b_i}})

It's grade-school addition in base 2: each column's digit is the column sum mod 2, and the carry is the column sum divided by 2.

What the symbols mean

$s_i$
Sum bit
The output bit in column i.
$a_i$
First input bit
Column i of the first number.
$b_i$
Second input bit
Column i of the second number.
$c_i$
Carry in
The carry arriving from the column to the right.
$c_{i+1}$
Carry out
The carry passed to the next column on the left.

Write each number in binary. Adding column by column from the right, each column adds two bits plus the carry from the column before.
The column's sum bit is 1 when an odd number of its three inputs are 1: $s = a \oplus b \oplus c$ .
It carries a 1 to the next column when at least two inputs are 1: $c_{\text{out}} = ab + c\,(a \oplus b)$ , built from AND, OR and XOR gates.
Chaining four full adders adds 4-bit numbers (a ripple-carry adder), and a fifth output bit catches overflow. Real processors chain 64 and compute the carries faster with lookahead logic.

Learn the math

Statements and ConnectivesDiscrete · Lesson 1, Logic Boolean Algebra and Logic GatesDiscrete · Lesson 5, Logic Binary and HexadecimalDiscrete · Lesson 29, The Math Inside Computers Negative Numbers: Two's ComplementDiscrete · Lesson 30, The Math Inside Computers Bitwise Operations and MasksDiscrete · Lesson 31, The Math Inside Computers

Learn the math

Statements and ConnectivesDiscrete · Lesson 1, Logic

Boolean Algebra and Logic GatesDiscrete · Lesson 5, Logic

Binary and HexadecimalDiscrete · Lesson 29, The Math Inside Computers

Negative Numbers: Two's ComplementDiscrete · Lesson 30, The Math Inside Computers

Bitwise Operations and MasksDiscrete · Lesson 31, The Math Inside Computers