1354. Multiply Two Numbers Using Bit Shifts

Given two integers a and b, compute their product using only shifts and additions (the Russian peasant / shift-and-add method), without the multiplication operator.

Input: A JSON object {"a": <integer>, "b": <integer>}.

Output: Return a * b.

Examples

Input: {"a":13,"b":7}
Output: 91
Explanation: 13 shifted and added per set bit of 7 gives 91.

Input: {"a":-6,"b":7}
Output: -42
Explanation: Magnitudes multiply to 42 and the sign is negative -> -42.

Constraints

• -10^6 <= a, b <= 10^6

Asked by