AlgoPlusAlgoPlus
Learn/Computer Architecture
Lesson

Binary Division

Long division in base 2 as hardware: the shift-subtract-restore loop that yields a quotient and remainder.

9 min read Watch it move Build it

Binary division is the long division you learned in school, done in base 2. Restoring division turns it into a tight hardware loop over three registers: A holds the running remainder (starts at 0), Q holds the dividend and fills up with the quotient, and M holds the divisor.

The shift-subtract-restore loop

Each round brings in one more bit of the dividend, tries to subtract the divisor, and decides a single quotient bit. If the trial subtraction goes negative, the divisor did not fit — so the value is restored (added back) and the quotient bit is 0; otherwise it fits and the bit is 1.

  1. 1Shift the combined A : Q register left by one bit.
  2. 2Subtract: A = A - M.
  3. 3If A is negative (top bit 1): set the new quotient bit Q0 = 0 and restore with A = A + M.
  4. 4If A is non-negative: set Q0 = 1 (no restore needed).
  5. 5Repeat for all n bits. At the end Q is the quotient and A is the remainder.
Divide 7 (Q = 0111) by 3 (M = 0011).  4 bits.

  step                         A      Q
  init                         0000   0111
   1  shift                    0000   1110
      A - M < 0   -> restore, Q0=0     0000   1110
   2  shift                    0001   1100
      A - M < 0   -> restore, Q0=0     0001   1100
   3  shift                    0011   1000
      A - M = 0   -> keep,    Q0=1     0000   1001
   4  shift                    0001   0010
      A - M < 0   -> restore, Q0=0     0001   0010

  quotient  Q = 0010 = 2
  remainder A = 0001 = 1     (7 ÷ 3 = 2 remainder 1)
"Restore" undoes a subtraction that overshot
The hardware always subtracts first and *checks the sign afterward*. A negative result means the divisor was too big for what is in A this round, so adding it back returns A to its pre-subtraction value — hence restoring division. That extra add is wasted work on every 0 quotient bit.
Non-restoring division skips the add-back
The faster non-restoring variant never restores: when a subtraction goes negative it simply adds the divisor on the *next* round instead of subtracting. It does one operation per step rather than sometimes two, trading a little extra control logic for speed.
OperationTimeSpace
Restoring division · shift, subtract, restore on negativesO(n) iterationsO(n) registers
Non-restoring division · no add-back; add/subtract alternatesO(n) iterationsO(n) registers
Check yourself
In restoring division, what happens when the trial subtraction A = A - M turns A negative?