Digital Arithmetic
61
Table 3.4 Example 3.8.
1 0 1 0 1 1
Multiplicand
1 1
Multiplier
0 0 0 0 0 0
Start
+ 1 0 1 0 1 1
1 0 1 0 1 1
Result of first addition
0 1 0 1 0 1
1 (Result of addition shifted one bit to right)
+ 1 0 1 0 1 1
1 0 0 0 0 0 0
Result of second addition
0 1 0 0 0 0 0
01 (Result of addition shifted one bit to right)
subtract’ or the ‘repeated subtract and left-shift’ algorithm. These are briefly described and suitably
illustrated in the following sections.
3.6.1 Repeated Right-Shift and Subtract Algorithm
The algorithm is similar to the case of conventional division with decimal numbers. At the outset,
starting from MSB, we begin with the number of bits in the dividend equal to the number of bits in
the divisor and check whether the divisor is smaller or greater than the selected number of bits in
the dividend. If it happens to be greater, we record a ‘0’ in the quotient column. If it is smaller, we
subtract the divisor from the dividend bits and record a ‘1’ in the quotient column. If it is greater and
we have already recorded a ‘0’, then, as a second step, we include the next adjacent bit in the dividend
bits, shift the divisor to the right by one bit position and again make a similar check like the one made
in the first step. If it is smaller and we have made the subtraction, then in the second step we append
the next MSB of the dividend to the remainder, shift the divisor one bit to the right and again make a
similar check. The options are again the same. The process continues until we have exhausted all the
bits in the dividend. We will illustrate the algorithm with the help of an example. Let us consider the
division of (100110) 2 by (1100) 2 . The sequence of operations needed to carry out the above division
is shown in Table 3.5. The quotient = 011 and the remainder = 10.
Table 3.5 Binary division using the repeated right-shift and subtract algorithm.
Quotient
First step
0
1 0 0 1 1 0
Dividend
−1 1 0 0
Divisor
Second step
1
1 0 0 1 1
First five MSBs of dividend
−1 1 0 0
Divisor shifted to right
0 1 1 1
First subtraction remainder
Third step
1
0 1 1 1 0
Next MSB appended
−1 1 0 0
Divisor right shifted
0 0 1 0
Second subtraction remainder
61
Table 3.4 Example 3.8.
1 0 1 0 1 1
Multiplicand
1 1
Multiplier
0 0 0 0 0 0
Start
+ 1 0 1 0 1 1
1 0 1 0 1 1
Result of first addition
0 1 0 1 0 1
1 (Result of addition shifted one bit to right)
+ 1 0 1 0 1 1
1 0 0 0 0 0 0
Result of second addition
0 1 0 0 0 0 0
01 (Result of addition shifted one bit to right)
subtract’ or the ‘repeated subtract and left-shift’ algorithm. These are briefly described and suitably
illustrated in the following sections.
3.6.1 Repeated Right-Shift and Subtract Algorithm
The algorithm is similar to the case of conventional division with decimal numbers. At the outset,
starting from MSB, we begin with the number of bits in the dividend equal to the number of bits in
the divisor and check whether the divisor is smaller or greater than the selected number of bits in
the dividend. If it happens to be greater, we record a ‘0’ in the quotient column. If it is smaller, we
subtract the divisor from the dividend bits and record a ‘1’ in the quotient column. If it is greater and
we have already recorded a ‘0’, then, as a second step, we include the next adjacent bit in the dividend
bits, shift the divisor to the right by one bit position and again make a similar check like the one made
in the first step. If it is smaller and we have made the subtraction, then in the second step we append
the next MSB of the dividend to the remainder, shift the divisor one bit to the right and again make a
similar check. The options are again the same. The process continues until we have exhausted all the
bits in the dividend. We will illustrate the algorithm with the help of an example. Let us consider the
division of (100110) 2 by (1100) 2 . The sequence of operations needed to carry out the above division
is shown in Table 3.5. The quotient = 011 and the remainder = 10.
Table 3.5 Binary division using the repeated right-shift and subtract algorithm.
Quotient
First step
0
1 0 0 1 1 0
Dividend
−1 1 0 0
Divisor
Second step
1
1 0 0 1 1
First five MSBs of dividend
−1 1 0 0
Divisor shifted to right
0 1 1 1
First subtraction remainder
Third step
1
0 1 1 1 0
Next MSB appended
−1 1 0 0
Divisor right shifted
0 0 1 0
Second subtraction remainder