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:
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:
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