Binary Division by Shift and Subtract

Basically the reverse of the mutliply by shift and add.



  • Set quotient to 0
  • Align leftmost digits in dividend and divisor
  • Repeat
    • If that portion of the dividend above the divisor is greater than or equal to the divisor
      • Then subtract divisor from that portion of the dividend and
      • Concatentate 1 to the right hand end of the quotient
      • Else concatentate 0 to the right hand end of the quotient
    • Shift the divisor one place right
  • Until dividend is less than the divisor
  • quotient is correct, dividend is remainder
  • STOP



What is the average number of operations needed to complete each of these algorithms, assuming the dividend has m digits in the representation and the divisor has n digits?


Modify this algorithm to produce the fractional part of the quotient.

Check out the tutorial section and get more help on-line (click here).


Last updated 2000/05/15
© J.A.N. Lee, 2000.