Multiply two signed numbers with Booth's algorithm. Write the multiplier Q in n-bit two's complement. For each bit position i from 0 to n − 1, look at bit i and the bit to its right (bit i − 1, with an imaginary 0 to the right of bit 0):
1 0: sub: subtract M × 2ⁱ;0 1: add: add M × 2ⁱ;0 0or1 1: none.
Input
One line: M, Q and n (2 ≤ n ≤ 16; Q fits in n bits as a signed number, and M is any whole number).
Output
Two lines: the operation for each position from i = 0 up, separated by spaces, then the product.
Examples
7 -3 4
sub add sub none -21
3 3 4
sub none add none 9
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Write Q in n-bit two's complement: q = Q & ((1 << n) - 1).
Hint 2
Go from i = 0 to n - 1 with prev = 0: look at the pair (bit i of q, prev). 10 means sub, 01 means add, 00 and 11 mean none. Then prev = bit i.
Hint 3
The product adds M × 2^i for each add and subtracts it for each sub.
Solution
Show one correct solution (try it yourself first)
m, q, n = map(int, input().split())
bits = q & ((1 << n) - 1)
ops, product, prev = [], 0, 0
for i in range(n):
bit = (bits >> i) & 1
if (bit, prev) == (1, 0):
ops.append("sub")
product -= m << i
elif (bit, prev) == (0, 1):
ops.append("add")
product += m << i
else:
ops.append("none")
prev = bit
print(" ".join(ops))
print(product)