Integer Multiplication and Division
Base 10 Multiplication Review (obviously)
a (multiplicand) * b (multiplier)
Consider a = 123, b = 123.
369 (this is 123 * 3)
246 (Thisis123*2shiftedleft1place)
123 (This is 123 * 1 shifted left 2 places) ========
Binary (Base 2) Multiplication Now consider:
a (multiplicand) * b (multiplier) where a = 1011 (11 decimal), b = 1110 (14 decimal)
(this is 11 in decimal)
(this is 14 in decimal)
===================
(this is 1011 x 0)
(this is 1011 x 1, shifted one position to the left)
(this is 1011 x 1, shifted two positions to the left)
(this is 1011 x 1, shifted three positions to the left)
===========================
(this is 154 in decimal)
This is the same process that we use for decimal multiplication!
One could say that binary multiplication is actually easier because each row is either just a “shifted copy” of the multiplicand or it’s 0.
Hardware for integer multiplication (Simplest version)
•Suppose we want the CPU to multiply two operands: a (multiplicand) * b (multiplier)
•Typically, in the simplest version of multiplication hardware, 4 additional registers are used:
-Multiplicand register (contains a copy of the multiplicand) -Multiplier register (contains a copy of the multiplier) -Shifted multiplicand register
-Result register
Multiplication hardware cont
•For n bit multiplication, we can denote the bits in the multiplier as b0 (least significant bit) to bn-1 (most significant bit)
•The hardware initializes the result register to 0
•Then, the hardware does the following (pseudo-code):
for (j = 0; j
So if op2n> 1 in our example, overflow occurs.
•Again, overflow may also occur due to addition, but the result above describes cases where overflow will definitely occur due to shifting.
w=8, 0p1=4, op2=3 w(8) – 1 – op1(4) = 3
w=8, 0p1=4, op2=3
w(8) – 1 – op1(4) = 3
Is op2 > w – 1 – op1? 3 > 3?
w=8, 0p1=4, op2=3
w(8) – 1 – op1(4) = 3
Is op2 > w – 1 – op1? 3 > 3? No overflow in this case.
Dividing by powers of 2
•Even slower than integer multiplication
•Dividing by powers of 2right shifting -There are 2 types of right shifting:
-Logical – unsigned: fill with 0’s
-Arithmetic – two’s complement: fill with copy of msb
•Integer division always truncates
-C float-to-integer casts round towards zero.
-Division by right shifting rounds down. -These rounding errors generally accumulate
Unsigned Integer Division
•Dividing by 2k
•Logical right shift by k (x>>k) •Then rounding down (toward zero)
•Remember that logical shift will shift in zeroes to fill
the most significant bits when the original bit pattern is shifted right
Dividing by powers of 2
101000 101001 100 1 1 0 0 1001111
x = 8 = 1000
y = 2 = 0010 = 21
x >> 1 = 100 (x / y)
x = 9 = 1001
y = 2 = 0010 = 21
x >>1 = 100 (x / y)
Dividing by powers of 2
101000 101001 100 1 1 0 0 1001111
x = 12 = 1100
y = 4 = 0100 = 22 x >> 2 = 11
x = 15 = 1111
y = 4 = 0100 = 22 x >>2 = 11
Signed Integer Division
•Two’s complement
•Sign extend for arithmetic shift (fill with copy of msb) •Rounds down (away from zero for negative results) •-7/2 will yield -4 rather than -3
•x = -82 y = 2k
-82.000000
-41.000000
-20.500000
-10.250000
Note rounding effect