Multiplication

k is the number of bit positions you shift (how far)

In “shift by k” what does k mean?

A power of two; shifting left by k multiplies the value by 2^k.

What does 2^k mean?

It computes A × 2^k by appending k zeroes on the right.

What does a left shift by k do to an integer A?

Shift right and fill new left bits with 0.

What is a logical right shift (for unsigned)?

It approximates floor (A/2^k) (LSBs are discarded)

What does a right shift by k do to an unsigned integer A?

Truncation in binary shifts

The loss of information when the k least-significant bits are dropped during a right shift

Arithmetic right shift (for signed 2’s complement)

Shift right while replicating the sign bit on the left.

Divides by 2 while preserving sign (rounds toward -∞)

What does an arithmetic right shift by 1 do?

Arithmetic keeps the sign by filling with the sign bit; logical always fills with 0.

How is the arithmetic right shift different from logical right shift?

2A

Inside the binary arithmetic, it is the value of A left-shifted by 1 bit, which multiplies A by 2.

Is cheap in hardware because it is basically just a left shift A<<1.

3A

In the binary multiplication, it is the value of A multiplied by 3, often computed efficiently as 2A + A; which basically is one left shift plus the addition of one.

Ensure the adder/result has enough bits to avoid overflow.

What width caution applies when doing 3A?

Multiplicand (A)

Inside the Binary multiplication, this is defined as the value that is being copied/shifted.

Multiplier (Q)

Inside the Binary multiplication, this is defined as the value that selects which shifted copies to add.

The core idea of binary multiplication

For each multiplier bit = 1, take a left-shifted copy of the multiplicand and add them together.

qi

In binary multiplication, this bit is the i-th bit of the multiplier.

If qi = 1, it selects adding a shifted copy of the multiplicand.

(A << i)

Represents that the multiplicand A is shifted by i-bits. Multiplies A by 2^i.

Because each bit’s index i directly tells how many positions to shift the multiplicand. q0 = (A << 0); q1 = (A << 1)

Why do w scan multiplier bits from LSB to MSB?

Partial Product (PP)

A row formed by ANDing A with one multipler bit and shifting left by that bit’s position.

Generation of the PP row in hardware

AND gates ( A bits with qi) + a left shift by i.

Sum all PP rows with adders to form the the final product.

How are the PPs combined?

Array multiplier structure

A grid of ANDs (to make PP rows) plus full-adders that sum rows with ripple carries.

Because the higher-order shifted rows do not affect the low positions.

Why do some product LSBs settle early in an array multiplier.

Simple structure by carry ripple can make it slower than tree adders.

What is a trade-off of the array multiplier?

Product width is 2n bits

Multiplying two n-bit integers can need up to 2n bits to hold the result.

2n bits

How many bits do we need for n × n

(2^n - 1)^2 which is always less than 2^2n

The largest possible product of 2 n-bit numbers?

16 bits

If n = 8, then how much wide will be our product?

Sign extension

Replicating the sign bit to widen a signed number without changing its value.

Shifts increase width; sign-extension keeps sum aligned and preserves sign.

Why sign-extend the multiplicand when forming shifted PPs?

You can corrupt the sign and get an incorrect product.

What happens if you don’t sign-extend before adding shifted PPs?

Take the 2’s complement of both operands; the product is unchanged and the multiplier becomes unchanged.

How can you simplify multiplication with a negative multiplier?

(-A) × (-B) = A × B

Why does negating both operands keep the products unchanged?

The standard shift-and-add case (same as unsigned case)

After making the multiplier non-negative, what algorithm do you use?

Because the worst-case magnitude still fits below 2^(2n)

Why is the signed product also 2n bits?

Keep the full 2n-bit result to avoid overflow/overflow-like truncation.

What is the final caution for signed products?