Computer Arithmetic 73
We continue our scanning from left to right and next encounter with the left most two digits of the
dividend, i.e., 01 (underlined). Again it is found to be less than the divisor, which forces us to add
another zero in the quotient [Figure 4.14 (c)]. As we continue our scanning, we next meet with 010 part
of the dividend (its three leading digits) and nd that it is equal (even greater would do) to the divisor.
At this point, we may add a 1 in the place of quotient, making it 001, write the divisor below the divi-
dend and perform a subtraction. The remainder in this case is 000. We then write the next considerable
digit of the dividend, i.e., 1 at the right side of the remainder [shown by a vertical downward arrow in
Figure 4.14 (d)].
As the last step, we nd that the present remainder 0001 is less than divisor. Therefore, we add another
zero with the quotient making it 0010 and complete our process. Thus, nally, we get a quotient of 0010
(2 in decimal) and a remainder 0001 (1 in decimal) by our process, matching with our expectations.
An algorithm may be developed for the above method to divide unsigned integers. However, this
method would not be applicable for signed integers, expressed in two’s complement form. For that pur-
pose, we have to adopt another algorithm (William Stallings, 2009), as described below.
4.6 DIVISION OF SIGNED INTEGERS
Just like Booth’s algorithm for multiplication of signed binary integers, the division algorithm also uses
several locations. In this case, a joint left-shift of two locations has to be performed. In the following
sub-sections we describe all relevant details, discuss about the algorithm and then solve a few examples
using this algorithm.
4.6.1 Locations and Counters
To implement this algorithm for division of signed integers, we would need four locations; all should be
n -bit wide, where ‘ n ’ is the number of bits being considered for divisor and dividend. In other words, for
4-bit numbers, we shall need 4-bit wide locations, for 8-bit numbers, we shall need 8-bit wide locations
and so on. We designate these four locations as V, R, D and C, as indicated in Figure 4.15 .
Figure 4.15 Locations involved for division algorithm
Location V, is to contain n -bit divisor. If the divisor is negative, its two’s complement form should
be loaded in V. We shall only use its content, which would remain unchanged till the completion of the
process. Location C is the n -bit down counter and initially to be loaded by n . At the end of every cycle, C
would be decremented by 1. The operation of division would be complete when C becomes 0. The n -bit
dividend must be expanded to 2 n -bit form and be loaded in locations R and Q, where R would contain
M04_GHOS1557_01_SE_C04.indd 73M04_GHOS1557_01_SE_C04.indd 73 4/29/11 5:04 PM4/29/11 5:04 PM
74 Computer Architecture and Organization
the most signi cant part. If negative, then the dividend should be changed to its two’s complement form
and expanded from n -bit to 2 n -bit format. In other words, if n is 0100, then it should be expanded as
00000100 and if n is 1101, then it should be expanded to 11111101. However, at the end of operation, R
would contain n -bit remainder and Q would contain n -bit quotient.
4.6.2 One-bit Left-shift
Figure 4.16 Detail of one-bit left-shift operation for division algorithm
Let us consider the shifting technique to be implemented at the beginning of each iteration. In this
case, it would be a one-bit left-shift considering R and Q, simultaneously. A zero has to be inserted at
the LS bit of Q, and the MS bit of Q should be shifted to LS bit of R. The MS bit of R would be moved
out and discarded, as shown in Figure 4.16 .
4.6.3 Algorithm for Division of Signed Integers
The algorithm for the division of signed integers is explained through the following steps.
Step 1 : Load V by n -bit divisor using two’s complement form for negative numbers.
Step 2 : Load n -bit dividend within R and Q after expanding it to 2 n -bit format maintaining its sign
as it is.
Step 3 : Load C by the number of bits being considered, i.e., n.
Step 4 : Perform 1-bit left-shift with R-Q, inserting a 0 at the LS bit of Q.
Step 5 : If the divisor (in V) and R have same sign, then replace R by R − V, otherwise replace R by
R + V.
Step 6 : If the sign of R remains unchanged after Step 5, or R becomes 0, then set LS bit of Q as 1.
Otherwise, if the sign of R changes after Step 5 and R becomes non-zero, then restore the value
of R as it was after Step 4.
Step 7 : Decrement C by 1 and if it is not 0, then go to Step 4.
Step 8 : Find the remainder in R. If the divisor and dividend have same signs, then Q indicates the
quotient. Otherwise, its two’s complement would be the correct quotient.
Note that steps 4 to 7 are involved in the iteration process. Steps 1 to 3 are for initialization and the
Step 8 is for getting the correct result. We next discuss two example cases for implementing this divi-
sion algorithm.
4.6.4 Solved Example 4.5
In our rst example, we divide 5 by 2. The remainder would be 1 and the quotient would be 2. All steps
for this example of each of four cycles are illustrated in Figure 4.17 . The reader may note that the loca-
tions which are not participating in any phase are lightly shaded.
M04_GHOS1557_01_SE_C04.indd 74M04_GHOS1557_01_SE_C04.indd 74 4/29/11 5:04 PM4/29/11 5:04 PM
Computer Arithmetic 75
We start with initialization by loading the divisor (2 in decimal) in location V in its binary form of
4-bit, i.e., 0010. The counter C is initialized as 4 to represent 4-bit operation. The dividend (5 in decimal)
is converted to its 8-bit representation, i.e., 00000101 and its lower half 0101 is loaded within location
Q and the upper half 0000 is loaded in location R.
The rst cycle begins with a one-bit left-shift of R and Q and a 0 is inserted at the least signi cant
position of Q. This changes Q to 1010 and R remains as 0000 after left-shift. As the MS bit of R and
MS bit of V are both 0, a subtraction operation is to be performed to replace R by R − V. So, two’s
complement form of V, i.e., 1110 is added with R, i.e., 0000 to get 1110, which becomes the value in R
at this point. As there is a sign change between the present content of R (1110) and its previous content
(0000), the previous value of R is restored and R becomes 0000 again. By decrementing C from 4 to 3,
we complete the rst cycle and three more cycles are pending.
The second cycle begins with a left-shift of R and Q together changing R to 0001 and Q to 0100. As
the present signs of V and R are identical (both are 0), V is subtracted from R and the result (1111) is
placed in R. This is because of the sign change of R in this process, R is restored to its original value of
0001. The counter C is decremented by 1 to make it 2.
In the third cycle, locations R and Q are jointly shifted one-bit left, making R as 0010 and Q as 1000.
As V and R are having same sign at this point, therefore, R is replaced by the result of R − V, which is
Figure 4.17 Illustration of division algorithm for 5 divided by 2
M04_GHOS1557_01_SE_C04.indd 75M04_GHOS1557_01_SE_C04.indd 75 4/29/11 5:04 PM4/29/11 5:04 PM
76 Computer Architecture and Organization
0000. Note that the sign of R remains unchanged forcing us to set the least signi cant bit of Q as 1. This
changes Q to 1001 and R remains as 0000. Finally, C is decremented to 1, completing the third cycle.
The fourth cycle starts with the left-shift of R as well as Q, changing R to 0001 and Q to 0010. As R
and V are of same sign, R is replaced by R − V, which is 1111. This change in sign of R with respect to
is previous sign forces us to replace R by its old value of 0001. C is now decremented to 0 indicating the
completion of the division operation. The result of the division is now available at Q and R. Q contains
the quotient, i.e., 0010 or 2 in decimal and R contains the remainder 0001 or 1 in decimal. These results
indicated that the operation is correctly performed.
4.6.5 Solved Example 4.6
To illustrate the division of negative integers, we discuss another example to divide (−5) by (−2). In this
case, as we know, the quotient should be 2 and the remainder would be (−1). To start with, we initialize loca-
tion C by 4. The divisor in two’s complement form would be 1110 and loaded in location V. The dividend
−5 is converted to 1011 in two’s complement form considering 4 bits. However, in 8-bit format it would
be extended to 11111011. The upper half, i.e., 1111 is loaded in location R and the lower half, i.e., 1011 is
loaded in Q. This and the remaining steps are illustrated in Figure 4.18 and may be referred by the reader.
Figure 4.18 Illustration of division algorithm for −5 divided by −2
M04_GHOS1557_01_SE_C04.indd 76M04_GHOS1557_01_SE_C04.indd 76 4/29/11 5:04 PM4/29/11 5:04 PM
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.