The ALU

The pages so far have built the pieces: an adder that also subtracts, logic gates for every bit, shifts, and registers to hold the results. A processor packs its sums and logic into one circuit, the arithmetic logic unit, or ALU: two numbers in, an operation code saying what to do with them, one number out, and a few flags describing the result.

This page builds its ALU around the operations and flags of the 6502, the 8-bit processor these pages are working towards. Numbers are written in hex with a $, as in 6502 assembly: $3C is 0x3C, 60.

1 · One circuit, many operations

The simplest way to build an ALU is to work out every operation at once, side by side, and then choose one result with a multiplexer, like the one on Combining gates, whose select inputs are the operation code.

Click the bits of A and B, and choose an operation. The table on the right shows every operation’s result for these inputs: the ALU works them all out, and the operation code picks one. C in is the carry flag going in; the flags below are what the operation leaves, and “unchanged” marks a flag the operation doesn’t touch. Operations on A alone (the shifts, rotates, INC and DEC) fade B out.

Real ALUs share more than that. One adder does five of these operations (ADC, SBC, CMP, INC and DEC), just with different inputs: B, B flipped, or 1. But the idea is the same: the operation code steers the inputs and picks the output.

2 · Logic, bit by bit

AND, OR and exclusive OR (the 6502 names them AND, ORA for OR with A, and EOR for exclusive OR) work on each pair of bits separately: bit 0 of A with bit 0 of B, bit 1 with bit 1, and so on, eight gates side by side with no carries between them. They’re how a program picks out, sets and flips individual bits:

AND keeps the bits where B has a 1, and clears the rest: AND with $0F keeps the low four bits. B used like this is called a mask.
OR sets bits: OR with $80 makes the top bit 1, whatever it was.
Exclusive OR flips bits: EOR with $FF flips all eight (the 6502 has no NOT instruction; this is how it’s done), and EOR with $80 flips just the top one, the trick on Numbers in binary for turning unsigned samples into signed ones.

3 · Arithmetic: one adder

ADC, add with carry, adds A, B and the carry flag. The carry going in is what lets a processor add numbers bigger than a byte, one byte at a time, exactly like carrying in long addition: clear the carry, add the low bytes, then add the high bytes, and the carry from the low bytes is added in. For $12FF + $0001: the low bytes give $FF + $01 = $00, carry 1; the high bytes give $12 + $00 + 1 = $13. The answer is $1300.

SBC, subtract with borrow, is the subtractor from Adding: it adds B with every bit flipped, plus the carry flag as the extra 1. So a program sets the carry before subtracting, and a carry of 0 coming out means a borrow was needed, ready for the next byte.

CMP, compare, subtracts B from A but throws the answer away, keeping only the flags: Z says whether they were equal, and C whether A was at least as big as B (as unsigned numbers). It’s how a program asks “is it 10 yet?”.

INC (increment) and DEC (decrement) add or take away 1. On the 6502 they work on memory, and on the X and Y registers, as INX (increment X), DEY (decrement Y) and so on, rather than on A, and they leave the carry flag alone, so that counting doesn’t disturb a sum in progress.

4 · Shifts and rotates

ASL (arithmetic shift left) and LSR (logical shift right) are the shifts from Numbers in binary: left, doubling, and right, a logical shift that halves. The bit that falls off the end goes into the carry flag.

ROL and ROR, rotate left and right, do the same, but bring the old carry flag in at the empty end. The byte and the carry act as one 9-bit ring. As with adding, that’s what makes them work across bytes: shift a 16-bit number left by doing ASL on its low byte, then ROL on its high byte, and the bit that falls out of the first goes into the second.

5 · Flags

The flags are single bits that describe the last result, kept in a status register. The 6502 has four that the ALU sets:

N, negative: the result’s top bit. As a signed number, the result is negative. It’s just a wire.
Z, zero: the result is 0. All eight bits are 0, which is an 8-input NOR gate.
C, carry: the carry out of the adder, or the bit shifted out.
V, overflow: a signed result didn’t fit. As on Adding, the carry into the top column differs from the carry out of it: one XOR gate.

Not every operation sets every flag. Each one updates the flags that mean something for it, and leaves the others alone:

	N	V	Z	C
ADC, SBC	✓	✓	✓	✓
CMP	✓		✓	✓
AND, ORA, EOR	✓		✓
ASL, LSR, ROL, ROR	✓		✓	✓
INC, DEC	✓		✓

Flags are how a program makes decisions. The 6502’s branch instructions each test one flag and jump if it’s set or clear: BEQ and BNE (“equal”, “not equal”) test Z, BCS and BCC test C, BMI and BPL (“minus”, “plus”) test N, BVS and BVC test V. Compare, then branch: that’s every if and every loop.

6 · Decimal mode

The 6502 can also add in binary-coded decimal (BCD): each byte holds two decimal digits, one in each group of four bits, so $58 means fifty-eight. It’s handy for anything shown to people as digits, like a score or a clock, because there’s no converting from binary to decimal for the display.

Adding BCD with the ordinary adder goes wrong as soon as a digit passes 9: $09 + $01 gives $0A, but the answer should be $10. The fix is to add 6 to any digit that comes to more than 9. Four bits hold 16 patterns and a decimal digit only uses 10, so adding 6 skips the six unused patterns, A to F, and pushes a carry into the next digit, just as 9 + 1 should. The 6502 does this when its decimal flag, D, is set: SED (set decimal) sets it, and CLD (clear decimal) clears it.

Two decimal numbers as BCD, added. The plain binary sum is wrong whenever a digit passes 9. Correct the low digit, then the high digit, and the answer is right in decimal. 58 + 46 needs both corrections: binary gives $9E, and the decimal answer is 04, carry 1: 104.

Decimal mode had loose ends. On the original 6502, after a decimal add the N, V and Z flags don’t reliably describe the decimal result (the later 65C02 fixed this), so programs used only the carry. And the version of the 6502 inside the Nintendo Entertainment System had decimal mode switched off altogether.

Summary

The ALU takes two numbers and an operation code, and gives a result and flags. The simple way to build one is to work out every operation at once and choose with a multiplexer; real ones share one adder between ADC, SBC, CMP, INC and DEC.
AND, OR and exclusive OR work bit by bit: AND clears bits (masking), OR sets them, exclusive OR flips them.
ADC and SBC take the carry in, so numbers wider than a byte are added a byte at a time. CMP subtracts only for the flags.
Shifts put the bit that falls off into the carry; rotates bring the carry back in, for multi-byte shifts.
The flags, N (top bit), Z (zero: an 8-input NOR), C (carry) and V (signed overflow), describe the result, and branch instructions test them.
Decimal mode adds BCD digits, adding 6 to any digit that passes 9.