Non-Restoring Division For Unsigned Integer

The non-restoring division algorithm is a faster method to divide binary numbers. Unlike traditional division, it avoids repeatedly adding back the divisor, making it more efficient for computers to perform.

• It uses repeated subtraction and addition to find the quotient bits.
• If subtraction gives a negative result, the algorithm just adds in the next step instead of fixing it.

Flow Chart of Non-Restoring Division For Unsigned Integer

Steps Involved in the Non-Restoring Division Algorithm

• Step-1: First the registers are initialized with corresponding values (Q = Dividend, M = Divisor, A = 0, n = number of bits in dividend)
• Step-2: Check the sign bit of register A
• Step-3: If it is 1 shift left content of AQ and perform A = A+M, otherwise shift left AQ and perform A = A-M (means add 2's complement of M to A and store it to A)
• Step-4: Again the sign bit of register A
• Step-5: If sign bit is 1 Q[0] become 0 otherwise Q[0] become 1 (Q[0] means least significant bit of register Q)
• Step-6: Decrements value of N by 1
• Step-7: If N is not equal to zero go to Step 2 otherwise go to next step
• Step-8: If sign bit of A is 1 then perform A = A+M
• Step-9: Register Q contains quotient and A contains remainder.

Example

Let’s divide the binary number 1011 (which is 11 in decimal) by 0011 (which is 3 in decimal) using the Non-Restoring Division Algorithm.

Initialization:

• Dividend (Q) = 1011
• Divisor (M) = 0011
• Accumulator (A) = 0000
• Number of bits (n) = 4

Step-by-Step Solution

1. Initial Setup:

• Q = 1011
• M = 0011
• A = 0000
• n = 4

2. First Iteration:

• Shift Left AQ: A = 0000, Q = 1011 becomes A = 0000, Q = 0110
• Perform Operation: A = A - M = 0000 - 0011 = 1101 (2's complement of 0011)
• Sign Bit of A: 1
• Update Q[0]: 0
• Decrement N: N = 3

3. Second Iteration:

• Shift Left AQ: A = 1101, Q = 0110 becomes A = 1010, Q = 1100
• Perform Operation: A = A + M = 1010 + 0011 = 1101
• Sign Bit of A: 1
• Update Q[0]: 0
• Decrement N: N = 2

4. Third Iteration:

• Shift Left AQ: A = 1101, Q = 1100 becomes A = 1011, Q = 1000
• Perform Operation: A = A - M = 1011 - 0011 = 1000 (2's complement of 0011)
• Sign Bit of A: 1
• Update Q[0]: 0
• Decrement N: N = 1

5. Fourth Iteration:

• Shift Left AQ: A = 1000, Q = 1000 becomes A = 0001, Q = 0000
• Perform Operation: A = A + M = 0001 + 0011 = 0010
• Sign Bit of A: 0
• Update Q[0]: 1
• Decrement N: N = 0

6. Final Adjustment:

• Sign Bit of A: 0 (no additional adjustment needed)
• Final Result: Quotient (Q) = 0011 (3 in decimal)
• Remainder (A) = 0010 (2 in decimal)