Here are a couple of ways of doing two's complement multiplication by hand. Direct implementations of these algorithms into the circuitry would result in very slow multiplication! Actual implementations are far more complex, and use algorithms that generate more than one bit of product each clock cycle. ECE 352 should cover these faster algorithms and implementations.
Remember that the result can require 2 times as many bits as the original operands. We can assume that both operands contain the same number of bits.
In 2's complement, to always get the right answer without thinking about the problem, sign extend both integers to twice as many bits. Then take the correct number of result bits from the least significant portion of the result.
A 4-bit, 2's complement example:
1111 1111 -1
x 1111 1001 x -7
---------------- ------
11111111 7
00000000
00000000
11111111
11111111
11111111
11111111
+ 11111111
----------------
1 00000000111
-------- (correct answer underlined)
Another 4-bit, 2's complement example, showing both the incorrect result (when sign extension is not done), and the correct result (with sign extension):
WRONG ! Sign extended:
0011 (3) 0000 0011 (3)
x 1011 (-5) x 1111 1011 (-5)
------ -----------
0011 00000011
0011 00000011
0000 00000000
+ 0011 00000011
--------- 00000011
0100001 00000011
not -15 in any 00000011
representation! + 00000011
------------------
1011110001
--------
take the least significant 8 bits 11110001 = -15
multiplicand
x multiplier
----------------
product
If we do not sign extend the operands (multiplier and multiplicand), before doing the multiplication, then the wrong answer sometimes results. To make this work, sign extend the partial products to the correct number of bits.
To result in the least amount of work, classify which do work, and which do not.
+ - + - (muliplicands)
x + x + x - x - (mulipiers)
---- ---- ---- ----
OK sign | |
extend | take |
partial | additive |
products | inverses |
- +
x + x +
---- ----
sign OK
extend
partial
products
Example:
without with correct
sign extension sign extension
11100 (-4) 11100
x 00011 (3) x 00011
------------ ---------
11100 1111111100
11100 1111111100
------------ ---------------
1010100 (-36) 1111110100 (-12)
WRONG! RIGHT!
Another example:
without adjustment with correct adjustment
11101 (-3) 11101 (-3)
x 11101 (-3) x 11101 (-3)
------------- -------------
11101 (get additive inverse of both)
11101
11101 00011 (+3)
+11101 x 00011 (+3)
----------- -------------
1101001001 (wrong!) 00011
+ 00011
---------
001001 (+9) (right!)
| Copyright © Karen Miller, 2006 |