26

How did 8 bit processors such as the Z80 and 8080 perform 16 bit arithmetic? They have an 8 bit data bus, so how does the ALU perform 16 bit arithmetic on the register pairs?

Z80 architecture diagram (from Wikipedia):

enter image description here

38

In the case of the Z80, the ALU is only 4 bits wide. That's no problem, since the internals of the CPU are controlled by a program internal to the processor, called the microprogram (or microcode), which is responsible for piping data around in the necessary way to execute some instruction. So if the Z80 gets an instruction like ADD HL, BC, the microprogram probably goes something like this:

  • Add the lowest half of the lowest bytes; no carry-in; carry-out to H flag
  • Add the upper half of the lowest bytes; carry-in from H flag; carry-out to C flag
  • Add the lowest half of the upper bytes; carry-in from C flag; carry-out to H flag
  • Add the upper half of the upper bytes; carry-in from H flag; carry-out to C flag

The result is a 16-bit addition, just that it's done four bits at a time. Some Z80 compatibles had microcode that did what I describe, but microcode is not the only way to achieve this. The same procedure could have been controlled by a finite state machine or some other kind of sequencer.

Another example of an 8-bit processor is the 6502. It doesn't do any 16-bit arithmetic for you; the software needs to explicitly do a 16-bit operation in two halves; perhaps like this:

; Add $BEEF to a 16-bit variable stored at address $40
clc       ; Clear carry
lda $40   ; load first half of the 16-bit variable into memory
adc #$ef  ; Add the first half of the number
sta $40   ; save it
lda $41   ; load the other half
adc #$be  ; Add the other half of the constant, plus the carry
sta $41   ; and save it

The principle extends to any width of ALU and any width of data. So the PDP-8 is a 12-bit computer. There's an implementation called PDP-8/S, which has a 1-bit ALU, and the hardware performs all 12-bit operations one bit at a time. Needless to say, it was much slower, and I believe it was rather unsuccessful commercially.

  • 3
    Having written microcode for some specialised processors (back around the time when the Z80 was fresh and new) I would beg to differ with the description of "simple" for the internal microprogram. The microcode sequences can get quite wide with many internal timing dependencies that have to be catered for on each of the internal clock phases. – uɐɪ Jun 5 '18 at 14:08
  • 2
    The Z80 includes two ALUs: a 4-bit general-purpose one, and a 16-bit increment/decrement circuit. Having recently found out about that, I find myself curious how much circuitry would have been needed to allow the inc/dec to add or subtract 256 rather than 1, and use that to expedite the s8+16 arithmetic used in "jr" or the indexed addressing modes. Or, for that matter, how much circuitry would be required to special-case (IX+0) or (IY+0) to save some cycles. – supercat Jun 5 '18 at 15:36
  • 1
    @ʎəʞo uɐɪ: Did the processors you describe perform arithmetic and such like a typical CPU, or were they more like Steve Wozniak's Disk ][ controller? I've sometimes "toyed" with the idea of implementing something similar to the Simon® brand electronic memory game with a few shift registers and a state machine. I think the ROM would need to be larger than the microcontroller on the Simon®, but I'm not sure by how much. – supercat Jun 5 '18 at 15:44
  • 1
    @JetBlue 8-bit CPU microcode is in usually (always?) in a mask-programmed ROM on the chip. It can't be changed, and in my experience it can't be examined. – Wayne Conrad Jun 5 '18 at 22:57
  • 3
    @Tim, DEC made several varieties of PDP-8; Wilson was only referring to the PDP-8/S when he said it was unsuccessful. – prl Jun 6 '18 at 1:46
36

How did 8 bit processors such as the Z80 and 8080 perform 16 bit arithmetic?

Same way one adds multiple digit numbers on paper. One digit (-pair) at a time and iterating over all digits while incooperating any carry. With(in) a CPU the chunks are ALU sized units like 4/8/16 or 32 bit.

As with paper based addition this method can be used for numbers of arbitary length (number of digits). The difference between an 8 bit CPU processing 64 bit numbers and a 32 bit CPU doing 64 bit (*1) is just the number of iterations needed.

They have an 8 bit data bus, so how does the ALU perform 16 bit arithmetic on the register pairs?

As above. But I guess the question you wanted to ask is rather

"How can a 8 bit ALU do 16 bit operations in a single instruction"

Still as above, as two operations of 8 bit each, the second minding any carry of the first. Just now the iteration (with a count of 2) is hard coded within the CPU, thus only one instruction is needed. Again, still the same for any other CPU with hard coded operation for operands wider than its ALU size.


Further Reading:

The Wiki article about Arbitrary Precision Arithmetic offers a wider view on this topic, including some historic information.


*1 - Or a 1 bit CPU - Best granuality, worst performance :))

  • 1
    The 6502 could perform 16-bit addition in a single cycle with an 8-bit ALU in the case where there was no carry or borrow from the lower half to the upper half. I find it curious that the concept of expediting the no-carry case doesn't seem to have been used in other chips since it would seem like it should be a cheap improvement. – supercat Jun 5 '18 at 19:10
  • 2
    @supercat, how often do you do an add with no internal carry? – Mark Jun 5 '18 at 21:24
  • 3
    @Mark: In the course of address calculations, quite often. If code is indifferent to the possibility of a page crossing, then adding a random 8-bit displacement to a random 16-bit address would on average cause a carry or borrow into the top 8 bits about 1/4 of the time (so 3/4 of the time there would be no carry/borrow). On the 6502, many instructions will execute a cycle faster in the "no carry/borrow" case, and programmers often exploit this by arranging things to avoid having loops or data structures cross page boundaries. – supercat Jun 5 '18 at 22:12
  • 1
    @Mark: If X holds a value less than $CC, the first fetched MSB of the address will be correct "as-is" thus avoiding any need to increment it. Only if a carry occurs out of the lower half will it be necessary to spend a cycle computing the upper half. – supercat Jun 5 '18 at 22:18
  • 1
    @PeterCordes: Pipelining may reduce propagation delays, but requires hardware to compute all the bits. The 6502 uses the same ALU hardware to calculate upper 8 address bits in the page-crossing case as it uses to calculate just about everything else, but can "calculate" the upper 8 bits in the non-page crossing case without using the ALU (since in that case the upper 8 bits of the address can be copied directly from the data bus). – supercat Jun 7 '18 at 19:57
12

by using CARRY flag. Bignum (its common name for any large number lib like arbitrary size integer/fixed point/floating point numbers) algorithms do the same thing (compute m*n bit operations using only n bit operations) for more info see

So operations like +,- are done by sequencing from LSW to MSW (where word is the ALU bitwidth).

+: add,adc,adc,adc...
-: sub,sbc,sbc,sbc...

so for example if we have 8 bit ALU and want compute 16 bit C = A + B it would be like this (sequencing 2 times 8 bit opeartion):

C.L = A.L + B.L
C.H = A.H + B.H + Carry

for the C = A - B it would look like this:

C.L = A.L - B.L
C.H = A.H - B.H - Carry

other operations like *,/,... are a bit more complicated for more info see these:

Now if you want to implement it inside CPU than that is done in microcode (the stuff in CPU controls how are its parts used and in which order it is like a small program for each instruction). Some HW architectures might even nest smaller ALU blocks for speed ...

  • 2
    Bignum is a good hint here. – Raffzahn Jun 5 '18 at 8:39
  • 1
    Re: your last point: Pentium4 (before Prescott) has 0.5 cycle latency for add, using narrow ALUs that ran at twice core clock speed. So a chain of dependent add eax, ecx or whatever can run at 2 per clock, instead of the usual latency bottleneck of 1 cycle. Was there a P4 model with double-pumped 64-bit operations? – Peter Cordes Jun 7 '18 at 10:41
4

Conceptually, this is a lot like how we (humans) do add, subtract, multiply, etc multi-digit numbers. An 8-bit processor has 8-bit "digits" that it can concentrate on one at a time.

If we want to add 1234+5678, we do as follows: we add the two lowest digits (4+8=12), we write down the 2 in the 1s column of the answer, carry the 1. We add 7+3, plus the carried 1, to get 11. We write down the 1 (second digit of 11) in the 10s column of our answer, carry the 1... and so forth.

Note: in the following paragraph, all numbers are base 10; when broken down into bytes, the high byte is first, and they are still shown in decimal; they are in brackets to keep them together, seperated by a comma. So (4,211) means a high byte with the decimal value 4, and a low byte with decimal 211. 4*256+211=1235.

An 8-bit processor can do the same, but it has 256 digits, which we would call 1 through 255, and 0. Don't be confused by bytes being written as 2 hex digits; this just saves us from needing only 16 different digits; an 8-bit computer has 256 different digits; each byte is one digit.

If it wants to add 1235 + 5678, each stored as 2 bytes (4, 211) + (22,46), it would add the "1s column", which here is 211+46=257. Since it's an 8-bit processor, only the lowest 8 bits are kept; this comes out as 1. The processor does remember that there is a "carry" by setting the carry flag.

The sum (without carry) is stored as the lowest byte of the answer.

It then adds the 2 "digits" (bytes) in the "tens column" (256s column). 4+22=26, don't forget to add the carry, making 27.

So the answer should be two bytes: (27,1). 27*256+1=6913, which is correct.

A similar process can be applied by subtraction (possibly "with borrow"), multiplication, and division. If you think how you might do these yourself, for long numbers, an 8-bit processor might do a similar thing for larger numbers.

Note that this does not just apply to 16-bit arithmetic, but can be extended to any size number (of a fixed size).

These steps, of course, are part of the (machine code) program. Adding a multi-byte number would take several instructions.

Note that the above only applies to integers; floating point (e.g. 0.1) is more complicated.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.