How logic gates add numbers: sum bits and carry bits

Adding 7 and 9 with nothing but switches

Logic gates add binary numbers by producing a sum bit and a carry bit for each column. A full adder also accepts the carry from the previous column. In a ripple carry adder, each carry must travel through the gates before the final answer settles.

On paper, 7 + 9 takes one line: 6 in the ones column, carry the 1, and the answer is 16. A computer has no paper and no idea what a number is. What it has are switches that are either on or off. So how does a pile of switches get 16 out of 7 and 9?

The board above answers that one layer at a time, and then keeps going. It opens on a 4-bit ripple carry adder: eight bit switches along the front edge for two numbers, A and B, each from 0 to 15, twenty logic gates behind them, and five LEDs along the back edge for the result. When you flip a switch, the copper traces that carry a 1 light up, and the light moves through the gates at the speed you set with the gate delay slider. The panel in the corner shows the inputs and the LEDs in binary and in decimal at the same time.

The Circuit slider swaps the board for one of 15 circuits built from the same kind of gate chip: a single gate, a half adder, a full adder, 4-bit and 8-bit ripple carry adders, a carry lookahead adder, an adder-subtractor, a comparator, a multiplexer, a 7-segment decoder, an SR latch, a D flip-flop, a counter, a small ALU and a puzzle made of four NAND gates. Every one of them runs on the same simulation, so you can compare how many gates each needs and how long each takes to settle.

Numbers written with two digits

In decimal each column is worth ten times the column to its right: ones, tens, hundreds. Binary works the same way with two instead of ten. The columns are worth 1, 2, 4 and 8, so four bits can hold any number from 0 (0000) to 15 (1111). On the board, switch A0 is the ones column and A3 is the eights column, and the small numbers printed under each switch give its value.

Seven is 4 + 2 + 1, which is 0111. Nine is 8 + 1, which is 1001. Their sum, 16, needs a fifth column worth 16, so the answer is 10000. That fifth column is the carry LED, C4. Whenever a sum is bigger than 15, the carry LED is the only way the board can show it.

Binary suits electronics because a wire only has to be in one of two clearly different states. A circuit does not have to tell 3 volts from 3.5 volts, only "high" from "low", and that is much easier to do reliably billions of times a second.

A transistor used as a switch

Set the Circuit slider to One gate and choose Wire under the model. Switch X connects an LED to the supply through a jumper, and the LED shows exactly what the switch says: 1 is on, 0 is off.

Now choose Transistor. The model shows an NPN transistor with three legs. A small current into the middle leg (the base) lets a much larger current flow between the other two (the collector and the emitter), and the LED lights. Take the base current away and the LED goes dark. The transistor has become a switch that is flipped by electricity instead of by a finger.

This is a simplification, and the model says so. A real transistor is an analogue part: more base current gives more collector current over a range. Logic circuits are designed so that the transistor only spends time fully off or fully on and passes through the middle as quickly as it can. That is what lets us treat it as a switch.

Gates made from pairs of transistors

Once a switch can control another switch, you can build decisions. Chips today use a kind of transistor called the MOSFET, in two types: n-channel transistors conduct when their input is high, p-channel transistors conduct when it is low. CMOS logic pairs them so that one network can pull the output up to the supply and the other can pull it down to ground, and for any input exactly one of the two networks conducts. A gate standing still draws almost no current. That property, shown by Chih-Tang Sah and Frank Wanlass at Fairchild in 1963, is the reason a phone can hold billions of transistors without melting.

Count the transistors and the gates stop costing the same:

The surprise is that AND, the gate everyone learns first, costs more than NAND. In CMOS the natural gates are the inverting ones, because the n-channel network pulls the output down: two n-channel transistors in series pull down only when both inputs are 1, which is NAND, and two in parallel make NOR. To get AND you add an inverter. Turn on Transistors per chip and each chip on the board shows its own count; the One gate bench lets you step through all seven types and the plain wire.

NAND has one more property. With NAND gates alone you can build NOT (tie both inputs together), AND (a NAND and a NOT), OR (invert both inputs first) and everything else. The last circuit on the board is a puzzle built on this: four NAND gates whose inputs you choose in the lab under the controls. Get the wiring right and the output matches XOR in all four rows.

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

Look at the XOR truth table. 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10 in binary, which is 0 in this column with a 1 carried. The right-hand digit of every answer is exactly the XOR column. The carry is 1 only in the last row, which is exactly AND.

So one XOR and one AND fed by the same two bits add them. This pair is called a half adder. On the Half adder board it stands alone; on the 4-bit adder it is the first block in every bit. With A and B both at 1, the XOR gives sum 0 and the AND gives carry 1.

The full adder: three bits in, two bits out

A half adder is enough for the ones column, but every other column has three things to add: a bit of A, a bit of B and the carry coming from the right. The full adder handles this with two half adders and an OR gate. On the board each bit uses these names:

1. p = A xor B and g = A and B (the first half adder)
2. S = p xor C and t = p and C (the second half adder adds the incoming carry C)
3. Carry out = g or t

The OR gate never sees two 1s at once. If A and B are both 1, then p is 0 and t cannot be 1. It only joins the two ways a carry can be made: the column itself made one (g), or the column passed on the carry it received (t). The eight rows of the full adder truth table cover every case, and the largest, 1 + 1 + 1 = 3, comes out as carry 1 and sum 1.

Five gates per bit and four bits make the 20 gates of the 4-bit adder. The carry out of each full adder is wired to the carry in of the next one to the left, like the "carry the 1" step on paper. That chain is why it is called a ripple carry adder. While it runs, the truth table in the corner marks which row each bit is using, so you can watch bit 0 sit on 1 1 0 while bit 3 waits on 0 1 1.

Why the carry is slow

No gate answers instantly. When its inputs change, the output follows a short time later, called the gate delay or propagation delay. The model gives every gate a delay of exactly one unit, and the slider stretches that unit from 0.05 to 2.4 seconds so you can watch it.

Here is 7 + 9, starting from a board at 0 + 0:

Each bit needs two gate delays to pass the carry along: one for the AND that makes t, one for the OR that makes the carry out. Across four bits the last carry lands after 8 delays. The worst case for the 4-bit board is 9 delays, which matches 2n + 1 for n = 4 bits. Turn on Delay on each chip and every chip shows the delay at which its output last changed; along the carry chain the numbers climb 2, 4, 6, 8.

Watch the LEDs during those 8 delays and you will see wrong answers. At delay 6 the panel can read 01000, which is 8. Nothing is broken: those LEDs are showing a sum computed before the carry arrived. Real circuits have the same short false outputs, called glitches, which is why a processor waits a fixed time for the slowest path before it reads an adder's output. The length of that wait is one of the things that sets the clock speed. The Timing chart shows the same thing as waveforms, with each output stepping up and down before it settles.

The 8-bit board makes the cost plain. It is the same full adder eight times, 40 gates, and 255 + 1 sends a carry through every bit: the LEDs settle after 16 gate delays, twice as long as 15 + 1 on the 4-bit board. A 64-bit ripple carry adder built the same way would need 129 gate delays in the worst case. If you want to see one delay at a time, turn on One delay at a time and press Next delay under the model.

Working out the carries ahead

Fast adders do not wait for the ripple. Look again at the full adder: a column makes a carry by itself when g = A and B is 1, and passes on the carry it receives when p = A xor B is 1. Those two signals are ready after one gate delay in every column at once. From them each carry can be written out in full:

• C1 = g0 + p0 C0
• C2 = g1 + p1 g0 + p1 p0 C0
• C3 = g2 + p2 g1 + p2 p1 g0 + p2 p1 p0 C0
• C4 = g3 + p3 g2 + p3 p2 g1 + p3 p2 p1 g0 + p3 p2 p1 p0 C0

Read C2 as a sentence: there is a carry into bit 2 if bit 1 made one, or if bit 1 passes on a carry made by bit 0, or if bits 1 and 0 both pass on the carry in. Each line is a row of AND gates followed by one OR, so every carry arrives after three gate delays, and the sums one delay later. The Carry lookahead board does this with 26 gates. Put 15 + 1 on it and it settles in 4 gate delays, where the ripple board took 8. The panel's table shows P, G and the carry for each bit.

The price is in the AND gates. C4 already needs a 5-input AND and a 5-input OR, and the terms grow with every bit, so wide adders combine the two ideas: small lookahead blocks of four bits, with a second level of lookahead between the blocks. IBM's Gerald Rosenberger filed a patent for a binary carry lookahead adder in 1957. Charles Babbage had seen the same problem a century earlier and designed a mechanism to anticipate carries for his analytical engine. Today a 4-bit adder with "fast carry" is a catalogue chip: Texas Instruments still lists the SN74LS283.

Subtracting with the same adder

Computers do not need a separate subtractor. In two's complement, the usual way to store negative numbers, minus B is written as "flip every bit of B, then add 1". So A − B is A + (not B) + 1.

The Adder-subtractor board adds one XOR per bit in front of B. With SUB off, each XOR passes its B bit straight through; with SUB on, each XOR flips its bit, and the same SUB line feeds the carry in, which supplies the extra 1. Try 5 − 7. B = 0111 becomes 1000, the adder works out 0101 + 1000 + 1 = 1110, and 1110 read as a signed 4-bit number is −2. Read as an unsigned number it is 14, which is also right in its own way: 5 − 7 + 16 = 14. The same bits mean different things depending on how you read them, and the panel shows both.

A signed 4-bit number only runs from −8 to 7, so some answers do not fit. The board's green V LED catches this: it is an XOR of the carry into the top bit and the carry out of it, and it lights when they differ. 7 + 1 (SUB off) lights it, because 0111 + 0001 = 1000, which reads as −8. The extra XOR row costs one more gate delay at the start, and the V gate one more at the end, so the worst case on this board is 11 delays.

Comparing two numbers

How does a circuit decide that 9 is bigger than 5? The way you would do it with written numbers: look at the highest digit where they differ. The Comparator board works it out per bit. A > B in one bit means A is 1 and B is 0 (an AND with an inverter on B), A < B means the opposite, and the bit is equal when neither is true, which is a NOR of the two.

Then it ranks the bits. A is bigger if bit 3 says so, or if bit 3 is equal and bit 2 says so, or if bits 3 and 2 are equal and bit 1 says so, and so on down. Those are four AND terms joined by an OR, the same shape as the lookahead carries. 1001 against 0101 differ first at bit 3, where A has the 1, and the A > B LED lights after 4 gate delays (the worst case on this board is 5). The board uses 29 gates. The TI SN74LS85 does the same job in one package and has extra inputs so that several chips can compare longer numbers.

Choosing one input and drawing a digit

Two more circuits use the same pattern of AND gates collected by an OR.

A multiplexer chooses. The 4-to-1 board has four data inputs, D0 to D3, and two select bits. Each data input goes into a 3-input AND that also takes the select bits (or their inverses), so for any setting exactly one AND is open, and the OR passes its data bit to Y. Seven gates and three gate delays. Wherever one wire has to carry one of several signals, from the register file of a processor to the source switch on a TV, there is a multiplexer.

A decoder draws. A 7-segment display has seven bar-shaped LEDs named a to g, and each digit lights a different set: 1 lights b and c, 8 lights all seven. For every segment you can list the digits that light it and simplify that list into a sum of products, a handful of AND terms joined by an OR. The board's decoder was worked out that way: 4 inverters, 28 shared AND terms and 7 ORs, 39 gates, three gate delays from switch to segment. It draws the hex digits A to F as well as 0 to 9. The TI SN74LS47 is the catalogue version for 0 to 9.

Circuits that remember

Everything so far forgets. Change the switches and the output follows; nothing depends on what happened before. Memory needs a loop.

The SR latch is two NOR gates, each feeding its output into the other. With S and R both 0 the loop holds whatever it had, Q = 1 or Q = 0, and keeps holding it as long as power stays on. A 1 on S forces Q to 1, a 1 on R forces it to 0. Set Q, turn S off again, and Q stays at 1. That is one bit of memory made of eight transistors.

The latch has a forbidden input. With S and R both 1 both outputs are 0, and if you then release both at the same moment, the two gates race. In the model, where both gates have exactly the same delay, the loop never settles: the outputs flip together every gate delay and the panel says so. A real latch is never perfectly balanced, so one side wins, but which one and how long it takes cannot be predicted. Engineers call this metastability, and digital designs are arranged so that it cannot happen in normal use.

A D flip-flop removes the problem by taking in data only at one instant. The board's version is the six-NAND design used in the 7474 chip. While the clock is low or high, D can change as often as it likes and Q does not move. Only at the moment CLK rises from 0 to 1 does Q take the value of D, and it holds it until the next rising edge. Fed 49,152 random steps of D and CLK, Q followed that rule every time.

Counting clock pulses

Put four flip-flops side by side, add a small circuit that works out the current number plus one, and feed the result back to the flip-flops' D inputs. Every clock pulse loads the next number. The 4-bit counter board does exactly that with 30 gates: 24 NANDs in the four flip-flops and six gates for the adder. Bit 0 always flips, bit 1 flips when bit 0 is 1, bit 2 when bits 1 and 0 are both 1, bit 3 when all three below it are 1.

Press Clock pulse and watch the order. The clock edge reaches all four flip-flops together, their outputs change two gate delays later, and the "plus one" gates then prepare the next number long before the next pulse. Because every bit changes on the same edge, it is called a synchronous counter, like the TI SN74LS161A. After 1111 it wraps round to 0000. Run through 40 pulses, it counted 0 to 15 and round again without a miss.

An ALU from the same parts

A processor's arithmetic logic unit is the circuit that does the actual sums. The 4-bit ALU board shows the idea in 59 gates. For each bit it works out four results side by side: A + B, A − B, A AND B and A OR B. Two op bits then choose which one reaches the outputs, through the same kind of AND and OR selection as the multiplexer. Op 00 adds, 01 subtracts (using the XOR row from the adder-subtractor), 10 is AND and 11 is OR.

All four results are computed all the time; the op bits only choose which one you see. That is how real ALUs work too, and it is why the ALU's longest path, 13 gate delays here, is longer than the adder's alone. Try 12 AND 10: 1100 and 1010 have only bit 3 in common, so the answer is 1000, which is 8.

How long is a gate delay?

The model counts delays; real parts measure them in nanoseconds. Texas Instruments gives a typical delay of 9 ns for its SN74HC00 NAND gates at 4.5 V, 9 to 10 ns for the older SN74LS00, and about 5 ns for the SN74AC00 at 5 V. A relay is a million times slower: the Omron G5V-1 data sheet allows up to 5 ms to operate.

Multiply that by the board's longest path. A 4-bit ripple carry adder needs 9 delays, so with 74HC00-style gates it settles in about 81 ns, fast enough for twelve million additions a second. Built from relays, the same adder would need 45 ms. The lab under the controls does this sum for whichever circuit is on the board. A modern processor adds 64-bit numbers billions of times a second because its gates are thousands of times faster and its adders use lookahead, not because the logic is any different.

Check every circuit yourself

Every circuit on the board was checked against its truth table for every possible input. The 4-bit adder gave A + B + C0 for all 512 combinations and settled on the right answer within 9 gate delays after each of the 262,144 possible changes from one input to another. The 8-bit adder was checked for all 131,072 sums and 400,000 random changes. The lookahead adder settled within 4 delays, the adder-subtractor within 11, the comparator within 5, the multiplexer and the decoder within 3, and the ALU within 13 after every one of its 1,048,576 changes. The memory circuits were run through sequences: the latch through set, hold and reset, the flip-flop through random clock and data, the counter through 40 pulses.

You can try a few on the board:

• 15 + 1 on the ripple adder: all four carries ripple, and the LEDs read 10000 after 8 delays.
• 15 + 1 on the lookahead adder: the same answer after 4 delays.
• 5 + 2: no column carries, and the answer 0111 (7) is ready after 2 delays.
• 5 − 7 on the adder-subtractor: 1110, which is −2.

How the model differs from a real chip

• Every gate has the same delay. In real logic an XOR is slower than a NAND, a gate driving many inputs is slower than one driving a single input, and delays change with temperature and supply voltage.
• Every wire takes 0.85 of a gate delay to cross, whatever its length. On a real board short traces are effectively instant; inside a chip long wires can be slower than the gates.
• Signals are perfectly 0 or 1. Real voltages rise and fall over a short time, and the board has no noise, heat or fan-out limits.
• One gate per chip. Real logic chips hold four NANDs or six inverters in one package, and they need power pins, decoupling capacitors and pull-up resistors that the board leaves out.
• The transistor on the bench is drawn as a single bipolar switch, while the transistor counts on the chips are for CMOS.

From Boole's algebra to relay adders

In 1854 George Boole published The Laws of Thought, an algebra in which logical statements are combined with operations much like multiplication and addition, and in which the symbols 1 and 0 play a special part. It was a book about reasoning, not machines.

The link to circuits came in 1937. Claude Shannon, a master's student at MIT, wrote the thesis A Symbolic Analysis of Relay and Switching Circuits. He showed that switches in series and in parallel follow the same rules as Boole's algebra, so a circuit can be designed and simplified with algebra instead of by trial. In the last chapter he gave several example circuits, including an adder for binary numbers. A paper from the thesis was published in the Transactions of the American Institute of Electrical Engineers in 1938, and it won the Alfred Noble Prize.

In the same year George Stibitz, a scientist at Bell Labs, built a demonstration adder from relays. He called it the Model K, after the kitchen table where he assembled it. Ten years later, in December 1947, John Bardeen and Walter Brattain made the first working transistor at Bell Labs, in a group led by William Shockley. The three shared the 1956 Nobel Prize in Physics "for their researches on semiconductors and their discovery of the transistor effect".

From relays to billions of transistors

The first large computers used whatever switches were at hand. Konrad Zuse's Z3 of 1941 used 2,300 relays; the Harvard Mark 1, finished in 1944, used 3,500, kept in step by a camshaft fifty feet long. Colossus, working at Bletchley Park from early 1944, switched with 2,500 valves, and ENIAC, announced at the University of Pennsylvania in February 1946, needed 18,000 vacuum tubes and filled a room 30 by 50 feet (about 9 by 15 metres). MIT's TX-0 of 1956 was the first general-purpose programmable computer built with transistors, each one in a plug-in "bottle" so it could be swapped like a tube.

Then the gates moved onto silicon. In 1961 Fairchild announced one of the first planar integrated circuits, a flip-flop with four transistors and five resistors. Texas Instruments' 7400 series of TTL logic chips, sold in cheap plastic packages from 1966, soon held more than half the logic market, and many of its parts, such as the SN7400 quad NAND, are still sold today. The Apollo Guidance Computer that first flew on Apollo 7 in 1968 was built mostly from one chip type holding two 3-input NOR gates, several thousand of them per computer.

In 1965 Gordon Moore predicted that the number of components on a chip would double every year, and later revised that to every two years. The Intel 4004 of 1971 put a whole 4-bit processor on one chip with 2,300 transistors (the Computer History Museum's timeline gives 2,250). Apple's M1 of 2020 holds 16 billion, about seven million times as many, and NVIDIA's Blackwell GPUs of 2024 hold 208 billion. Inside all of them the arithmetic is still done by adders, multiplexers and flip-flops like the ones on this board.