Clemson University -- CPSC 231
More Binary Arithmetic
Multiplication (unsigned example on p. 128)
multiplying two 32-bit values gives up to a 64-bit product
we go from right to left across the multiplier digits in generatingpartial products
we could use a double-length product register, and at each step we could shift the multiplicand into the correct place for adding or not (just like the normal paper and pencil approach)
e.g., 1111 4-bit multiplicand
x 0101 4-bit multiplier
------
....1111
...0000. (. is a placeholder, equal to 0)
..1111..
.0000...
------need 8-bit adder
01001011
since one column is completely determined on the right at each step, we could instead arrange to shift the partial sum to the right after each add - this means we only need a 4-bit wide adder
carry accumulator MQ (multiplier/quotient) register
C / partial product / multipliermultiplicand
initially:
carry 0
accumulator 0
mq multiplier
mdr multiplicand
for(i = 1; i <= n; i++ )
{
/* step i */
if(mq_bit[0] == 1 )
{
(carry:accumulator) accumulator + mdr
}
shift (carry:accumulator:mq) right one place
}
results:
high bits of product in accumulator
low bits of product in mq
e.g., 1111 4-bit multiplicand
x 0101 4-bit multiplier
------
initially: C ACC MQ
0 0000 0101
MDR
1111
------
step 1: 0 0000 0101
+ 1111 ^ add based on lsb=1
------
0 1111 0101
> shift right
0 0111 1010
------
step 2: 0 0111 1010
+ 0000 ^ no add based on lsb=0
------
0 0111 1010
> shift right
0 0011 1101
------
step 3: 0 0011 1101
+ 1111 ^ add based on lsb=1
------
1 0010 1101
> shift right
0 1001 0110
------
step 4: 0 1001 0110
+ 0000 ^ no add based on lsb=0
------
0 1001 0110
> shift right
0 0100 1011
------
Division
instead of add-then-shift, division is implemented by shift-then-subtract
double-length dividend divided by single-length divisor yields single-lengthquotient and single-length remainder
we work from left to right in generating the quotient
carry accumulator MQ (multiplier/quotient) register
C / double length dividenddivisor
initially:
carry 0
accumulator high bits of dividend (0s if dividend is single length)
mq low bits of dividend
mdr divisor
if(mdr == 0 ){ raise( DIVIDE_BY_ZERO__SIGNAL ); }
if(mdr <= accumulator ){ raise( QUOTIENT_OVERFLOW_SIGNAL ); }
for(i = 1; i <= n; i++ ) {
/* step i */
shift (carry:accumulator:mq) left one place
(carry:accumulator) (carry:accumulator) - mdr /* subtract */
if( (carry:accumulator) is negative )
{
mq_bit[0] 0
(carry:accumulator) (carry:accumulator) + mdr /* restore */
}
else {
mq_bit[0] 1
}
}
results:
quotient in mq
remainder in accumulator
this is called restoring division, since the C:ACC must be restored to its
previous value if the result of a subtraction is negative
when the dividend is double-length, there is a special check (the value in
the MDR should be greater than the value in the ACC) to make sure that
the quotient won't overflow (e.g., consider 11111111 / 1)
when dividend is single-length, it is placed in the MQ and the ACC is set
to zero
e.g., 11001001 8-bit dividend
/ 1111 4-bit divisor
------
initially: C ACC MQ
0 1100 1001
MDR
1111
(step 0: ( MDR != 0 ) and ( MDR > ACC ) so no exceptions)
------
step 1: 0 1100 1001
< shift left
1 1001 001.
- 1111 subtract (== add 1 0001)
-----
0 1010 0011
^ set to 1 since subtract successful
------
step 2: 0 1010 0011
< shift left
1 0100 011.
- 1111 subtract (== add 1 0001)
----
0 0101 0111
^ set to 1 since subtract successful
------
step 3: 0 0101 0111
< shift left
0 1010 111.
- 1111 subtract (== add 1 0001)
------
1 1011 1110
^ set to 0 since subtract unsuccessful
+ 1111 restoring add
------
0 1010 1110
------
step 4: 0 1010 1110
< shift left
1 0101 110.
- 1111 subtract (== add 1 0001)
------
0 0110 1101
^ set to 1 since subtract successful
------
remainderis in ACC / quotient
is in MQ
0110 / 1101
(there are faster forms of division, e.g., non-restoring)