--- title: "Restoring division algorithm and hardware" subject: "Computer Organization and Architecture" chapter: 5 key: "semester_5/computer_organization_and_architecture:restoring-division" source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/restoring-division site: BCT Engineering --- # Restoring division algorithm and hardware Computer Organization and Architecture · Chapter 5: Computer Arithmetic - Asked in: 2074 Asoj, 10 marks; 2069 Chaitra, 10 marks (asked 2 times) - Video: [Restoring Division Algorithm: Flowchart, Circuit & Example Explained | COA](https://www.youtube.com/watch?v=Ek-Ea2NnjeQ) — Engineering Funda - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/restoring-division - Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-5 ## Question Explain the restoring division algorithm, flowchart and hardware design with example. ## Short answer Restoring division shifts the dividend and partial remainder left, subtracts divisor; if negative, the old remainder is restored. It repeats n times. Hardware uses shift registers A and Q, an adder/subtractor, and a counter. For 7÷3, quotient = 2 (010), remainder = 1. ## Answer The restoring division algorithm divides an unsigned (or magnitude) dividend by a divisor using repeated shift and subtract. If a subtraction gives a negative result, the old value is restored, hence the name. #### Algorithm 1. Load A = 0, Q = dividend, M = divisor, SC = n. 2. Shift A and Q left by one bit (the MSB of Q goes into the LSB of A). 3. A = A − M. 4. If A < 0 (sign bit 1): set Q0 = 0 and **restore** A by adding M back (A = A + M). If A ≥ 0: set Q0 = 1. 5. SC = SC − 1. If SC ≠ 0 repeat from step 2. 6. At the end Q holds the quotient and A holds the remainder. #### Flowchart ```text +----------------------+ | A=0, Q=dividend | | M=divisor, SC=n | +----------+-----------+ v +----------------------+<--------------+ | Shift left A,Q | | | A = A - M | | +----------+-----------+ | v | A < 0 ? | Yes / \ No | v v | +----------+ +----------+ | | Q0 = 0 | | Q0 = 1 | | | A = A+M | | | | +----+-----+ +-----+----+ | +------+------+ | v | SC = SC - 1 | v | SC = 0 ? ---- No --------------+ | Yes v Quotient = Q, Remainder = A ``` #### Hardware ```text +-----------+ +---------+ | Divisor M | | Control | +-----+-----+ | & SC | | (n+1 bits) +----+----+ v | +------------------------+ | | (n+1)-bit adder/subtr. |<---------+ +-----------+------------+ | result / sign v +-----------------+ +-------------------+ | A (remainder) |<->| Q (dividend -> | | n+1 bits | | quotient) n bits| +-----------------+ +-------------------+ <---- shift left as one register ----> ``` - **A** (n+1 bits) starts at 0 and finally holds the remainder. - **Q** (n bits) starts with the dividend and finally holds the quotient; the new quotient bit enters at Q0 as Q shifts left. - **M** holds the divisor; the extra bit in A and the adder keep the sign of A − M. - The adder/subtractor does A − M (and A + M for restoring or non-restoring correction). - The sequence counter SC counts n steps. #### Example: 7 ÷ 3 Dividend = 7 = 111 (Q), divisor M = 3 = 0011 (n+1 = 4 bits), A = 0, n = 3. ```text Step Action A Q - Initial 0000 111 1 Shift left A,Q 0001 110 A = A - M (1 - 3 = -2) 1110 110 A<0: Q0=0, restore A 0001 110 2 Shift left A,Q 0011 100 A = A - M (3 - 3 = 0) 0000 100 A>=0: Q0=1 0000 101 3 Shift left A,Q 0001 010 A = A - M (1 - 3 = -2) 1110 010 A<0: Q0=0, restore A 0001 010 ``` **Answer: 7 ÷ 3: quotient = 2 (010), remainder = 1 (0001)** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In each step of restoring division, what is done first? A. Shift A and Q left, then A = A - M B. A = A - M then shift C. Restore A D. Clear Q Answer: A. Shift left (MSB of Q enters LSB of A) and subtract the divisor. (Key point: Step order) 2. If A < 0 after subtraction: A. Q0 = 0 and A = A + M B. Q0 = 1 and keep A C. Q0 = 1 and A = A + M D. Q0 = 0 and keep A Answer: A. A failed subtraction is undone and quotient bit 0 is recorded. (Key point: Restore rule) 3. Why is A (n+1) bits? A. Extra bit keeps the sign of A - M B. To hold the quotient C. To count steps D. To store M Answer: A. The sign bit shows whether the subtraction failed. (Key point: Register sizes) 4. At the end, where are quotient and remainder? A. Quotient in Q, remainder in A B. Quotient in A, remainder in Q C. Both in M D. Both in A Answer: A. Q was loaded with the dividend and receives quotient bits; A holds the remainder. (Key point: Results) 5. 7 / 3 gives: A. Quotient 2, remainder 1 B. Quotient 1, remainder 2 C. Quotient 3, remainder 0 D. Quotient 2, remainder 0 Answer: A. The trace ends with Q = 010 and A = 0001; 2 x 3 + 1 = 7. (Key point: Example 7 / 3) ## Related in Computer Organization and Architecture - [Non-restoring division with flowchart](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Anonrestoring-explain) — Computer Organization and Architecture, chapter 5, asked 3× - [Restoring division flowchart](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Arestoring-flowchart) — Computer Organization and Architecture, chapter 5 - [Signed division and non-restoring division](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Anonrestoring-division) — Computer Organization and Architecture, chapter 5 - [Restoring division of 31 by 13](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Arestoring-31-13) — Computer Organization and Architecture, chapter 5 - [Restoring division of 10 by 3](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Arestoring-10-3) — Computer Organization and Architecture, chapter 5 - [Restoring vs non-restoring division](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Arestoring-vs-nonrestoring) — Computer Organization and Architecture, chapter 5, asked 5× ## Related in other subjects - [Algorithm and flowchart help; Armstrong flowchart](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Aalgorithm-flowchart-armstrong) — Computer Programming, chapter 2 - [Algorithm and flowchart for largest](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Aalgorithm-flowchart-largest-n) — Computer Programming, chapter 2 - [Algorithm and flowchart: quadratic roots](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Aalgo-flowchart-quadratic) — Computer Programming, chapter 2 - [Algorithm and flowchart: distance between points](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Aalgo-flowchart-distance) — Computer Programming, chapter 2