Division restoring and non-restoring techniques

💡 First, What Does Division Mean in Binary?

Division in binary works exactly like division in decimal —
we repeatedly subtract the divisor from the dividend and find how many times it “fits in.”

But here’s the twist:
In binary, numbers only have 0 and 1, so each step is about deciding —

“Can the divisor fit here (1), or not (0)?”

To make this efficient, computers use special hardware algorithms — and the two most common are Restoring Division and Non-Restoring Division.

---

⚙️ The Main Idea Behind Both Techniques

Both methods follow the same overall pattern:

1. Start with a dividend (the number being divided) and a divisor (the number dividing it).
2. Shift bits to the left (similar to bringing down digits in long division).
3. Subtract or add the divisor depending on the situation.
4. Set quotient bits (0 or 1) based on whether the result was positive or negative.
5. Repeat for each bit of the dividend.

The only difference is in how they handle negative results — that’s what separates restoring from non-restoring division.

---

🧮 Example Numbers

Let’s take a simple example:
We’ll divide 13 (1101) by 3 (0011) in binary.

We’ll go step-by-step to understand both techniques.

---

🔹 Restoring Division Technique

The restoring division method is like a cautious learner.
Whenever it makes a mistake (gets a negative result), it goes back and “restores” things before trying again.

🧩 Steps to Understand

1. Initialize:

• Put the dividend in a register called Q.
• The divisor in another register called M.
• A third register A (accumulator) starts with 0.

   A = 0000
   Q = 1101  (Dividend)
   M = 0011  (Divisor)

2. Shift Left:
   Shift A and Q together to the left by one bit.
3. Subtract Divisor (A – M):

• If result ≥ 0 → set Q₀ = 1
• If result < 0 → restore A by adding M back, and set Q₀ = 0

2. Repeat the process for all bits in Q.
3. When done:

• Q = Quotient
• A = Remainder

---

⚙️ Example Steps (Simplified View)

Step	Operation	A	Q	Action
0	Initialize	0000	1101
1	Shift left	0001	101_
2	A – M	0001 – 0011 = 1110 (negative)		Restore A, Q₀ = 0
3	Shift left	1110	1010
4	A – M	1110 – 0011 = 1011 (negative)		Restore A, Q₀ = 0
5	Shift left	1011	0100
6	A – M	1011 – 0011 = 1000 (negative)		Restore A, Q₀ = 0
7	Shift left	1000	1000	Done

At the end:

Quotient (Q)  = 0100 (4 in decimal)
Remainder (A) = 0001 (1 in decimal)

✅ So, 13 ÷ 3 = 4 remainder 1 — correct!

---

🧭 Restoring Division Diagram

       +-----------------------------------+
       |           CONTROL LOGIC           |
       +-----------------------------------+
        |           |               |
        v           v               v
   +---------+  +---------+    +----------+
   |   A     |  |   Q     |    |    M     |
   |Accumulator| |Quotient|    |Divisor   |
   +---------+  +---------+    +----------+
        ^           |
        |           v
      (Subtract / Restore)

Here, the control logic decides whether to subtract or restore based on the sign of A after subtraction.

---

🔸 Non-Restoring Division Technique

The non-restoring division method is like a confident student —
it doesn’t go back to “fix” things immediately when something goes wrong.
Instead, it adjusts in the next step automatically.

This makes it faster, since we skip the “restore” step.

---

🧩 Steps to Understand

1. Initialize A = 0, Q = Dividend, M = Divisor
2. Shift A and Q left by 1 bit
3. * If the sign of A is positive → Subtract M (A = A – M)

• If the sign of A is negative → Add M (A = A + M)

1. * If result ≥ 0 → set Q₀ = 1

• If result < 0 → set Q₀ = 0

1. Repeat for all bits
2. If A < 0 at the end, restore A once by adding M.

---

⚙️ Example (Simplified)

Step	A	Q	Operation	Action
0	0000	1101	Initialize
1	Shift left	0001	Subtract M	A = 0001 – 0011 = 1110 (neg), Q₀ = 0
2	Shift left	1110	Add M	A = 1110 + 0011 = 0001 (pos), Q₀ = 1
3	Shift left	0001	Subtract M	A = 0001 – 0011 = 1110 (neg), Q₀ = 0
4	Shift left	1110	Add M	A = 1110 + 0011 = 0001 (pos), Q₀ = 1

Final results:

Q = 0101  (5 in decimal)
A = 0001  (Remainder 1)

✅ So 13 ÷ 3 = 4 remainder 1 — same answer, fewer steps!

---

⚙️ Non-Restoring Division Diagram

       +----------------------------------+
       |          CONTROL LOGIC           |
       +----------------------------------+
           |                 |
           v                 v
   +-------------+      +------------+
   |  A Register |<---->|   Adder    |
   +-------------+      +------------+
           |                 ^
           |                 |
           v                 v
   +-------------+      +------------+
   |  Q Register |      |  M Register|
   +-------------+      +------------+

The control logic checks the sign of A after every operation and decides whether to add or subtract in the next step.

---

🧠 Key Difference Between the Two

Feature	Restoring Division	Non-Restoring Division
Method	Restores A if subtraction gives negative	Adjusts automatically next step
Speed	Slower (extra restore step)	Faster
Hardware	Simpler control	Slightly more complex control
Example	Step-by-step cautious approach	Confident “adjust later” method
Use	Early processors	Modern processors & ALUs

---