Binary Multiplication

Task 1 - The single bit times table

In denary you had to learn times tables up to 9 × 9. In binary there are only two digits, so the whole times table fits in four lines.

The answer is only 1 when both bits are 1. That makes multiplying two single bits the same as the logical AND operation.

It also means multiplying a whole binary number by a single bit is easy. Multiplying by 0 gives all zeros. Multiplying by 1 gives the same number back.

Task 2 - Multiplying by 2 is a shift

In denary, multiplying by 10 moves every digit one place to the left and puts a 0 on the end. 47 × 10 = 470.

Binary works the same way, but each column is worth 2 times the column to its right, not 10 times. So moving every bit one place left doubles the number. This is called a left shift.

Shifting left by k places multiplies by 2^k.

Try it on the shifter below. It starts at 3. Press Shift left a few times and watch the value double each time. Keep going until a 1 falls off the left-hand end, and see what happens to the value. You can also click any bit to change it, and try Shift right to see the opposite effect.

Write each answer as an 8-bit binary number.

Task 3 - Long multiplication in denary

Before multiplying in binary, remind yourself how long multiplication works in denary. Here is 23 × 14.

      2 3
  ×   1 4
  -------
      9 2      (23 × 4)
  + 2 3 0      (23 × 1, shifted one place left)
  -------
    3 2 2

You multiply the top number by each digit of the bottom number in turn, starting on the right. Each new row is shifted one more place to the left, which is why the grey placeholder 0 is there. Then you add the rows.

The hard part in denary is the first step, working out 23 × 4. In binary that step disappears, because every digit of the bottom number is either 0 or 1, and you already know from Task 1 that multiplying by 0 or 1 is trivial.

Task 4 - The shift and add method

To multiply two binary numbers, follow these steps.

1. Write the first number (the multiplicand) above the second number (the multiplier).
2. Look at the multiplier one bit at a time, starting from the right.
3. If the bit is 1, write down a copy of the multiplicand. If the bit is 0, write a row of zeros.
4. Shift each new row one more place to the left than the row above it. Fill the gap on the right with placeholder zeros.
5. Add up all the rows. These rows are called partial products.

Worked example: 1011 × 0110 (11 × 6)

            1 0 1 1    (11)
  ×         0 1 1 0    (6)
    ---------------
            0 0 0 0    (bit is 0, write zeros)
          1 0 1 1 0    (bit is 1, copy the top number, shifted 1 place left)
        1 0 1 1 0 0    (bit is 1, copy the top number, shifted 2 places left)
  +   0 0 0 0 0 0 0    (bit is 0, write zeros, shifted 3 places left)
    ---------------
    0 1 0 0 0 0 1 0    = 66

Check in denary. 64 + 2 = 66, and 11 × 6 = 66. Correct.

Ignoring the rows of zeros, the partial products are 22 (11 × 2) and 44 (11 × 4), so the method has really worked out 11 × 6 as 11 × 4 + 11 × 2. That is because 6 is 4 + 2, which is exactly what its binary pattern 0110 says.

Task 5 - Step through shift and add

The diagram below carries out shift and add one step at a time on two 4-bit numbers. It starts with the worked example from Task 4, 11 × 6. Press Next step to use the next bit of B, starting from the right. The gold box shows which bit of B has just been used. Grey digits are placeholder zeros.

Once you are happy with how it works, click the bits of A and B to make your own sums. Work each one out on paper first, then step through to check.

1. Set B to 0001. What do you notice about the answer?
2. Set B to 1000. How does the answer relate to A?
3. Set A and B both to 1111. How many bits does the answer use?

Task 6 - A guided multiplication

Work out 1101 × 0101 on paper using shift and add. Fill in each partial product as an 8-bit number, including any placeholder zeros on the right and leading zeros on the left.

For example, if the top number were 0011 and the bit were 1 with a shift of 2, the partial product would be 00001100.

Task 7 - Adding the partial products safely

When there are several partial products, a column can end up with three or four 1s in it. 1 + 1 + 1 = 3 = 11, so you write 1 and carry 1. With four 1s you get 4 = 100, which carries into the column two places to the left. This is easy to get wrong.

A safer way is to keep a running total. Add the first two partial products, then add the next one to that answer, and so on. Then you never add more than two rows at once. This is also how a simple processor does it, using its normal adding circuit once for each bit of the multiplier.

Worked example: 1101 × 1011 (13 × 11)

The multiplier 1011 has 1s in bits 0, 1 and 3, so the partial products are 13, 26 and 104.

   0 0 0 0 1 1 0 1    (13, bit 0)
 + 0 0 0 1 1 0 1 0    (26, bit 1)
   ---------------
   0 0 1 0 0 1 1 1    = 39

Bit 2 of the multiplier is 0, so there is nothing to add for it. Now add the bit 3 partial product to the running total.

   0 0 1 0 0 1 1 1    (running total)
 + 0 1 1 0 1 0 0 0    (104, bit 3)
   ---------------
   1 0 0 0 1 1 1 1    = 143

13 × 11 = 143. Correct.

Use shift and add, with a running total if it helps. Give each answer as an 8-bit binary number and in denary.

Task 8 - Multiplying by numbers that are not powers of 2

Shift and add also explains a trick that computers use when they multiply by a fixed number. To work out x × 10, split 10 into powers of 2. 10 = 8 + 2, so x × 10 = x × 8 + x × 2. That is one shift of 3 places, one shift of 1 place, and one addition.

Worked example: 13 × 10

   0 1 1 0 1 0 0 0    (13 × 8)
 + 0 0 0 1 1 0 1 0    (13 × 2)
   ---------------
   1 0 0 0 0 0 1 0    = 130

Task 9 - How many bits does the answer need?

When you add two 4-bit numbers, the answer needs at most 5 bits. Multiplying makes numbers grow much faster. The biggest 4-bit number is 1111 = 15, and 15 × 15 = 225 = 11100001, which needs all 8 bits.

In general, multiplying an n-bit number by an m-bit number gives a product that fits in n + m bits. The biggest n-bit number is 2ⁿ - 1, so the biggest possible product is the one below, which is always smaller than 2^n+m.

This is why many processors put the result of multiplying two 8-bit numbers into a 16-bit space, and the result of multiplying two 32-bit numbers into a 64-bit space.

Task 10 - When the product does not fit

Sometimes a computer multiplies two numbers but only has room for an 8-bit answer. If the true product is bigger than 255, the bits above the 128 column are lost, just like the 1 that fell off the end of the shifter in Task 2. This is overflow, and the stored answer is wrong.

Worked example: 20 × 13

The true answer is 260 = 0000000100000100 in 16 bits. Keep only the rightmost 8 bits and you get 00000100, which is 4. The 256 has been lost.

A quick check is to work out the product in denary first. Anything above 255 will overflow an 8-bit space.

Task 11 - Multiplying two's complement numbers

In the Two's Complement lab you stored negative numbers using a -128 column, and found -x with flip and add 1. The easiest way to multiply signed numbers by hand is to deal with the signs separately, using the same sign rule as in denary.

1. Note whether the answer will be positive or negative.
2. Turn any negative number into its positive version with flip and add 1.
3. Multiply the two positive numbers using shift and add.
4. If the answer should be negative, flip and add 1 on the product.

Worked example: 11111101 × 00000101 (-3 × 5)

1. One number is negative, so the answer is negative.
2. 11111101 is negative. Flip gives 00000010, add 1 gives 00000011, which is +3.
3. 3 × 5 = 15 = 00001111.
4. The answer should be negative. Flip gives 11110000, add 1 gives 11110001.

Check with the -128 column: -128 + 64 + 32 + 16 + 1 = -15. Correct.

Give each answer in 8-bit two's complement and in denary. Remember the minus sign for negative answers, for example -7.

Task 12 - Check your understanding