<section class="calculator-description">
<h2>Booth's Algorithm Calculator</h2>
<p>
Multiply two signed binary numbers using Booth's algorithm and see every step.
Enter a multiplicand and a multiplier in decimal or binary and choose the bit width.
The calculator shows the full step-by-step table: the A, Q and Q<sub>-1</sub>
registers, the operation performed in each cycle, and the final product in both
binary and decimal.
</p>
<h3>What is Booth's Algorithm?</h3>
<p>
Booth's algorithm is a method for multiplying signed binary numbers in
<strong>two's complement</strong> form. Andrew Donald Booth developed it in 1950.
Simple shift-and-add multiplication only works on unsigned numbers. Booth's method
handles positive and negative numbers the same way, and it skips over runs of 1s in
the multiplier, which can reduce the number of additions and subtractions. That's why
it's a core topic in computer organization and architecture courses and is still used
in hardware multiplier design.
</p>
<h3>How to Use the Calculator</h3>
<ol>
<li>Enter the <strong>multiplicand (M)</strong> and the <strong>multiplier (Q)</strong> as decimal integers or binary values.</li>
<li>Choose the <strong>number of bits (n)</strong>. Both numbers must fit in the range −2<sup>n−1</sup> to 2<sup>n−1</sup> − 1.</li>
<li>Click <strong>Calculate</strong> to see the step-by-step table and the final product.</li>
</ol>
<h3>How Booth's Algorithm Works</h3>
<p>The algorithm uses these registers:</p>
<ul>
<li><strong>M</strong>: the multiplicand</li>
<li><strong>Q</strong>: the multiplier</li>
<li><strong>A</strong>: the accumulator, which starts at 0</li>
<li><strong>Q<sub>-1</sub></strong>: an extra bit to the right of Q, which starts at 0</li>
<li><strong>Count</strong>: the number of bits, n</li>
</ul>
<p>In each cycle, look at the last bit of Q (Q<sub>0</sub>) and Q<sub>-1</sub>:</p>
<table>
<thead>
<tr>
<th>Q<sub>0</sub> Q<sub>-1</sub></th>
<th>Operation</th>
</tr>
</thead>
<tbody>
<tr><td>0 0</td><td>Arithmetic shift right only</td></tr>
<tr><td>1 1</td><td>Arithmetic shift right only</td></tr>
<tr><td>1 0</td><td>A = A − M, then arithmetic shift right</td></tr>
<tr><td>0 1</td><td>A = A + M, then arithmetic shift right</td></tr>
</tbody>
</table>
<p>
The arithmetic shift right moves A, Q and Q<sub>-1</sub> one bit to the right as a
single unit and keeps the sign bit of A. Repeat for <strong>n</strong> cycles. The
final product is the 2n-bit value formed by A and Q together.
</p>
<h3>Worked Example: 7 × (−3) Using 4 Bits</h3>
<p>M = 0111 (7), −M = 1001, Q = 1101 (−3)</p>
<table>
<thead>
<tr>
<th>Step</th>
<th>Q<sub>0</sub> Q<sub>-1</sub></th>
<th>Operation</th>
<th>A</th>
<th>Q</th>
<th>Q<sub>-1</sub></th>
</tr>
</thead>
<tbody>
<tr><td>Initial</td><td>–</td><td>–</td><td>0000</td><td>1101</td><td>0</td></tr>
<tr><td>1</td><td>1 0</td><td>A = A − M → 1001, shift</td><td>1100</td><td>1110</td><td>1</td></tr>
<tr><td>2</td><td>0 1</td><td>A = A + M → 0011, shift</td><td>0001</td><td>1111</td><td>0</td></tr>
<tr><td>3</td><td>1 0</td><td>A = A − M → 1010, shift</td><td>1101</td><td>0111</td><td>1</td></tr>
<tr><td>4</td><td>1 1</td><td>Shift only</td><td>1110</td><td>1011</td><td>1</td></tr>
</tbody>
</table>
<p>
<strong>Result:</strong> A:Q = 11101011, which is <strong>−21</strong> in two's complement.
</p>
<h3>Frequently Asked Questions</h3>
<h4>Why does Booth's algorithm need the Q<sub>-1</sub> bit?</h4>
<p>
Comparing Q<sub>0</sub> with Q<sub>-1</sub> tells the algorithm where a run of 1s
starts or ends in the multiplier. It subtracts at the start of a run and adds at the
end, instead of adding once for every 1 bit.
</p>
<h4>Does Booth's algorithm work with negative numbers?</h4>
<p>
Yes. That's its main advantage. Both operands are in two's complement, and the
product comes out correctly signed with no sign correction step.
</p>
<h4>Is Booth's algorithm always faster?</h4>
<p>
No. It saves operations when the multiplier has long runs of 1s. With alternating
bits such as 0101…, it can need more additions and subtractions than ordinary
shift-and-add multiplication. Radix-4 (modified) Booth encoding fixes this and is
what modern hardware uses.
</p>
<h4>How many bits does the product have?</h4>
<p>For n-bit operands, the product is 2n bits, held in A and Q together.</p>
</section>
<script type="application/ld+json">
{
"@context": "https://schema.org",
"@type": "FAQPage",
"mainEntity": [
{
"@type": "Question",
"name": "Why does Booth's algorithm need the Q-1 bit?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Comparing Q0 with Q-1 tells the algorithm where a run of 1s starts or ends in the multiplier. It subtracts at the start of a run and adds at the end, instead of adding once for every 1 bit."
}
},
{
"@type": "Question",
"name": "Does Booth's algorithm work with negative numbers?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Yes. That's its main advantage. Both operands are in two's complement, and the product comes out correctly signed with no sign correction step."
}
},
{
"@type": "Question",
"name": "Is Booth's algorithm always faster?",
"acceptedAnswer": {
"@type": "Answer",
"text": "No. It saves operations when the multiplier has long runs of 1s. With alternating bits it can need more operations than ordinary shift-and-add multiplication. Radix-4 (modified) Booth encoding fixes this and is what modern hardware uses."
}
},
{
"@type": "Question",
"name": "How many bits does the product have?",
"acceptedAnswer": {
"@type": "Answer",
"text": "For n-bit operands, the product is 2n bits, held in A and Q together."
}
}
]
}
</script>