Binary Multiply - Repeated Shift and Add

Repeated shift and add - starting with a result of 0, shift the second multiplicand to correspond with each 1 in the first multiplicand and add to the result. Shifting each position left is equivalent to multiplying by 2, just as in decimal representation a shift left is equivalent to multiplying by 10.

  • Set result to 0
  • Repeat
    • Shift 2nd multiplicand left until rightmost digit is lined up with leftmost 1 in first multiplicand
    • Add 2nd multiplicand in that position to result
    • Remove that 1 from 1st multiplicand
  • Until 1st multiplicand is zero
  • Result is correct
  • STOP

Consider the following problem in multiplication:

Click on the image to cycle through the multiplication steps.


What is the average number of operations needed to complete each of these multiplication algorithms when the two numbers to be multiplied have n digits in their representation?


Last updated 2001/10/08
© J.A.N. Lee, 2000-2001.