Chapter 3 part 3
Unsigned Division (Paper & Pencil)
100112 = 19 Quotient
Divisor 10112 110110012 = 217 Dividend
-1011
10 Try to see how big a
101 number can be
subtracted, creating a
1010 digit of the quotient on
10100 each attempt
Dividend = -1011
Quotient × Divisor 1001 Binary division is
+ Remainder accomplished via
10011
shifting and subtraction
217 = 19 × 11 + 8 -1011
10002 = 8 Remainder
Sequential Division
Uses two registers: HI and LO
Initialize: HI = Remainder = 0 and LO = Dividend
Shift (HI, LO) LEFT by 1 bit (also Shift Quotient LEFT)
Shift the remainder and dividend registers together LEFT
Has the same net effect of shifting the divisor RIGHT
Compute: Difference = Remainder – Divisor
If (Difference ≥ 0) then
Remainder = Difference
Set Least significant Bit of Quotient
Observation to Reduce Hardware:
LO register can be also used to store the computed Quotient
Sequential Division Hardware
Initialize: Start
HI = 0, LO = Dividend
Results: 1. Shift (HI, LO) Left
Difference = HI – Divisor
HI = Remainder
LO = Quotient ≥0 <0
Difference?
Divisor
2. HI = Remainder = Difference
32 bits Set least significant bit of LO
sub
32-bit ALU
sign No
Difference 32nd Repetition?
write Yes
HI LO Control
shift left Done
32 bits 32 bits
set lsb
Unsigned Integer Division Example
Example: 11102 / 00112 (4-bit dividend & divisor)
Result Quotient = 01002 and Remainder = 00102
4-bit registers for Remainder and Divisor (4-bit ALU)
Iteration HI LO Divisor Difference
0 Initialize 0000 1110 0011
1: Shift Left, Diff = HI - Divisor 0001 1100 0011 1110
1
2: Diff < 0 => Do Nothing
1: Shift Left, Diff = HI - Divisor 0011 1000 0011 0000
2
2: Rem = Diff, set lsb of LO 0000 1001
1: Shift Left, Diff = HI - Divisor 0001 0010 0011 1110
3
2: Diff < 0 => Do Nothing
1: Shift Left, Diff = HI - Divisor 0010 0100 0011 1111
4
2: Diff < 0 => Do Nothing
Signed Integer Division
Simplest way is to remember the signs
Convert the dividend and divisor to positive
Obtain the 2's complement if they are negative
Do the unsigned division
Compute the signs of the quotient and remainder
Quotient sign = Dividend sign XOR Divisor sign
Remainder sign = Dividend sign
Negate the quotient and remainder if their sign is negative
Obtain the 2's complement to convert them to negative
Signed Integer Division Examples
1. Positive Dividend and Positive Divisor
Example: +17 / +3 Quotient = +5 Remainder = +2
2. Positive Dividend and Negative Divisor
Example: +17 / –3 Quotient = –5 Remainder = +2
3. Negative Dividend and Positive Divisor
Example: –17 / +3 Quotient = –5 Remainder = –2
4. Negative Dividend and Negative Divisor
Example: –17 / –3 Quotient = +5 Remainder = –2
The following equation must always hold:
Dividend = Quotient × Divisor + Remainder
Integer Multiplication in MIPS
Multiply instructions
mult $s1,$s2 Signed multiplication
multu $s1,$s2 Unsigned multiplication
$0
32-bit multiplication produces a 64-bit Product $1
..
Separate pair of 32-bit registers
$31
HI = high-order 32-bit of product
Multiply
LO = low-order 32-bit of product Divide
MIPS also has a special mul instruction
HI LO
mul $s0,$s1,$s2 $s0 = $s1 × $s2
Put low-order 32 bits into destination register
HI & LO are undefined
Integer Division in MIPS
Divide instructions
div $s1,$s2 Signed division
divu $s1,$s2 Unsigned division
Division produces quotient and remainder $0
$1
Separate pair of 32-bit registers ..
HI = 32-bit remainder $31
LO = 32-bit quotient Multiply
If divisor is 0 then result is unpredictable Divide
Moving data from HI/LO to MIPS registers HI LO
mfhi Rd (move from HI to Rd)
mflo Rd (move from LO to Rd)
Integer Multiply/Divide Instructions
Instruction Meaning Format
mult Rs, Rt Hi, Lo = Rs × Rt op6 = 0 Rs5 Rt5 0 0 0x18
multu Rs, Rt Hi, Lo = Rs × Rt op6 = 0 Rs5 Rt5 0 0 0x19
mul Rd, Rs, Rt Rd = Rs × Rt 0x1c Rs5 Rt5 Rd5 0 0x02
div Rs, Rt Hi, Lo = Rs / Rt op6 = 0 Rs5 Rt5 0 0 0x1a
divu Rs, Rt Hi, Lo = Rs / Rt op6 = 0 Rs5 Rt5 0 0 0x1b
mfhi Rd Rd = Hi op6 = 0 0 0 Rd5 0 0x10
mflo Rd Rd = Lo op6 = 0 0 0 Rd5 0 0x12
Signed arithmetic: mult, div (Rs and Rt are signed)
LO = 32-bit low-order and HI = 32-bit high-order of multiplication
LO = 32-bit quotient and HI = 32-bit remainder of division
Unsigned arithmetic: multu, divu (Rs and Rt are unsigned)
NO arithmetic exception can occur
Integer to String Conversion
Objective: convert an unsigned 32-bit integer to a string
How to obtain the decimal digits of the number?
Divide the number by 10, Remainder = decimal digit (0 to 9)
Convert decimal digit into its ASCII representation ('0' to '9')
Repeat the division until the quotient becomes zero
Digits are computed backwards from least to most significant
Example: convert 2037 to a string
Divide 2037/10 quotient = 203 remainder = 7 char = '7'
Divide 203/10 quotient = 20 remainder = 3 char = '3'
Divide 20/10 quotient = 2 remainder = 0 char = '0'
Divide 2/10 quotient = 0 remainder = 2 char = '2'
