Multiplying works just like long multiplication you do on pencil and paper,
but you just use binary. Makes it pretty easy.
Take a look,
10010100 or 148
x 00010010 x 18
----------- -----
00000000 1184
10010100 + 148
00000000
00000000
10010100
00000000
00000000
+ 00000000
================= ====
000101001101000 or 2664
The way I actually implemented it was like this:
var.lo=multiplicand (i.e. 148)
var.hi=0
W=multiplier (i.e. 18)
I right shift the LSB out of var.
Then 8 times, I do this:
If the bit is set, I add W to the high part.
Right shift the high part (which will shift in overflow from the add)
Right shift the low part. The low part will, as I pull bits out from the
right, will get new bits in from the left from the high part, so IOW, the
multiplicand is being replaced, bit by bit, with the low byte of the answer.
Here's what would happen in the 148 x 14 case:
W=18 (00010010)
lo=148 (10010100)
hi=0
rrf lo (?1001010) C=0
no carry
rrf hi & lo (0000000 0?100101) C=0
(answer so far is 0)
no carry
rrf hi & lo (0000000 00?10010) C=1
(answer so far is 0)
carry! hi+=W (00010010)
rrf hi & lo (00001001 000?1001) C=0
(answer so far is 18*4 or 72)
no carry
rrf hi & lo (00000100 1000?100) C=1
carry! hi+=W (00010110)
rrf hi & lo (00001011 01000?10) C=0
(answer so far is 18*4+18*16 or 360)
no carry
rrf hi & lo (00000101 101000?1) C=0
no carry
rrf hi & lo (00000010 1101000?) C=1
carry! hi+=W (00010100)
rrf hi & lo (00000001 01101000) C=?
(answer so far is 18*4+18*16+18*128 or 2664)
See how easy that was?
How about division... A little more complicated, but the same basic idea.
Pretty much binary long division.
Think of show 2664 / 18 would work in real life:
___148__
18 ) 2664
-18
--
86
-72
--
144
-144
---
0
Now in binary:
______10010100__
10010 ) 101001101000
-10010
-----
10110
-10010
-----
10010
-10010
-----
0
Interested:
Comments:
;=== 8x8 bit Multiplier ================ 1/18/08 ===== ERM ===========
;
;This code uses rotate right and add to mimic the process of long-hand
;multiplication as learned and practiced by middle aged and up
;in the bygone days of slide rules and lookup tables.
;
; 10010110 muliplicand 0x96, d'150
; 01101100 x multiplier 0x6c d'108
; ________________
; 00000000 bit 0 in multiplier is 0
; 00000000 bit 1 in multiplier is 0
; 10010110 bit 2 in multiplier is 1
; 10010110 bit 3 in multiplier is 1
; 00000000 bit 4 in multiplier is 0
; 10010110 bit 5 in multiplier is 1
; 10010110 bit 6 in multiplier is 1
; 00000000 bit 7 in multiplier is 0
; _____________________________
; 011111101001000 Add up the results, d'16,200
; 011 1111 0100 1000 0x3f48
;
;The 16 bit result is stored in 2 bytes. We "right rotate" the
;result as we go which is in effect "left" shifting our result
;as we do in long-hand multiplication.
;
;Before calling the subroutine " mpy ", the multiplier should
;be placed in register named " mulplr ", and the multiplicand in
;" mulcnd " . The 16 bit result is stored in registers named
;H_byte & L_byte.
;
;Written and tested with MPLAB IDE v8.00
;--------------------------------------------------------------------
list p=16F877A
#INCLUDE <P16F877A.INC>
__config h'3f32'
radix hex
;===================================================================
; ***** REGISTER EQUATES *****
;===================================================================
CBLOCK 0x20
count ;used to loop through multiplier 8 times
mulcnd ;stores multiplicand
mulplr ;stores multiplier
mulplrC ;reserves a copy of the multiplier
H_byte ;stores high bits of result
L_byte ;stores low bits of result
ENDC
;
;-----------------------------------------------------
org 0x000
goto main
org 0x005
;=====================================================================
; ***** TEST PROGRAM *****
;=====================================================================
main movlw 0x96
movwf mulplr ; multiplier (in mulplr) 0x96, d'150
movwf mulplrC
movlw 0x6c
movwf mulcnd ; multiplicand(in mulcnd ) 0x6a, d'106
;
call mpy_F ; The result 0x96*0x6c = 0x3f48 is in
; ; locations H_byte & L_byte
; ; 011 1111 0100 1000
self goto self
;
;====================================================================
; ***** SUBROUTINES *****
;====================================================================
;---------------------------------------------------------------------
; ***** MULTIPLY ROUTINE *****
;---------------------------------------------------------------------
mpy_F clrf H_byte ;Clear high byte of result (product)
clrf L_byte ;Clear low byte of result (product)
bsf count,3 ;Set counter value 0x08
movf mulcnd,W ;Move the multiplicand to W reg.
bcf STATUS,C ;Clear the carry bit in the status reg.
; ;so we don't rotate a misleading bit
; ;into H_byte.
; -----------------
; Multiply Loop
; -----------------
mult btfsc mulplr,0 ;Check rightmost bit in multiplier.
addwf H_byte,f ;If set add mulcnd (w) to H_byte.
;If clear, don't add, just rotate right.
rrf H_byte,f ;Rotate carry out of H_byte.
rrf L_byte,f ;Rotate carry into L_byte.
rrf mulplr ;Move next bit to rightmost position.
bcf STATUS,C ;Clear the carry so we don't move a
;misleading bit into H_byte.
decfsz count ;Decrement loop counter.
goto mult ;Repeat 8 times. Once for each bit
retlw 0 ;in the multiplier.
;--------------------------------------------------------------------
end ;End directive stops assembly here.