Division
Paper & Pencil
1001 Quotient
Divisor 1000 1001010 Dividend
1000
10
101
1010
1000
10 Remainder

See how big a number can be subtracted, creating quotient bit on each step

Binary => 1 * divisor or 0 * divisor

Dividend = Quotient x Divisor + Remainder

3 versions of divide, successive refinement
Version 1

64bit Divisor reg, 64bit ALU, 64bit Remainder reg,
32bit Quotient reg
Divide Algorithm

Takes n+1 steps for nbit Quotient & Rem.
Observations

1/2 bits in divisor always 0
=> 1/2 of 64bit adder is wasted
=> 1/2 of divisor is wasted

Instead of shifting divisor to right, shift remainder to left?
The 1st step cannot produce a 1 in quotient bit do shift first and then
subtract  saves 1 iteration
Version 2

32bit Divisor reg, 32 bit ALU, 64bit Remainder reg,
32bit Quotient reg
Algorithm
Observations on Divide Version 2

Eliminate Quotient register by combining with Remainder as shifted left

Start by shifting the Remainder left as before.
Now loop contains only two steps because the shifting of the Remainder
register shifts both the remainder in the left half and the quotient in
the right half.
Combining the two registers and the new order of operations means that
the remainder will be shifted left one time too many.

Thus the final correction step must shift back only the remainder in the
left half of the register
Version 3

32bit Divisor reg, 32 bit ALU, 64bit Remainder reg,
Divide Algorithm Version 3
Observations on Divide Version 3

Same Hardware as Multiply: just need ALU to add or subtract, and 63bit
register to shift left or shift right

Signed Divides: Simplest is to remember signs, make positive, and complement
quotient and remainder if necessary

Note: Dividend and Remainder must have same sign

Note: Quotient negated if Divisor sign & Dividend sign disagree