How do computers add numbers? Binary and logic gates

Computers add numbers in binary, with circuits built from logic gates. Every binary digit is a switch that is on (1) or off (0). An XOR gate and an AND gate, fed the same two bits, add them: XOR gives the sum bit and AND gives the carry. That pair is called a half adder. A full adder also takes in the carry from the column before, and a chain of full adders, one per column, adds whole numbers, passing each carry along like a row of dominoes. In this post we count in binary, add by hand, build each gate from light switches, then write the whole adder in a few lines of Python and watch it add 13 + 11. Then we make it overflow, and meet the 32-bit limit that Gangnam Style's view count reached on YouTube in 2014.

This post goes with letsBug Explains, episode 2. Watch it, or read on: the post adds every truth table, a working adder in Python you can run yourself, the 8-bit overflow and practice questions with answers.

There are no 1s and 0s inside your phone

Myth or fact: somewhere inside your phone there are tiny ones and zeros? Myth. The A17 Pro chip in an iPhone 15 Pro holds about 19 billion transistors, and in a digital circuit a transistor is used as a switch: on or off. There are no digits in there, only switches.

A transistor is a switch with no moving parts. Most logic gates today are made from a kind called the MOSFET. It has a control connection called the gate (nothing to do with the logic gates coming up), and a voltage on the gate controls whether current flows between two other connections, the source and the drain. A chip treats a high voltage as 1 and a low voltage as 0. So 1 and 0 are just our names for on and off. Each 1 or 0 is one bit: a single yes or no.

So how do switches do maths? In two steps: write numbers with switches, then wire the switches together so that the right answer comes out.

Counting in binary

One switch can only count to 1, so we use a row of them and give each place a value, the way ordinary (denary) numbers have hundreds, tens and ones. In binary, each place is worth double the one to its right: 1, 2, 4, 8, 16, and so on.

Number	Binary	Place values used
6	110	4 + 2
7	111	4 + 2 + 1
13	1101	8 + 4 + 1
31	11111	16 + 8 + 4 + 2 + 1

To write 13, take an 8, a 4 and a 1: 8 + 4 + 1 = 13, so 13 in binary is 1101. Try it on one hand: each finger is a switch, worth 1, 2, 4, 8 or 16. All five up is 11111 = 16 + 8 + 4 + 2 + 1 = 31, so one hand counts from 0 all the way to 31.

With n switches, the biggest number is 2ⁿ − 1: 15 with 4 bits, 255 with 8. And 20 bits count past a million (2²⁰ = 1,048,576), the same reason binary search needs at most 20 checks to find one item in a million. Python converts both ways:

print(bin(13))            # 0b1101
print(int("11111", 2))    # 31
print(format(13, "05b"))  # 01101: five fingers
print(2**8 - 1)           # 255: the biggest 8-bit number

Adding in binary: 1 + 1 = 10

Binary addition works just like column addition at school. Start from the right, add each column, and carry into the next one. There are only a few cases:

Column	Total	Write	Carry
0 + 0	0	0	0
0 + 1 or 1 + 0	1	1	0
1 + 1	2 = 10 in binary	0	1
1 + 1 + 1 (with a carry in)	3 = 11 in binary	1	1

The classic slip is writing 1 + 1 = 2. Binary has no digit 2: two is written 10 (one 2 and no 1s). So you write 0 and carry 1, exactly like 9 + 1 in denary: write 0, carry 1.

Worked example: 6 + 7

A small game stores your lives in four bits. You have 6 lives (0110) and pick up 7 more (0111). Let's add them column by column, ones column first:

Column	A + B + carry in	Write	Carry out
1s	0 + 1 + 0	1	0
2s	1 + 1 + 0	0	1
4s	1 + 1 + 1	1	1
8s	0 + 0 + 1	1	0

Read the Write column from the bottom up: 1101. That's 8 + 4 + 1 = 13 lives, and 6 + 7 is 13. It works.

Logic gates: AND, OR and XOR from light switches

To make switches add, we wire them into logic gates. You can build all three gates we need with a battery, a lamp and two switches, A and B (for XOR, two-way switches, the kind used on stairs):

• AND: two switches in series, one after the other. Current can only flow when both switches are closed, so the lamp lights only if A AND B are on.
• OR: two switches in parallel, side by side. The lamp lights when either switch, or both, are closed: A OR B.
• XOR, exclusive OR: the staircase light. You have probably used one. A staircase light has a switch at the bottom and one at the top, and flipping either one changes the light. An XOR gate's output is on when its inputs are different: exactly one of them is on. (Depending on the wiring, the light may be on or off with both switches up, but flipping either one always changes it.)

A, B	A AND B	A OR B	A XOR B
0, 0	0	0	0
0, 1	0	1	1
1, 0	0	1	1
1, 1	1	1	0

Inside a chip the switches are transistors instead of light switches. The logic is the same as the lamp's.

The half adder: XOR for the sum, AND for the carry

Now look back at the adding table and split each answer into two bits: a carry bit and a sum bit.

A + B	In binary	Carry	Sum
0 + 0	0	0	0
0 + 1	1	0	1
1 + 0	1	0	1
1 + 1	10	1	0

The sum bit is 1 when exactly one input is 1. That's the XOR column. The carry bit is 1 only when both inputs are 1. That's the AND column. So one XOR gate and one AND gate, side by side and fed the same two inputs, add two bits. This circuit is called a half adder.

Here it is in Python. On whole numbers, ^ is XOR and & is AND, worked out bit by bit, so on a single 0 or 1 they act exactly like the gates:

def half_adder(a, b):
    """Add two bits. Returns (sum, carry)."""
    return a ^ b, a & b  # XOR gives the sum, AND gives the carry

for a in (0, 1):
    for b in (0, 1):
        s, c = half_adder(a, b)
        print(f"{a} + {b}: carry {c}, sum {s}")

0 + 0: carry 0, sum 0
0 + 1: carry 0, sum 1
1 + 0: carry 0, sum 1
1 + 1: carry 1, sum 0

The half adder doesn't know that 1 + 1 is 2. It has no idea what a number is. The right answer comes from how the two gates are wired.

The full adder: two half adders and an OR gate

A half adder has one problem. In every column after the first, a carry might be coming in, so you're really adding three bits: A, B and the carry in. A full adder does that, and it's built from two half adders and an OR gate:

1. Half adder 1 adds A and B.
2. Half adder 2 adds the carry in to that sum. Its sum is the full adder's sum.
3. If either half adder makes a carry, the OR gate passes it on as the carry out, to the next column.

The two half adders can never both carry: if the first one carries, its sum is 0, and 0 plus the carry in is at most 1. So OR is all we need. Run this after the half adder:

def full_adder(a, b, carry_in):
    """Add three bits. Returns (sum, carry_out)."""
    s1, c1 = half_adder(a, b)         # half adder 1: A + B
    s, c2 = half_adder(s1, carry_in)  # half adder 2: + the carry in
    return s, c1 | c2                 # OR: either carry goes on

for a in (0, 1):
    for b in (0, 1):
        for c in (0, 1):
            s, carry_out = full_adder(a, b, c)
            print(f"{a} + {b} + {c} = {carry_out}{s}")

0 + 0 + 0 = 00
0 + 0 + 1 = 01
0 + 1 + 0 = 01
0 + 1 + 1 = 10
1 + 0 + 0 = 01
1 + 0 + 1 = 10
1 + 1 + 0 = 10
1 + 1 + 1 = 11

Read each answer as a two-bit binary number, carry first: 1 + 1 + 1 = 11 is 3, and 0 + 1 + 1 = 10 is 2. That's the full adder's truth table, all eight rows.

The ripple-carry adder: a chain of full adders

Now chain them. Each full adder handles one column and hands its carry to the full adder on its left, like a row of dominoes. This design is called a ripple-carry adder, because each carry bit "ripples" to the next full adder. Let's add 13 + 11, which is 1101 + 1011, with four full adders:

Column	A + B + carry in	Write	Carry out
1s	1 + 1 + 0	0	1
2s	0 + 1 + 1	0	1
4s	1 + 0 + 1	0	1
8s	1 + 1 + 1	1	1

Every column carries. The last carry runs out of the chain into a fifth place, and out comes 11000: 16 + 8 = 24. Now let's build that chain in Python, using the full_adder from above:

def ripple_add(x, y, bits=4):
    """Add x and y with a chain of full adders. Returns (result, carry_out)."""
    carry, result = 0, 0
    for i in range(bits):            # column i, ones column first
        a = (x >> i) & 1             # bit i of x
        b = (y >> i) & 1             # bit i of y
        s, carry = full_adder(a, b, carry)
        result |= s << i             # put the sum bit in column i
    return result, carry

print(ripple_add(0b0110, 0b0111))   # (13, 0): 6 + 7, the game's lives
print(ripple_add(0b1101, 0b1011))   # (8, 1): 13 + 11 = 11000, and 4 bits keep only 1000
print(ripple_add(0b1101, 0b1011, bits=5))  # (24, 0): with a fifth full adder, 24 fits

Line by line:

• (x >> i) & 1 reads one bit: shift x right by i places and keep the last bit. For i = 0 that's the ones column.
• Each loop is one full adder. Its carry out becomes the next loop's carry in: that's the ripple.
• s << i moves the sum bit back to column i, and |= sets that bit in the result.
• The function never uses +. The adding itself is only XOR, AND and OR, the way the chip does it; the shifts just pick out each bit and put it back.

Chain 8 full adders and you have an 8-bit adder. The A17 Pro is a 64-bit chip: it works with 64 bits at a time.

A long ripple chain is slow, though, because each full adder has to wait for the carry from the one before. Engineers count this in gate delays: a gate delay is the tiny moment one gate takes to react to its inputs. Wikipedia's adder article counts the worst case for a 32-bit ripple-carry adder: 3 gate delays for the first full adder, plus 31 × 2 for the carry to ripple through the rest, makes 65 gate delays.

That's why faster designs exist, such as the carry-lookahead adder, which works out the carry bits before the sum instead of waiting for them. The problem is old: in the mid-1800s, Charles Babbage saw the same slow ripple of carries in his difference engine, a calculating machine. Faster adders are still just gates, wired a cleverer way.

Overflow: when the last carry has nowhere to go

A row of switches has an end. With four bits, the biggest number is 1111 = 15. Add 1 more and every column carries. The last carry has nowhere to go, so it falls off the end, and the answer comes out as 0000. That's called overflow: the result needs more bits than there are. Eight bits overflow the same way, at 11111111 = 255. Our adder shows it as a carry out of 1:

print(ripple_add(0b1111, 0b0001))  # (0, 1): 15 + 1 = 0 in 4 bits, overflow
print(ripple_add(255, 1, bits=8))  # (0, 1): 255 + 1 = 0 in 8 bits

Gangnam Style and the 32-bit counter

Real counters have limits too. Guinness World Records says that in December 2014, PSY's "Gangnam Style" became the first YouTube video with so many views that the site's counter couldn't keep up. It reached 2,147,483,647 views, "the biggest number that can be stored using a 32-bit counter", and YouTube upgraded the counter to 64 bits.

That number is 2³¹ − 1: the biggest positive value of a signed 32-bit integer, one that can also hold negative numbers. A signed 64-bit counter goes up to 2⁶³ − 1 = 9,223,372,036,854,775,807: about 9.2 billion billion.

A signed 32-bit number overflows a little differently. Its top bit is the sign bit: it counts as −2,147,483,648 instead of +2,147,483,648 (this way of storing negatives is called two's complement). So the biggest positive number is a 0 followed by 31 ones, which is 2,147,483,647. Add 1 and the carry doesn't fall off the end. It ripples all the way into the sign bit, giving a 1 followed by 31 zeros, which reads as −2,147,483,648. Different route, same problem: the answer doesn't fit.

When a signed 32-bit number goes past its limit, the most common outcome, as Wikipedia puts it, is the number "wrapping" into the negatives. Python's own integers have unlimited precision, so they never overflow. But the standard ctypes module has C's fixed-size integer types, and it does no overflow checking, so you can squeeze a number into 32 bits and watch what a 32-bit counter would do:

import ctypes

views = 2_147_483_647
print(views + 1)                        # 2147483648: Python's ints never overflow
print(ctypes.c_int32(views + 1).value)  # -2147483648: a signed 32-bit counter wraps round
print(ctypes.c_int64(views + 1).value)  # 2147483648: 64 bits have room
print(2**63 - 1)                        # 9223372036854775807: the 64-bit limit

The maths is in the wiring

Back to the myth, then. There are no ones and zeros inside your phone, only switches holding high or low voltages. And the chip doesn't understand numbers. It doesn't know that 2 + 2 is 4. It has XOR gates and AND gates, wired so that the right answer falls out. The maths isn't in the chip's head. It's in the wiring.

Questions people ask

How do computers add numbers?

In binary, with logic gates. Each bit is a wire at a high (1) or low (0) voltage, set by transistor switches. For each column, a full adder, made of XOR, AND and OR gates, adds the two bits and the carry from the column before, writes a sum bit and passes a carry to the next column. A chain of full adders, one per column, adds whole numbers.

What is the difference between a half adder and a full adder?

A half adder adds two bits, A and B, and gives a sum and a carry: one XOR gate and one AND gate. A full adder adds three bits, A, B and a carry in from the previous column, so it can be chained. It's built from two half adders and an OR gate.

Why is XOR used for the sum in a half adder?

Because the sum bit of two bits is 1 exactly when one of them is 1: 0 + 1 and 1 + 0 give sum 1, while 0 + 0 and 1 + 1 give sum 0 (1 + 1 = 10). That's XOR's truth table. The carry is 1 only for 1 + 1, which is AND.

What is 1 + 1 in binary?

10, which is how binary writes two: one 2 and no 1s. In a column sum you write 0 and carry 1 into the next column. And 1 + 1 + 1 = 11 (three): write 1, carry 1.

What is overflow in binary addition?

Overflow happens when the answer needs more bits than there are. For unsigned numbers the last carry out of the leftmost bit is lost: in 4 bits, 1111 + 0001 gives 0000, and in 8 bits, 255 + 1 gives 0. In a signed 32-bit number, 2,147,483,647 + 1 carries into the sign bit and wraps to −2,147,483,648.

Is binary addition on GCSE and A level Computer Science?

Yes. The OCR GCSE Computer Science specification (J277) asks students "how to add two binary integers together (up to and including 8 bits) and explain overflow errors which may occur". The OCR A Level specification (H446) lists "the logic associated with D type flip flops, half and full adders". A typical question asks you to add two 8-bit binary numbers, show your carries and say whether the result overflows.

Keep going

• Watch the full lesson, How Do Computers Add Numbers? Binary and Logic Gates Explained, and its Short, 1 + 1 = 10? Inside a computer, that's exactly right. Then see the rest of letsBug Explains on YouTube.
• From adder circuits up to real programs: what happens when you run Hello World, from source code to machine code to pixels.
• The next Explains episode: how the internet works, and how your data travels under the sea and back.
• Powers of two at work: binary search in JavaScript and Python, one item in a million in 20 checks.

Sources

• Wikipedia: Adder (electronics) (half adder, full adder, ripple-carry adder, the 65 gate delays)
• Wikipedia: Carry-lookahead adder (carries worked out in advance; Babbage)
• Wikipedia: XOR gate (true when exactly one input is true; used in binary addition)
• Wikipedia: Logic gate (gates built from transistors acting as switches, mostly MOSFETs)
• Wikipedia: Transistor (on/off switches in digital circuits; gate, source and drain)
• Wikipedia: Logic level (high and low voltage as 1 and 0)
• Electronics Tutorials: Switching theory (switches in series as AND, in parallel as OR)
• IIT Bombay Virtual Labs: XOR gate and staircase light control
• CompSci Tutoring: Binary addition and overflow (column rules, overflow)
• OCR: GCSE Computer Science J277 specification (binary addition up to 8 bits, overflow)
• OCR: A Level Computer Science H446 specification (half and full adders)
• Wikipedia: Apple A17 Pro (19 billion transistors, 64-bit, iPhone 15 Pro)
• Guinness World Records: First YouTube video to require a 64-bit counter (Gangnam Style, December 2014)
• Wikipedia: 2,147,483,647 (the largest signed 32-bit integer; wrapping into the negatives)
• Python documentation: Built-in types (integers have unlimited precision)
• Python documentation: ctypes (fixed-size C integers, no overflow checking)

Every code sample in this post was run in Python 3.13 before publishing.