Shifts, multiplication and Booth's algorithm

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Overflow test using carries? from Lesson 1.1.2
• −5 in 4-bit 2's complement? from Lesson 1.1.2
• What does a left shift by k places do to an unsigned number? from Lesson 0.1.3

1 · The Hook

🎣

Multiplying by 2 is a shift. But what happens when the number is negative? Shift −8 right with zeros coming in and it turns into a big positive number. Arithmetic shifts fix that. And when a processor multiplies signed numbers, it often uses Booth's algorithm, which skips over runs of 1s. GATE asks how many additions and subtractions Booth's method needs for a given multiplier.

2 · Predict First

🤔

In 8 bits, −8 is 1111 1000. If we shift it right by one place and fill the empty MSB with 0, what number do we get? What if we fill it with a copy of the old MSB instead?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

With 0: 0111 1100 = +124 (wrong). Copying the MSB: 1111 1100 = −4 (correct: −8 ÷ 2).

🗣️

In plain words

A logical shift treats bits as plain bits: zeros come in. An arithmetic right shift copies the sign bit in, so a 2's-complement number is halved correctly. Booth's algorithm multiplies by looking at pairs of neighbouring multiplier bits: it does work only where the bits change (start or end of a run of 1s), and nothing inside a run.

1. Shifts

• −7 = 1111 1001 → arithmetic right → 1111 1100 = −4 (−3.5 rounded down).
• A left shift overflows for signed numbers if the sign bit changes: 0100 0000 (64) → 1000 0000 (−128).

2. Signed multiplication

The product of two n-bit 2's-complement numbers needs 2n bits.

3. Booth's recoding

Look at each multiplier bit qᵢ with its right neighbour qᵢ₋₁ (take q₋₁ = 0):

Why it works: 0111 = 8 − 1, so ×0111 = ×(+1 0 0 −1): one add and one subtract instead of three adds. Multiplier 0111 0110 → digits +1 0 0 −1 +1 0 −1 0: 2 additions and 2 subtractions. Worst case: alternating bits (0101 0101) need an operation at every bit.

4. Booth's algorithm step by step

Registers A (starts 0), Q (multiplier), Q₋₁ (starts 0), M (multiplicand). Repeat n times: look at (Q₀, Q₋₁), do nothing / A − M / A + M, then arithmetic-shift right A, Q, Q₋₁ together. The product is A followed by Q. M = 3 (0011), Q = −2 (1110), n = 4:

Product A Q = 1111 1010 = −6 ✓.

4 · Visual

Booth recoding of the multiplier 0 1 1 1 0 1 1 0   (append q-1 = 0 on the right)

bits   :  0   1   1   1   0   1   1   0   [0]
pairs  : 01  11  11  10  01  11  10  00        (q_i, q_i-1) read right to left
digit  : +1   0   0  -1  +1   0  -1   0
          ^ run ends        ^ run ends
                   ^ run starts       ^ run starts
2 additions (+1) and 2 subtractions (-1)

5 · Worked Examples

Example 1 Easy

Arithmetic right shift of the 8-bit number 1111 1001 (−7). Result?

Solution

1111 1100 = −4.

Example 2 Medium

Booth-recode the multiplier 0111. How many additions and subtractions?

Solution

Digits +1 0 0 −1: one addition, one subtraction.

Example 3 GATE

With Booth's algorithm, how many additions plus subtractions are needed for the 8-bit multiplier 0101 0101?

Solution

Every pair is 10 or 01: 8 operations (4 subtractions, 4 additions), the worst case.

6 · GATE Traps

⚠️

• Arithmetic right shift copies the MSB; logical right shift inserts 0.
• Arithmetic right shift rounds towards −∞ (−7 → −4, not −3).
• Booth pairs are (current bit, bit to its right), with an imaginary 0 to the right of the LSB.
• 10 → subtract, 01 → add (not the other way round).

7 · Memory Hook

🧠

"Arithmetic shift keeps the sign. Booth: 10 subtract, 01 add, 00 and 11 just shift."

8 · Connect the Dots

Chapter 1.1 is complete. Not every bit pattern is a binary number: Chapter 1.2 looks at codes (BCD, excess-3, Gray code, parity) used for decimal digits, rotary encoders and error detection.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markArithmetic shift

The 8-bit 2's-complement number 1111 1001 is arithmetic-shifted right by 1. What value results?

Numerical answer: ________

Q2MCQ1 markLogical shift

The 8-bit 2's-complement number 1111 1001 (−7) is logically shifted right by 1. The result read as 2's complement is:

• (A) −3
• (B) +124
• (C) −4
• (D) +3

Q3NAT2 marksBooth count

Using Booth's algorithm, how many additions plus subtractions are performed for the multiplier 0111 0110?

Numerical answer: ________

Q4NAT2 marksBooth trace

Booth's algorithm multiplies M = 5 by Q = −3 in 4-bit registers. How many add or subtract steps are performed in total?

Numerical answer: ________

Q5NAT1 markProduct width

Minimum number of bits for the product of two 16-bit 2's-complement numbers?

Numerical answer: ________

10 · Rule Card

• Logical shifts insert 0; arithmetic right shift copies the MSB (÷2, rounding towards −∞).
• Signed n × n product needs 2n bits.
• Booth pairs (qᵢ, qᵢ₋₁), q₋₁ = 0: 10 → −M, 01 → +M, 00/11 → nothing; then arithmetic shift right of A, Q, Q₋₁.
• Booth operations = number of 01 and 10 pairs; worst case alternating bits.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

logical shiftarithmetic shiftrounding of arithmetic right shiftsigned multiplication widthBooth recodingBooth digits +1, 0, −1Booth's algorithm registers A, Q, Q₋₁, Mcounting Booth operations

12 · Answer Vault