Binary Division

Binary Division

• The division process for binary numbers is similar to the decimal numbers. Fig. 2.5.1 shows binary division process.

• In the division process, first the bits of the dividend are examined from left to right, until the set of bits examined represents a number greater than or equal to the divisor.

• Until this condition occurs, 0's are placed in the quotient from left to right.

• When the condition is satisfied, a 1 is placed in the quotient and the divisor is subtracted from the partial dividend. The result is referred to as a partial remainder.

• From this point onwards, the division process is required. In each repetition cycle, additional bits from the dividend are brought down to the partial remainder until the result is greater than or equal to the divisor and the divisor is subtracted from the result to produce a new partial remainder.

• The process continues until all the bits of the dividend are brought down and result is still less than the divisor.

 

1. Restoring Division Algorithm

• Fig. 2.5.2 shows the hardware for implementation of restoring division.

• It consists of n+1‒bit binary adder, shift, add and subtract control logic and registers A, B, and Q.

• As shown in Fig. 2.5.2 divisor and dividend are loaded into register B and register Q, respectively. Register A is initially set to zero. The division operation is then had carried out.

• After the division is complete, the n‒bit quotient is in register Q and the remainder is in register A.

Division operation steps:

1. Shift A and Q left one binary position.

2. Subtract divisor (i.e. add 2's complement of divisor (B)) from A and place answer back in A (A← A − B).

3. If the sign bit of A is 1, set Q₀ to 0 and add divisor back to A (that is, restore A); Otherwise, set Q₀ to 1.

4. Repeat steps 1, 2, and 3 n times.

A flowchart for division operation is as shown in Fig. 2.5.3.

Example: 1

Perform the division of following numbers using restoring division algorithm.

Dividend = 1 0 1 0

Divisor = 0 0 1 1

Solution:

Fig. 2.5.2 shows steps involved in the above binary division.

Example: 2

 Divide the following unsigned numbers using restoring division method

Dividend = 1000, Divisior = 11.

Solution :

Example: 3

Perform the following division using restoring division algorithm :

Dividend = 1001

Divisor = 0101.

Solution :

Example: 4

Perform 1100+ 11 using restoring algorithm.

Solution:

Restoring Division: Q← Dividend (1100), B← Divisor (11).

2's Complement of divisor (B) = 11101.

Example: 5

Using restoring division algorithm solve the following:

Dividend = 17.

Divisor = 03

Solution :

Dividend = 17 = 17 = (10001)₂ → Q

Divisor = 03 = 03 = (00011)₂ → B

2's complement of B = (111101)₂

• The division algorithm just discussed needs restoring register A after each unsuccessful subtraction. (Subtraction is said to be unsuccessful if the result is negative). Therefore it is referred to as restoring division algorithm.

Example: 6

Perform restoring division when divisor V = 3 and dividend D = 7. Also give the results for all possible combinations of signs of D and V.

Solution:

The restoring division algorithm assumes positive signs of D and V.

Remainder = (0001)₂ = 1 and Quotient = (0010)₂ = 2

• In the division operation, the magnitudes of quotient (Q) and remainder (R) are unaffected by the input signs. The signs of Q and R are easily derived from the signs of D and V using expression: D=Q × V + R

• The signs of Q and R for all possible combinations of signs of D and V are as FB follows:

D =7,      V=3    ⇒    Q=2,    R=1

D =7,      V= ‒3    ⇒    Q= ‒2,    R=1

D = ‒7,      V=3    ⇒    Q= ‒2,    R= ‒1

D = ‒7,      V= ‒3    ⇒    Q=2,    R= ‒1

 

2. Non‒Restoring Division

• Consider the sequence of operations that takes place after the subtraction operation in the restoring algorithm.

If A is positive

Shift left and subtract divisor →2A ‒ B

If A is negative

Restore → A+B

Shift left and subtract divisor→ 2 (A+B) – B

= 2A+B

• Looking at the above operations we can write following steps for non‒restoring algorithm.

Step 1: If the sign of A is 0, shift A and Q left one bit position and subtract divisor from A; otherwise, shift A and Q left and add divisor to A. If the sign of A is 0, set Q₀ to 1; otherwise, set Q₀ to 0.

Step 2: Repeat steps 1 and 2 for n times.

Step 3: If the sign of A is 1, add divisor to A.

Note: Step 3 is required to leave the proper positive remainder in A at the end of n cycles.

• A flowchart for non‒restoring division operation is as shown I Fig. 2.5.10.

Example: 7

Perform the division of following numbers using non‒restoring division algorithm:

Dividend = 1 0 1 0

Divisor = 0 0 1 1.

Solution:

Fig. 2.5.11 shows steps involved in the non-restoring binary division.

In this example, after 4 cycles A is positive and hence step 3 is not required.

Example: 8

Perform the division of following numbers using non‒restoring division algorithm:

Dividend = 1 0 1 1

Divisor = 0 1 0 1.

Solution :

• Fig. 2.5.12 shows steps involved in the non‒restoring binary division.

• The hardware shown in Fig. 2.5.2 can also be used to perform non‒restoring. algorithm. There is no simple algorithm for signed division. In signed division, the operands are pre‒processed to transform them into positive values. Then using one of the algorithms just discussed quotients and remainders are calculated. The quotients and remainders are then transformed to the correct signed values.

Example: 9

Divide the following unsigned numbers using non‒restoring division method.

Dividend = (15)₁₀, Divisor = (2)₁₀

Solution :

Dividend = (15)₁₀ = (01111)₂

Divisor = (2)₁₀ = (00010)₂

Example: 10

Perform division operation on the following numbers using the non‒restoring division algorithm.

Dividend = 1101 Divisor = 0100

Solution :

Example: 11

Perform 1100 + 11 using non‒restoring algorithm.

Solution:

Non‒Restoring Division: Q← Dividend (1100), B← Divisor (11).

Complement and divisor (B) = 11101.

Example: 12

Perform division of the following numbers using restoring and non restoring division algorithm.

A : 1100 and B : 0100

Solution:

A = 1100    B = 0100 (Using restoring division)

Note: Subtract B means add B in 2's complement form.

A = 1100     B = 0100 (Using non restoring division)

 

3. Comparison between Restoring and Non‒Restoring Division Algorithm

Restoring

1. Needs restoring of register A if the result of subtraction is negative.

2. In each cycle content of register A is first shifted left and then divisor is subtracted from it.

3. Does not need restoring of remainder,

4. Slower algorithm.

Non‒restoring

1. Does not need restoring.

2. In each cycle content of register A is first shifted left and then divisor is added or subtracted with the content of register A depending on the sign of A.

3. Needs restoring of remainder if remainder is negative.

4. Faster algorithm.

Examples for Practice

Example: 13

Perform the following division using non‒restoring division algorithm.

Dividend = 1101, Divisor = 11.

Example: 14

Perform the following division using restoring division algorithm.

Dividend = 1100 Divisor = 0100.

Example: 15

Perform the following division using non‒restoring division algorithm.

Dividend = 1000, Divisor =11.

Example: 16

Compare restoring and non‒restoring division algorithm. Perform the division using restoring division algorithm.

Dividend = 17; Divisor = 03.

Example: 17

Draw flowchart of Booth's algorithm for non‒restoring unsigned division and divide the following unsigned numbers and justify your answer.

Dividend = 1011; Divisor = 0011.

Review Questions

1. Draw the flowchart for restoring division algorithm.

2. Draw the flowchart for non‒restoring division algorithm.

3. Compare restoring and non‒restoring division algorithm.

4. Write restoring unsigned division algorithm.

5. Perform the following division using restoring and nonrestoring division algorithm.

Dividend = 1100 Divisor = 0011

6. Perform following division using restoring and non‒restoring algorithm.

Dividend = 1010 and Divisor = 0011.

7. Perform division of the following numbers using restoring and non restoring division algorithm. A: 1100 and B: 0100