Multiply without multiply

Implement multiplication using only addition, subtraction, and bit shifts.

multiplication bit-manipulation arithmetic

Write a function `multiply(a, b)` that returns the product of two integers `a` and `b` WITHOUT using the `*` operator. You may use only the following operations: addition (`+`), subtraction (`-`), bit shifts (`<<`, `>>`), bitwise AND (`&`), bitwise OR (`|`), bitwise XOR (`^`), and comparison operators. You may NOT use `*`, `/`, `//`, `%`, `divmod`, `pow`, `math.prod`, or any other multiplication/division-related built-in or library function.

Assume `a` and `b` are integers in the range `-10^9` to `10^9`. Your function must handle negative operands correctly and must not overflow beyond Python's integer limits (Python ints are arbitrary precision).

Your solution should be efficient enough to handle the full range within a reasonable time (linear in the number of bits, i.e., O(log |a|) operations).

Constraints

- `a`, `b` are integers, each with absolute value up to 10^9.
- Time: O(log |a|) iterations or better.
- Space: O(1) extra.

Example

>>> multiply(3, 4)
12
>>> multiply(-3, 4)
-12
>>> multiply(0, 12345)
0
>>> multiply(123456789, 987654321)
121932631112635269

8 points ~12 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use the Russian peasant multiplication algorithm: double one operand and halve the other, adding when the halved operand is odd.

Handle signs separately: compute the absolute values, multiply, then apply the sign based on the parity of negative inputs.

Remember that `x >> 1` is integer division by 2, and `x << 1` is multiplication by 2.

Break your loop when the halved operand becomes 0.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.