This example follows the algorithm given in the Patterson and Hennessey book on page 202. We are doing integer division of two positive numbers. If we want to divide a negative by a positive, or a positive by a negative, or a negative by a negative, we can still work with positives and adjust the sign (in the first two cases) later. The terminology for the pieces of data are Dividend ---------- = Quotient + Remainder Divisor and we will find the Quotient and Remainder for a given Dividend and Divisor. Suppose that we want to find 1001010 / 1000. In 8 bits: Dividend = 01001010 Divisor = 00001000 We use Divisor, Quotient, and Remainder frequently, and will represent these as D, Q, and R, respectively. After step 0, we do not reference Dividend. We will use twice the precision, i.e. since this example has 8 bit values, we will find a Quotient and Remainder of 16 bits each. An important note is that the divisor extends to 16 bits and starts with the original 8 bits in the upper part. 0. R = Remainder = Dividend = 00000000 01001010 D = Divisor = 00001000 00000000 Q = Quotient = 00000000 00000000 count = 0 (decimal) 1. R = R - D R = 00000000 01001010 - 00001000 00000000 = 00000000 01001010 + 11110111 11111111 + 1 00000000 01001010 R 11110111 11111111 1's comp D + 1 +1 to get 2's comp D -------------------- 0 00001111 1111111 carry bits 00000000 01001010 R 11110111 11111111 1's comp D + 1 +1 to get 2's comp D -------------------- 11111000 01001010 = R - D 2. Is R >= 0? No: R = R + D, so R = 00000000 01001010 Q = left(Q), Q(0) = 0 so Q = 00000000 00000000 3. D = right(D) = 00000100 00000000 4. count++ count = 1 if count <= 8, goto 1 1. R = R - D R = 00000000 01001010 - 00000100 00000000 = 11111011 10110110 2. Is R >= 0? No: R = R + D, so R = 00000000 01001010 Q = left(Q), Q(0) = 0 so Q = 00000000 00000000 3. D = right(D) = 00000010 00000000 4. count++ count = 2 if count <= 8, goto 1 1. R = R - D R = 00000000 01001010 - 00000010 00000000 = 11111101 10110110 2. Is R >= 0? No: R = R + D, so R = 00000000 01001010 Q = left(Q), Q(0) = 0 so Q = 00000000 00000000 3. D = right(D) = 00000001 00000000 4. count++ count = 3 if count <= 8, goto 1 1. R = R - D R = 00000000 01001010 - 00000001 00000000 = 11111110 10110110 2. Is R >= 0? No: R = R + D, so R = 00000000 01001010 Q = left(Q), Q(0) = 0 so Q = 00000000 00000000 3. D = right(D) = 00000000 10000000 4. count++ count = 4 if count <= 8, goto 1 1. R = R - D 00000000 01001010 - 00000000 10000000 R = 11111111 10110110 2. Is R >= 0? No: R = R + D, so R = 00000000 01001010 Q = left(Q), Q(0) = 0 so Q = 00000000 00000000 3. D = right(D) = 00000000 01000000 4. count++ count = 5 if count <= 8, goto 1 1. R = R - D 00000000 01001010 - 00000000 01000000 R = 00000000 00001010 2. Is R >= 0? Yes: Q = left(Q), Q(0) = 1 so R = 00000000 00001010 so Q = 00000000 00000001 (decimal 1) 3. D = right(D) = 00000000 00100000 4. count++ count = 6 if count <= 8, goto 1 1. R = R - D 00000000 00001010 - 00000000 00100000 R = 11111111 11010110 2. Is R >= 0? No: R = R + D, Q = left(Q), Q(0) = 0 so R = 00000000 00001010 so Q = 00000000 00000010 (decimal 2) 3. D = right(D) = 00000000 00010000 4. count++ count = 7 if count <= 8, goto 1 1. R = R - D 00000000 00001010 - 00000000 00010000 R = 11111111 11100110 2. Is R >= 0? No: R = R + D, Q = left(Q), Q(0) = 0 so R = 00000000 00001010 so Q = 00000000 00000100 (decimal 4) 3. D = right(D) = 00000000 00001000 4. count++ count = 8 if count <= 8, goto 1 1. R = R - D 00000000 00001010 - 00000000 00001000 R = 00000000 00000010 2. Is R >= 0? Yes: Q = left(Q), Q(0) = 1 so R = 00000000 00000010 so Q = 00000000 00001001 (decimal 9) 3. D = right(D) = 00000000 00000100 4. count++ count = 9 if count <= 8, goto 1 // ********************************************* If count <= 8, goto 1. Thus, stop here. R = 00000000 00000010 Q = 00000000 00001001 (decimal 9) 9 * 8 = 72 74/8 = 9 with 2 remainder // *********************************************