62
Digital Electronics
Table 3.6 Binary division using the repeate subtract and left-shift
algorithm.
Quotient
1 0 0 1
1 0
−1 1 0 0
0
1 1 0 1
Borrow exists
+1 1 0 0
1 0 0 1
Final carry ignored
1 0 0 1 1
Next MSB appended
−1 1 0 0
1
0 1 1 1
No borrow
0 1 1 1 0
Next MSB appended
−1 1 0 0
1
0 0 0 1 0
No borrow
3.6.2 Repeated Subtract and Left-Shift Algorithm
The procedure can again be best illustrated with the help of an example. Let us consider solving the
above problem using this algorithm. The steps needed to perform the division are as follows. We begin
with the first four MSBs of the dividend, four because the divisor is four bits long. In the first step, we
subtract the divisor from the dividend. If the subtraction requires borrow in the MSB position, enter a
‘0’ in the quotient column; otherwise, enter a ‘1’. In the present case there exists a borrow in the MSB
position, and so there is a ‘0’ in the quotient column. If there is a borrow, the divisor is added to the
result of subtraction. In doing so, the final carry, if any, is ignored. The next MSB is appended to the
result of the first subtraction if there is no borrow, or to the result of subtraction, restored by adding
the divisor, if there is a borrow. By appending the next MSB, the remaining bits of the dividend are
one bit position shifted to the left. It is again compared with the divisor, and the process is repeated.
It goes on until we have exhausted all the bits of the dividend. The final remainder can be further
processed by successively appending 0s and trying subtraction to get fractional part bits of the quotient.
The different steps are summarized in Table 3.6. The quotient = 011 and the remainder = 10.
Example 3.9
Use the ‘repeated right-shift and subtract’ algorithm to divide (110101) 2 by (1011) 2 . Determine both
the integer and the fractional parts of the quotient. The fractional part may be determined up to three
bit places.
Solution
The sequence of operations is given in Table 3.7. The operations are self-explanatory.
• The quotient = 100.110.
• Now, (110101) 2 = (53) 10 and (1011) 2 = (11) 10 .
• (53) 10 divided by (11) 10 gives (4.82) 10 .
• (100.110) 2 = (4.75) 10 , which matches with the expected result to a good approximation.
Digital Electronics
Table 3.6 Binary division using the repeate subtract and left-shift
algorithm.
Quotient
1 0 0 1
1 0
−1 1 0 0
0
1 1 0 1
Borrow exists
+1 1 0 0
1 0 0 1
Final carry ignored
1 0 0 1 1
Next MSB appended
−1 1 0 0
1
0 1 1 1
No borrow
0 1 1 1 0
Next MSB appended
−1 1 0 0
1
0 0 0 1 0
No borrow
3.6.2 Repeated Subtract and Left-Shift Algorithm
The procedure can again be best illustrated with the help of an example. Let us consider solving the
above problem using this algorithm. The steps needed to perform the division are as follows. We begin
with the first four MSBs of the dividend, four because the divisor is four bits long. In the first step, we
subtract the divisor from the dividend. If the subtraction requires borrow in the MSB position, enter a
‘0’ in the quotient column; otherwise, enter a ‘1’. In the present case there exists a borrow in the MSB
position, and so there is a ‘0’ in the quotient column. If there is a borrow, the divisor is added to the
result of subtraction. In doing so, the final carry, if any, is ignored. The next MSB is appended to the
result of the first subtraction if there is no borrow, or to the result of subtraction, restored by adding
the divisor, if there is a borrow. By appending the next MSB, the remaining bits of the dividend are
one bit position shifted to the left. It is again compared with the divisor, and the process is repeated.
It goes on until we have exhausted all the bits of the dividend. The final remainder can be further
processed by successively appending 0s and trying subtraction to get fractional part bits of the quotient.
The different steps are summarized in Table 3.6. The quotient = 011 and the remainder = 10.
Example 3.9
Use the ‘repeated right-shift and subtract’ algorithm to divide (110101) 2 by (1011) 2 . Determine both
the integer and the fractional parts of the quotient. The fractional part may be determined up to three
bit places.
Solution
The sequence of operations is given in Table 3.7. The operations are self-explanatory.
• The quotient = 100.110.
• Now, (110101) 2 = (53) 10 and (1011) 2 = (11) 10 .
• (53) 10 divided by (11) 10 gives (4.82) 10 .
• (100.110) 2 = (4.75) 10 , which matches with the expected result to a good approximation.