The MASM Forum

Multiplying by shifting

shift left 1 time => x2
Shift left 2 time => x4
Shift left 3 time => x8


Data want to multiply
10110110 = data1 = B6H  ; User enter, can be different
01101010 = data2 = 6AH ; User also enter, can be different

2+8+32+64


0000000101101100 <- shl 1 = x2
0000010110110000 <- shl 3 = x8
0001011011000000 <- shl 5 = x32
0010110110000000 <- shl6  = x64
0100101101011100 = 4B5C



======================= MY CODE=========================
org 100h

mov bx, 6      ; data1 test value
mov dx, 15     ; data2 test value

;=====================================================
mov cx, 8      ; loop counter

    loop1:   
       
        shr dx, 1  ; shift right 1time       
        jc loop2   ; if carry is one jump to loop2
       

        loop loop1

ret     


;===================================================== 
     
    loop2:       
        shl bx, 1       
        add ax, bx ; 
        jmp loop1
    loop loop2

it's very simple, really
we'll call one operand the multiplier, and the other, the multiplicand

if we look at the multiplicand
10110110
there are set bits and cleared bits
bit 0 represents 2⁰ (=1)
bit 1 represents 2¹ (=2)
bit 2 represents 2² (=4), and so on

so, we would start by clearing the accumulator
then, we test bit 0 of the multiplicand
if the bit is set, we add the multiplier to the accumulator
otherwise, we do not add it

now, shift-left the multiplier
test bit 1 of the multiplicand
if the bit is set, we add 2Xmultiplier to the accumulator
otherwise, we do not add it

shift-left the multiplier again
test bit 2 of the multiplicand
if the bit is set, we add 4Xmultiplier to the accumulator
otherwise, we do not add it

and you continue until you have tested each bit in the multiplicand

to the left, we have the muliplier  X1, X2, X4, X8, X16, X32, X64, X128
to the right, we make an X mark for each bit that is set in the mulitplicand

0000000001101010     multiplicand bit 0 = 0
0000000011010100  X
0000000110101000  X
0000001101010000
0000011010100000  X
0000110101000000  X
0001101010000000
0011010100000000  X  multiplicand bit 7 = 1

now, we remove the ones that don't have an X, and add them up

0000000011010100  X
0000000110101000  X
0000011010100000  X
0000110101000000  X
0011010100000000  X
----------------
0100101101011100

Quote from: dedndave on October 31, 2013, 01:06:39 PM
it's very simple, really
we'll call one operand the multiplier, and the other, the multiplicand

if we look at the multiplicand
10110110
there are set bits and cleared bits
bit 0 represents 2⁰ (=1)
bit 1 represents 2¹ (=2)
bit 2 represents 2² (=4), and so on

so, we would start by clearing the accumulator
then, we test bit 0 of the multiplicand
if the bit is set, we add the multiplier to the accumulator
otherwise, we do not add it

now, shift-left the multiplier
test bit 1 of the multiplicand
if the bit is set, we add 2Xmultiplier to the accumulator
otherwise, we do not add it

shift-left the multiplier again
test bit 2 of the multiplicand
if the bit is set, we add 4Xmultiplier to the accumulator
otherwise, we do not add it

and you continue until you have tested each bit in the multiplicand

I apologize I didn't include this earlier:  what if data1 and data2 is dynamic ?

if you follow the text, the concept will apply to variable operands

make a loop
use a register to walk a 1 bit (1, 2, 4, 8, 16, 32, 64, 128)
when that hits 256, exit the loop

zero an accumulator - you can make that a 16-bit register
use a register for the multiplier - set the high byte to 0
use a register for the multiplicand - set the high byte to 0

pass through the loop
test the multiplicand against the walking 1 (TEST instruction)
if it's not zero, you add the multiplier to the accumulator
if it is zero, you jump around the ADD instruction

shift-left the multiplier
shift-left the walking 1
if the walking 1 becomes 256, there are no more bits to test in the multiplicand - exit the loop
otherwise, go back to where it says "pass through the loop"

when you're done, the accumulator will hold the product

        mov     cx,1       ;CX = walking 1
        mov     ax,0       ;AX = accumulator
        mov     dl,data1   ;DL = multiplicand
        mov     dh,0       ;DX = multiplicand
        mov     bl,data2   ;BL = multiplier
        mov     bh,0       ;BX = multiplier

loop00: test    cx,dx
        jz      loop01

        add     ax,bx

loop01: shl     bx,1
        shl     cx,1
        cmp     cx,256
        jb      loop00

;AX = product

Thank you sir !!!!!

Hi X86student:

You can can also use the carry flag.
STC; set the carry instructiom.
Just use a rotate bit instruction that
does not discard the carry bit.