Binary multiplication explained

All posts




At the heart of computer performance lies binary multiplication, the process of combining numbers bit-by-bit.

Let's take a look at how it works.

1st principles of binary multiplication

To break it down, here you have the three logical operations used in binary multiplication, AND, SHIFT, ADD.

  • AND: takes each bit of B in isolation and applies AND on the entire string of A bit-by-bit.
  • SHIFT: Shift Left is performed every move down starting from 0, till all moves (based on the range of B) are performed.
  • ADD: is used to add up the whole and get the product Sum in return.

For each bit of B (index i) we perform a move down, every move down is a Shift Left (starting at index 0) which creates a partial. Every partial is summed up using addition logic to get the multiplication end product.

Let me walk you through an example using 5 X 10 (0101 X 1010) starting at figure 1.0.

  • A is 0101 (5)
  • B is 1010 (10)
Bit position B[i] (B[i] AND A) Shift (<< i) Partial product (7b)
000000<< 0XXX0000
110101<< 1XX01010
200000<< 2X000000
310101<< 30101000
Figure 1.0: Step table: for each bit of B, AND it with A, then shift left by its index to form a partial product.

We mark unused positions with X which act as placeholders, in actual hardware these become 0s in register. So that the ALU can work with the same range in every bit-by-bit addition calculation, to get Sum and Carry out.

If you're not familiar with binary addition check out binary part-I.

Now let's apply binary addition row-by-row on each partial product.

Binary addition applied on Partial product

Short recap of Sum, and Carry out:

  • Sum: A XOR B XOR Carry in
  • Carry out: (A AND B) OR (Carry in AND (A XOR B))

Example: 1 + 1 with carry-in 0 gives sum = 0, carry = 1

Starting bit-by-bit at Partial 0, and 1 in figure 1.1, to get the Sum column then we repeat that process two more times.

Bit position Running sum Next partial Carry in Sum Carry out
000000
101010
200000
301010
400000
500000
600000
Figure 1.1: Ripple-carry addition: adding Partial 0 and Partial 1 from Figure 1.0.

NOTE: Bit 0 is rightmost least significant bit (LSB) moving to leftmost most significant bit (MSB).

Now in figure 1.2 we take Sum from figure 1.0 and apply addition logic bit-by-bit with Partial 2 of figure 1.0.

Bit position Running sum Next partial Carry in Sum Carry out
000000
110010
200000
310010
400000
500000
600000
Figure 1.2: Ripple-carry addition: adding the previous sum with Partial 2 from Figure 1.0.

Arriving at the last Partial, Partial 3 in figure 1.0, we repeat addition logic for Sum and Carry out one last time.

Bit position Running sum Next partial Carry in Sum Carry out
000000
110010
200000
311001
400110
501010
600000
Figure 1.3: Ripple-carry addition: adding the running sum with Partial 3 from Figure 1.0 to produce the final product.

After applying addition logic on all four arrays we end up with '0110010' (you can read it in the Sum column), which is integer 50.

That was binary multiplication.

Like to stay updated and learn about Systems, Rust, Math, and more? Then you can follow me on X/Twitter where I'll be posting when a blog goes live.

Want to see coded examples? Click ALU a 32-bit Arithmetic Logic Unit that goes from integers to bit-by-bit simulations through logic gates, supports ADD, SUB, MULTIPLY, DIV.

Now go practice some binary multiplication till next time.