# Number Representation

### Multiplication of Integers

``````
1000   (Multiplicand)
* 1001   (Multiplier)
----
1000
0000
0000
+ 1000
--------
1001000   (Product)
``````

NOTE: When multiplying an n-digit value by an m-digit value, the product may require as many as n + m digits.

Going from the last intermediate result up (i.e., going through the bits in the multiplier left-to-right), we have:

• Before computing the next intermediate result, shift the product so far left one bit.
• If the digit in the multiplier is 1, add another instance of the multiplicand to the intermediate result. If the multiplier digit is 0, don't do an add.
• Consider the next bit in the multiplier.
``````
Multiplicand   Multiplier     Product
------------   ----------     -------
00000000
1000           1001           1000  Bit is 1, so add multiplicand.
^          00001000
===========================
00010000  Shift left
1000           1001                 Bit is 0, so do nothing
^         00010000
===========================
00100000  Shift left
1000           1001                 Bit is 0, so do nothing
^        00100000
===========================
01000000  Shift left
1000           1001           1000  Bit is 1, so add multiplicand.
^       01001000
``````

Alternatively, we could go through the multiplier right-to-left:

• If the digit in the multiplier is 1, add another instance of the multiplicand to the intermediate result. If the multiplier digit is 0, don't do an add.
• Shift the multiplier to the right (losing the bit we just processed).
• Before computing the next intermediate result, shift the product so far right one bit.
``````
Multiplicand   Multiplier     Product
------------   ----------     -------
0000|0000
1000           1001       1000        Bit is 1, so add multiplicand.
^       1000|0000
0100 0|000  Shift right
===========================
1000            100                   Bit is 0, so do nothing
^       0100 0000
0010 00|00  Shift right
===========================
1000             10                   Bit is 0, so do nothing
^       0010 0000
0001 000|0  Shift right
===========================
1000              1       1000        Bit is 1, so add multiplicand.
^       1001 0000
0100 1000|  Shift right
``````