Information Technology Reference
In-Depth Information
r
2
¼
2r
1
00
†
1000
2r
2
01
†
0
0
0
Set q
3
¼
1
2
D
þ
11
†
010
r
3
¼
2r
2
2
D 00
†
010
(0
.
101)
The resultant quotient Q
¼
(5
8) and remainder R
¼
(1
32). These
¼
/
/
values are correct since X
¼
QD
þ
R
¼
2.
Now we show the validity of the above process in the case of integer values. In
this case,
(5
8)(3
4)
þ
1
32
1
/
/
/
¼
/
can be rewritten as 2
2n
2
X
f
¼
2
n
1
Q
f
the equation
X
¼
QD
þ
R
2
n
1
D
f
þ
2
n
1
R
f
,
2
(n
1)
R
f
leading to X
f
¼
Q
f
D
f
þ
where X
f
,D
f
,Q
f
, and R
f
are fractions. We offer the following illustrative example.
Example
Consider the division of a dividend X
¼
32
(0100000) and a divisor
¼
D
¼
6
(0110). The process is illustrated in the following table.
¼
r
0
¼
X
0
1
0
0
0
0
0
Initial values
2r
0
0
1
0
0
0
0
0
Set q
1
¼
1
2
D
þ
1
1
0
1
0
r
1
¼
2r
0
2
D
0
0
0
1
0
0
0
2r
1
0
0
1
0
0
0
Set q
2
¼
0
r
2
¼
2r
1
0
0
1
0
0
0
2r
2
0
1
0
0
0
Set q
3
¼
1
2
D
þ
1
1
0
1
0
r
3
¼
2r
2
2
D
0
0
0
1
0
2r
3
0
0
1
0
Set q
4
¼
0
The resultant quotient is Q
¼
0101
(5) and the remainder R
¼
0010 (2). These are
¼
correct values.
A hardware structure for binary division is shown in Figure 4.10. In this figure,
the divisor (D) and the contents of register A are added using an (n
þ
1)-bit adder. A
control logic is used to perform the required shift left operation (see Exercises).
The comparison between the remainder and the divisor is considered to be the
most difficult step in the division process. The way used above to perform such com-
parison is to subtract D from 2r
i
1
and if the result is negative, then we set q
i
¼
0.
This required restoring the previous value by adding back the subtracted value
(restoring division).
The alternative is to use a non-restoring division algorithm:
Step #1: Do the following n times
1. If the sign of A is 0, shift left AQ and subtract D from A; otherwise shift
left AQ and add D to A.
2. If the sign of A is 0, set q
0
¼
1; otherwise set q
0
¼
0.
Step #2: If the sign of A is 1, add D to A.
Search WWH ::
Custom Search