Number Representation


Multiplication of Integers

Review of 3rd Grade


        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

Alyce Brady, Kalamazoo College