Binary multiplication

Q: How does a computer multiply two binary numbers?

By shift-and-add, the binary version of longhand multiplication. For each bit of the multiplier it forms a partial product: a 1 bit copies the multiplicand (shifted into that bit's place) and a 0 bit contributes zero. Adding all the shifted partial products gives the result. In hardware an array multiplier forms every partial-product bit with an AND gate (pp(i,j) = a_i AND b_j) and sums them with an array of adders.

Q: How many bits does the product of two n-bit numbers need?

Up to 2n bits. Two n-bit numbers can each be almost 2^n, so their product can approach 2^(2n). For example two 4-bit numbers (max 15 × 15 = 225) need 8 bits, and two 8-bit numbers can need 16. Hardware keeps the full 2n-bit result, often split into a high half and a low half.

Q: What is an array multiplier?

An array multiplier is a combinational multiplier built from an n by n grid of AND gates that produce every partial-product bit at once, plus an array of full adders that sum the partial products column by column into the product. It is fast (one pass of logic) but large, with a gate count that grows with n squared.

Q: Why is multiplying by a power of two the same as shifting?

Multiplying by 2 shifts every bit one place left and inserts a 0 at the bottom, just as appending a 0 multiplies a decimal number by 10. So multiplying by 2^k is a left shift by k, and dividing by 2^k is a right shift by k. It needs no adder, only rewiring, which is why compilers replace x * 8 with x << 3.

Q: What is the difference between a logical and an arithmetic shift?

A logical right shift fills the vacated top bits with 0, which correctly divides an unsigned number. An arithmetic right shift copies the sign bit into the vacated bits, which divides a signed two's-complement number while keeping it negative. Using a logical shift on a negative value turns it large and positive, so signed division must use the arithmetic shift.

Q: What is the difference between an array multiplier and a sequential multiplier?

An array multiplier is combinational: it forms every partial product at once with a grid of AND gates and sums them in one pass, so it is fast but uses on the order of n squared gates. A sequential (shift-and-add) multiplier reuses a single adder over n clock cycles, testing one multiplier bit per cycle and accumulating the shifted multiplicand, so it uses far fewer gates but takes n cycles. It is the classic area-versus-time trade: the array multiplier buys speed with silicon, the sequential multiplier buys small size with time.

Q: How does a sequential shift-and-add multiplier work?

It keeps a running product register (an accumulator) cleared to zero, and each clock cycle it tests the least-significant bit of the multiplier: if that bit is 1 it adds the place-aligned multiplicand into the product, then it shifts to line up the next place and a small control unit counts the cycle. After n cycles the product register holds the full 2n-bit answer. A common optimization shifts the product right instead of the multiplicand left (halving the adder to n bits) and stores the multiplier in the product register's low half, so one register does both jobs.

Shift, add, and the array multiplier

15 min read

A hardware multiplier forms a binary product by ANDing the multiplicand with each bit of the multiplier to make shifted partial products, then adding those partial products together; multiplying two n-bit numbers gives a result of up to 2n bits.

Builds onAdding 8-bit numbers Two's complement

An adder adds, and with the two's-complement trick the same block subtracts. Multiplication is the next operation, and the good news is it is built entirely from things you already have: AND gates and adders. Binary multiplication is just the longhand multiply you learned in school, run on the simplest possible times table, where every digit is 0 or 1. Step through that shift-and-add in the interactive multiplication walkthrough.

Shift and add: longhand multiply in binary

To multiply two numbers by hand you take each digit of the multiplier, multiply it across the multiplicand to get a partial product, shift that partial product left to line up with the digit's place, and add all the partial products. In binary this is much easier than in decimal, because each multiplier bit is only 0 or 1. Multiplying the multiplicand by a 1 bit just copies it; multiplying by a 0 bit gives zero. There is no times table to memorize: each partial product is either the multiplicand, shifted into place, or nothing.

Worked example: 13 times 11

Multiply A = 1101 (13) by B = 1011 (11). Read B from its low bit up. For each 1 bit of B, write down A shifted left by that bit's position; for each 0 bit, write zeros:

B bit 0 is 1: partial product is A shifted left 0, which is 0000 1101.
B bit 1 is 1: partial product is A shifted left 1, which is 0001 1010.
B bit 2 is 0: partial product is 0000 0000.
B bit 3 is 1: partial product is A shifted left 3, which is 0110 1000.
Add the four partial products: 0000 1101 + 0001 1010 + 0000 0000 + 0110 1000 = 1000 1111.

1101 × 1011 = 1000 1111 (13 × 11 = 143)

Notice the width. Two 4-bit numbers can be as large as 15 × 15 = 225, which needs 8 bits, and indeed the result 1000 1111 is 8 bits wide. In general an n-bit by n-bit multiply produces a result of up to 2n bits. A multiplier's output is twice as wide as its inputs, which is why CPUs often split the product into a high half and a low half across two registers.

The array multiplier: a grid of ANDs plus an adder array

Turn that procedure into pure combinational logic. Each bit of a partial product is one bit of A ANDed with one bit of B: the partial-product bit pp(i,j) = a_i AND b_j is 1 only when both bits are 1, exactly the 'copy on 1, zero on 0' rule. So an array multiplier lays out an n by n grid of AND gates, one per (i, j) pair, producing every partial-product bit at once. Then an array of full adders sums the partial products column by column, carrying as it goes, and the columns' results are the product bits.

One cell of an array multiplier: a single AND gate computing the partial-product bit Pij = Ai AND Bj. An n-bit by n-bit multiplier is an n-by-n grid of these AND cells, with an adder array underneath summing the columns into the final product.

An array multiplier is fast (the product falls out in one pass of combinational logic) but large: its gate count grows with n squared, since there are n times n AND cells plus a comparable mesh of adders. That is the same speed-versus-area trade as the carry-lookahead adder. A smaller, slower alternative reuses one adder over several clock cycles: hold a running total, and on each cycle add in the next shifted partial product. Few gates, but n cycles instead of one.

The sequential multiplier: one adder, many cycles

The array multiplier spends gates to buy speed: every partial product exists at once. The sequential multiplier (also called the shift-and-add multiplier) makes the opposite bargain. It builds a single adder and reuses it, walking the longhand procedure one row per clock cycle. That is slower, n cycles for n-bit operands instead of one pass, but it is tiny, which is how small and older processors multiplied when transistors were scarce.

The datapath is small. You need a product register (the running total, also called the accumulator), cleared to 0 and wide enough for the full 2n-bit result; a register holding the multiplicand; a register holding the multiplier, whose lowest bit you test each cycle; one adder; and a small control unit, which is just a counter plus a little logic (a tiny state machine) that repeats one step exactly n times and then stops.

Every cycle does the same four things, which is why the control unit can be such a small loop (an algorithmic state machine, one step repeated):

Test the multiplier's least-significant bit.
If that bit is 1, add the place-aligned multiplicand into the product register. If it is 0, add nothing (a no-op).
Shift to line up the next place: slide the multiplicand one place left, and slide the multiplier one place right so its next bit becomes the new LSB.
Count the cycle. After n cycles the product register holds the answer and the control unit halts.

Trace A = 0011 (3) times B = 0101 (5). With n = 4 it takes 4 cycles. The product P is 8 bits, cleared to 0; the multiplicand starts in the low bits of an 8-bit register so it has room to slide left.

Start: the product P = 0000 0000, the multiplicand register holds 0000 0011, and the multiplier is B = 0101.
Cycle 1: B's LSB is 1, so add the multiplicand into P: 0000 0000 + 0000 0011 = 0000 0011. Then shift the multiplicand left to 0000 0110 and shift B right to 0010.
Cycle 2: B's LSB is 0, so add nothing. Shift the multiplicand left to 0000 1100 and B right to 0001.
Cycle 3: B's LSB is 1, so add: 0000 0011 + 0000 1100 = 0000 1111. Shift the multiplicand left to 0001 1000 and B right to 0000.
Cycle 4: B's LSB is 0, so add nothing. After this fourth cycle P = 0000 1111, which is 15, and indeed 3 × 5 = 15.

Only the two 1 bits of B = 0101 ever added anything: cycle 1 contributed the multiplicand shifted by 0 (0000 0011, which is 3) and cycle 3 contributed it shifted by 2 (0000 1100, which is 12), and 3 + 12 = 15. That is exactly the longhand sum of partial products, now built up one cycle at a time by reusing a single adder.

The width optimization: shift the product, not the multiplicand

The naive layout wastes hardware. To let the multiplicand slide left across the whole 2n-bit width, both its register and the adder have to be 2n bits wide, even though the multiplicand itself is only n bits. A cheaper arrangement computes the same thing. Only the *relative* motion between multiplicand and product matters, so instead of sliding the multiplicand left against a still product, hold the multiplicand still and slide the product right one place each cycle. Now the multiplicand register stays n bits, and the adder only ever adds the n-bit multiplicand into the top half of the product, so the adder shrinks from 2n bits to n.

One more saving. Two things shift right every cycle now: the product and the multiplier. As the product's answer bits fill in from the top and march down, its low half starts out empty, and meanwhile the multiplier loses one bit from its bottom each cycle. The classic trick packs both into one 2n-bit register: load the multiplier into the low half at the start (high half cleared to 0). Each cycle you test that register's LSB (the current multiplier bit), optionally add the multiplicand into its high half, then shift the whole register right by one. The multiplier bits march out the bottom exactly as the product bits march in from the top, so no separate multiplier register is needed at all.

Here is the same 3 × 5 in that single merged register:

Start: pack the multiplier into the low half of one 8-bit register: R = 0000 0101 (high half 0000, low half is the multiplier 0101). The multiplicand M = 0011 sits in its own fixed 4-bit register.
Cycle 1: R's LSB is 1, so add M into the high half (0000 + 0011 = 0011), giving R = 0011 0101, then shift R right one place to 0001 1010.
Cycle 2: R's LSB is 0, so add nothing, then shift right to 0000 1101.
Cycle 3: R's LSB is 1, so add M into the high half (0000 + 0011 = 0011), giving R = 0011 1101, then shift right to 0001 1110.
Cycle 4: R's LSB is 0, so add nothing, then shift right to 0000 1111. After four cycles R = 0000 1111, the full 15, with no separate multiplier register used.

Area versus time, again. The array multiplier is one giant pass of combinational logic: on the order of n squared gates, answer in one step. The sequential multiplier is one n-bit adder, a couple of registers, and a counter: a handful of gates, answer in n steps. Same product, opposite ends of the same area-versus-time dial, and real designs pick a point in between (handling two or four multiplier bits per cycle). It is also a first, clean example of the datapath-plus-control split (registers and an adder doing the work, a small state machine steering them) that the whole CPU datapath is built from. One caution: for unsigned operands the product shifts in a 0 at the top (a logical right shift); signed operands need sign extension on the shift, or the smarter encoding coming up next.

Multiplying and dividing by powers of two: just shift

There is a special case so cheap it barely counts as arithmetic. Multiplying by 2 shifts every bit one place left and brings in a 0 at the bottom, exactly like appending a 0 in decimal multiplies by 10. So **multiplying by 2^k is a left shift by k, and dividing by 2^k is a right shift by k**. No adder, no AND grid, just rewiring which bit goes where. This is why a compiler turns x * 8 into x << 3.

Right shifts come in two flavors, and the difference matters for signed numbers. A logical shift fills the vacated top bits with 0, which divides an unsigned number. An arithmetic shift copies the sign bit into the vacated top bits, which divides a signed two's-complement number while keeping it negative. For example 1111 1000 is -8; an arithmetic right shift by 1 gives 1111 1100 (-4), the correct half, while a logical right shift would give 0111 1100 (+124), nonsense for a signed value.

Common mistakes. Keep 2n bits for a product: discard the high half and a perfectly valid multiply silently overflows, just like a too-narrow adder. For signed values, use an arithmetic right shift (copy the sign), never a logical one, or a negative number turns large and positive. And note that an arithmetic right shift rounds toward negative infinity, not toward zero: -1 (1111 1111) shifted right by 1 stays -1, not 0, so a shift is not an exact stand-in for signed division when the result would round.

Signed multiplication, Booth's algorithm, and barrel shifters

Plain shift-and-add assumes unsigned operands. For signed two's-complement numbers the top bit carries a negative weight, so feeding negatives straight into the array gives the wrong answer unless you correct for it. Booth's algorithm is the standard fix and a small idea worth knowing: it scans the multiplier's bits in pairs and treats a run of 1s as one subtraction at the start of the run plus one addition at its end (since a block of 1s equals a high power of two minus a low one). That handles the sign bit's negative weight automatically and turns long strings of 1s into a single subtract-then-add, so fewer partial products are needed. Modified (radix-4) Booth encoding halves the partial-product count, which is why real multipliers use it.

Shifting by a *fixed* amount is free wiring, but shifting by a variable amount (when the shift count is itself data, as in x << y) needs hardware. A barrel shifter does it in one combinational step using a stack of multiplexer layers: one layer shifts by 1 or not, the next by 2 or not, the next by 4, and so on, so any shift from 0 to n-1 is selected by the bits of the shift amount in about log n mux layers. Unlike a shift register, which moves one bit per clock, a barrel shifter delivers the whole shift at once.

Try it

Multiply A = 0110 (6) by B = 0101 (5) by hand. Write each of the four partial products (one per bit of B), then add them. What is the product, and how many bits does it take?

Multiplication shows how far you get by composing the primitives you already own: a grid of AND gates makes the partial products and an adder array sums them, with shifts handling powers of two for free. It is another area-versus-speed dial (one fast array, or one small adder run for several cycles). Next, the ALU gathers add, subtract, and the bitwise operations into the single block at the center of the CPU, and division is the harder inverse: the same shift-and-add idea run backwards as shift-and-subtract.

Frequently asked

How does a computer multiply two binary numbers?

By shift-and-add, the binary version of longhand multiplication. For each bit of the multiplier it forms a partial product: a 1 bit copies the multiplicand (shifted into that bit's place) and a 0 bit contributes zero. Adding all the shifted partial products gives the result. In hardware an array multiplier forms every partial-product bit with an AND gate (pp(i,j) = a_i AND b_j) and sums them with an array of adders.

How many bits does the product of two n-bit numbers need?

Up to 2n bits. Two n-bit numbers can each be almost 2^n, so their product can approach 2^(2n). For example two 4-bit numbers (max 15 × 15 = 225) need 8 bits, and two 8-bit numbers can need 16. Hardware keeps the full 2n-bit result, often split into a high half and a low half.

What is an array multiplier?

An array multiplier is a combinational multiplier built from an n by n grid of AND gates that produce every partial-product bit at once, plus an array of full adders that sum the partial products column by column into the product. It is fast (one pass of logic) but large, with a gate count that grows with n squared.

Why is multiplying by a power of two the same as shifting?

Multiplying by 2 shifts every bit one place left and inserts a 0 at the bottom, just as appending a 0 multiplies a decimal number by 10. So multiplying by 2^k is a left shift by k, and dividing by 2^k is a right shift by k. It needs no adder, only rewiring, which is why compilers replace x * 8 with x << 3.

What is the difference between a logical and an arithmetic shift?

A logical right shift fills the vacated top bits with 0, which correctly divides an unsigned number. An arithmetic right shift copies the sign bit into the vacated bits, which divides a signed two's-complement number while keeping it negative. Using a logical shift on a negative value turns it large and positive, so signed division must use the arithmetic shift.

What is the difference between an array multiplier and a sequential multiplier?

An array multiplier is combinational: it forms every partial product at once with a grid of AND gates and sums them in one pass, so it is fast but uses on the order of n squared gates. A sequential (shift-and-add) multiplier reuses a single adder over n clock cycles, testing one multiplier bit per cycle and accumulating the shifted multiplicand, so it uses far fewer gates but takes n cycles. It is the classic area-versus-time trade: the array multiplier buys speed with silicon, the sequential multiplier buys small size with time.

How does a sequential shift-and-add multiplier work?

It keeps a running product register (an accumulator) cleared to zero, and each clock cycle it tests the least-significant bit of the multiplier: if that bit is 1 it adds the place-aligned multiplicand into the product, then it shifts to line up the next place and a small control unit counts the cycle. After n cycles the product register holds the full 2n-bit answer. A common optimization shifts the product right instead of the multiplicand left (halving the adder to n bits) and stores the multiplier in the product register's low half, so one register does both jobs.

Every lesson here builds toward one thing: a working CPU, from the transistor up.

Open the free lab →

Builds towardBinary division