1

So I'm attempting to implement a multiplier in an assembly language program using the shift and add algorithm. I don't have a left shift instruction available in this ISA, but I do understand that adding a number to itself will shift the number left by one.

Let's say I want to multiply 5 * 15, which would be 101 multiplied by 1111. I understand that I need to multiply 5 by each partial bit in 15, but I'm confused on how I can access/work with these partial bits. From right to left, I multiply 1 by 101 to get 101, add a placeholder to shift left, and continue with each successive bit, getting 1010, 10100, and 101000. Then I add up these numbers to get 1001011 which is 75, the correct answer.

So, how would I be able to do this in assembly? I'm quite confused. Thanks!

theinfiniteride
  • 11
  • 1
  • What architecture are you programming for? – fuz May 16 '18 at 14:42
  • `[no] left shift […] in this ISA` adding a binary coded number to itself is equivalent to shifting it in direction of the more significant bits. If you "add with carry (from adding the multiplicand to the partial product)", you can get an extended size product without additional cost but the viability of an "early out". – greybeard May 21 '18 at 22:15

1 Answers1

1

Maybe a duplicate of How can I multiply and divide using only bit shifting and adding? which has some more detail.

on x86, given 15 in EDX, you'd do 

lea eax, [rdx + rdx*4]

to do EAX = (EDX<<2) + EDX = EDX*5, because 101 is (1<<2) + (1<<0).

See also How can I multiply a binary representation by ten using logic gates? on computerscience.SE for more background on multiply.

Is a shift instruction faster than an IMUL instruction? has some stuff.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847