The one thing computers are really good at is calculating. You might now expect that all CPUs are capable of the four basic arithmetic operations, but that isn't the case. The first 8 bit processors were only able to add and subtract numbers, and even the subtraction was performed by adding the negated subtrahend. Multiplication and division instructions first appeared on 16 bit processors, albeit they were still very slow in the first generation.
Simple multiplications and divisions by powers of two can be achieved by shifting a value bitwise to the left or right, respectively. This is, shifting a value by one bit to the left is the same as multiplying it by 2, while shifting by two bits to the left multiplies it by 4, and so on.
But how can we multiply any two numbers? It has to be done step by step, by using basic operations like addition or bit rotation. This article will explain how it works on a Z80 CPU.
Back at school, we have learned to multiply large numbers by long multiplication. Basically, we break up the problem by multiplying the multiplier with each digit of the multiplicand, and then summing the products. For example, if we want to compute the product of 27 and 12, we compute 27×2 = 54 and 27×1 = 27, and then sum the products 57+270 = 324.
27 × 12
———————————
54
+ 27∙
———————————
324
We can use the same algorithm on a computer. But wait, wouldn't we still have to multiply, even if with smaller numbers? Actually, no! Since computers use binary digits, we only need to multiply either by 1, giving the value itself, or by 0, always giving 0.
This is the the same long multiplication of 27 (11011) and 12 (1100) with binary numbers:
11011 × 1100
————————————————
00000
00000∙
11011∙∙
+ 11011∙∙∙
————————————————
101000100
The steps can be executed in a loop. At the beginning, a result register is initialized with zero. If the rightmost bit of the multiplicand is 1, the multiplier is added to the result register. After that, the multiplicand is rotated to the right by one bit, and the multiplier is rotated to the left by one bit. This loop is repeated until the multiplicand is zero, because the result won't change after that anymore.
The following Z80 assembler code example multiplies the values in the BC and DE register pairs, and returns the product in the HL register pair. If an overflow occured during multiplication, the Carry flag will be set.
The multiplicant is kept in the BC register pair. To rotate it one bit to the right, we first use the srl b instruction. It rotates the B register, moving the value of bit 0 to the Carry flag, and inserting a 0 to bit 7, so the multiplicant is filled up with zeros with each rotation. After that, rr c rotates the C register and moves the content of the Carry flag to bit 7. Both instructions combined rotate the BC register pair one bit to the right, insert a 0 to the highest bit. The lowest bit is moved to the Carry flag, where it can be tested.
We essentially do the same with the multiplier in the DE register pair, but in the opposite direction. As a rotation to the left by one bit essentially just doubles the value, we also could have used add de,de. Sadly the Z80 does not offer such an instruction.
multiply: ld hl, 0 ; clear the result register
.loop: ld a, b ; is BC == 0?
or c ; (also resets carry flag)
ret z ; then we're done!
srl b ; logical right shift of BC
rr c ; bit 0 goes to carry flag
jr nc, .zerobit ; unless bit 0 was 0
add hl, de ; add multiplier to result
ret c ; return on overflow
.zerobit: sla e ; shift multiplier to the left
rl d ; topmost bit goes to carry flag
ret c ; return on overflow
jr .loop ; next iteration
The example only multiplies positive integers. To multiply negative integers, we first need to change all factors to positive numbers and do the multiplication. The result then needs to be negated if one of the factors was negative, but not both.