Coding questions

Implement multiplication without using the multiplication operator

This question evaluates proficiency in bitwise arithmetic, integer overflow semantics, sign handling, and algorithmic efficiency for implementing multiplication without using multiplication or division operators.

Implement int multiply(int a, int b) without using * or /. You may use +, −, bitwise operators, and shifts. Requirements:

Handle negatives, zero, and the corner case INT_MIN * −1.
Achieve O(log |b|) additions via shift‑and‑add (Russian peasant), not naive O(|b|) repeated addition.
Assume 32‑bit signed ints. First implement unchecked overflow (two’s‑complement wrap), then a safe version that saturates to INT_MAX/INT_MIN on overflow without using 64‑bit types.
Analyze time and space complexity and prove correctness for all sign combinations.
Provide unit tests: 0×x, 1×x, −1×x, powers of two, random pairs, INT_MAX×2, INT_MIN×2, INT_MIN×−1. Follow‑ups: how would you extend to big integers and compare with Karatsuba? What changes if the platform lacks arithmetic right shift?

Unchecked 32-bit Multiply Without *

Return a*b using shift-and-add with two-complement 32-bit wraparound.

Examples

Example 1

Input: (3, 5)
Output: 15

Explanation: Positive values.

Example 2

Input: (-7, 6)
Output: -42

Explanation: Negative sign.

Hints

Choose a representation that makes the requested operation direct.
Handle empty inputs and boundary cases first.

Saturating 32-bit Multiply Without *

Return a*b using shift-and-add, saturating to INT_MAX or INT_MIN on overflow.