Bit Math

[ACagliano]

Just wondering.... Is this the correct way to Multiply numbers, using bit shifting. Modify as needed. And how would you do division?

Code: Select All | Copy To Clipboard

1 2 3 4 5 6 7 8 9 10 11 12 13

ld c,a $: rl a rr b jr c, +$ jz nz, -$ $: or c push af ld a,b or b ret z pop af jr -2$ ;Your next command, upon returning, should be pop af.

[Xeda112358]

Hmm, it doesn't look quite right if you are trying to multiply registers. I don't know if this will help you?

Code: Select All | Copy To Clipboard

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

D_Times_E: ;Inputs: ;     D and E are factors ;Outputs: ;     A is the product (lower 8 bits) ;     B is 0 ;     C,DE, HL are not changed ;Size:  12 bytes ;Speed: 304+b cycles where b is the number of set bits in E      xor a         ;This is an optimised way to set A to zero. 4 cycles, 1 byte.      ld b,8        ;Number of bits in E, so number of times we will cycle through Loop:      add a,a       ;We double A, so we shift it left.      rlc e         ;We want the next bit in E, so it is shifted into the c flag      jr nc,$+3     ;If it is 0, we don't need to add anything to A        add a,d     ;Since it was 1, we do A+1*D      djnz Loop     ;Decrements B, if it isn't zero yet, jump back to Loop:      ret

Basically, this works like regular multiplication that you would do by hand. Since the above code is using 8-bit registers, there are 8 digits per number. Since bits are only 1 or 0, we only have to multiply by one or zero. Then we just add the result to the accumulator. When we get ready to add the next multiplication, we need to shift the accumulator left. In Decimal, we do this by multiplying by ten (tacking on a zero at the end). In binary, we multiply by 2. I hope this helps?

As for division, the algorithm is actually very similar and uses long division like you learned in grade school, except with binary. Say you have 37/5. In binary, you are doing:

00100101/101.

so you shift the 00100101 and move the overflow into another register. Pretend I have done this 5 times already:
0000010010100000
Now you see, the overflow is not greater than 5, so shift once more:
0000100101000000
Now it is, so we get tricky. First, subtract five from the overflow and increment the other number by 1:
0000010001000001
Now shift again:
0000100010000010
Now it is greater than 5 again, so:
0000001110000011
Shift again:
00000011100000110
And do the proper adjustment:
00000001000000111

Now look at that o_O You have the remainder as 2 and the division is 7. Note that in all, there were 8 shifts. I hope this helps! If you want a division code, feel free to ask

[ACagliano]

Oh, and so to do 2-byte multiplication, you can simply change the counter to 16, and then the input registers to 16-bit ones?

and yeah, the division routine would be great.

[Runer112]

For most of your z80 math routine needs, Z80 Bits is an excellent resource. It has a variety of multiplication, division, square root, and other z80 routines.

[calc84maniac]

Also, for future reference, it's a very bad idea to return after pushing something to the stack, since the processor will use the pushed value as the return address. So pushing af, returning, and popping af won't act like you think it will.

[Xeda112358]

Yes, Z80 Bits does indeed have some useful routines in there to look at

Oh, and so to do 2-byte multiplication, you can simply change the counter to 16, and then the input registers to 16-bit ones?

and yeah, the division routine would be great.

Yep Just remember, though, that 16-bit arithmetic sometimes takes a bit more work. For example, shifting HL left is as simple as add hl,hl, but shifting DE left, there is no add de,de instruction. So you have to do something like sla e \ rl d which is 3 bytes larger.

As for division, here is a routine:

Code: Select All | Copy To Clipboard

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

HL_Div_C: ;Inputs: ;     HL is the numerator ;     C is the denominator ;Outputs: ;     A is the remainder ;     B is 0 ;     C is not changed ;     DE is not changed ;     HL is the quotient ;        ld b,16        xor a Loop:          add hl,hl          rla          cp c          jr c,$+4            inc l            sub c          djnz Loop        ret

Luckily, division is pretty simple compared to multiplication. DEHL/C is much easier than DEHL*C.