Using the standard multiplication algorithm, a run of 1s in the multiplier in means that we have to add as many successively shifted multiplicand values as the number of 1s in the run.

      0010_two
x     0111_two
  --------
+     0010  multiplicand shifted by 0 bits left
+    0010   multiplicand shifted by 1 bit left
+   0010    multiplicand shifted by 2 bits left
+  0000
  --------
  00001110_two

We can rewrite 2ⁱ - 2^i-j as:

2i - 2i-j	=	2i-j x (2j - 1)
	=	2i-j x (2j-1 + 2j-2 + ... + 20)
	=	2i-1 + 2i-2 + ... + 2i-j

For example 0111_two = 2³_ten - 2⁰_ten. So 0010_two x 0111_two can be written as:

0010_two x (1000_two - 0001_two)

Or to make it look like the multiplication before:

      0010_two
x     0111_two
  --------
-     0010  = 0010_two x - 0001_two
+    0000
+   0000
+  0010     = 0010_two x + 1000_two
  --------
  00001110_two

The core of Booth's algorithm is examining two bits of the multiplicand at each step. The following diagram is the third multiplication algorithm in the textbook, only modified a little.

Note that Booth's algorithm uses an extra bit on the right of the least significant bit in the product register. This bit starts out as 0 because:

1. if bit 0 is a 1, we want to subtract the multiplicand from the product register
2. if bit 0 is a 0, we do not want to perform any operations

When the shift in step 2 in the diagram is performed, the rightmost (least significant) bit in the product register is placed into this extra bit.

Why does Booth's algorithm work for negative numbers? To see why, we need to rewrite a multiplication into the steps that Booth's algorithm operates on.

Booth's algorithm looks at adjacent pairs of bits. Suppose that a_i is bit i of the multiplier and b_i is bit i of the multiplicand. The following table shows what Booth's algorithm would do:

ai	ai-1	Operation	ai-1 - ai
0	0	Do nothing	0
0	1	Add b	1
1	0	Subtract b	-1
1	1	Do nothing	0

The rightmost column is the value we multiply the shifted value of b by before adding it to the Product register.

We can rewrite the product a x b as:

  (a_-1 - a₀) x b x 2⁰
+ (a₀  - a₁) x b x 2¹
+ (a₁  - a₂) x b x 2²
...
+ (a₃₀ - a₃₁) x b x 2³¹

which can be simplified to (using the equation for 2ⁱ - 2^i-j and the fact that a_-1 = 0):

b x (a₃₁ x -2³¹ + a₃₀ x 2³⁰ + a₂₉ x 2²⁹ + ... + a₁ x 2¹ + a₀ x 2⁰)

We are multiplying b by the two's complement representation of a!