Implement multiplication without using the multiplication operator

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?