Recursive Multiply

8.5 Recursive Multiply: Write a recursive function to multiply two positive integers without using the * operator (or / operator). You can use addition, subtraction, and bit shifting, but you should minimize the number of those operations.

  • With this problem, I give myself a big fuck ya. 5 min solution.

  • The multiplication of two numbers is negative only if either of the numbers are negative. XOR is perfect for this.

  • Multiplication is the same thing as adding the other number n amount of times. Either one can work, but I chose the max number to count the min number n amount of times, that way I minimize the number of times, or operations that I need to count.

int rec_mult(int a, int b, int sol, int count) {
    if (count >= abs(min(a, b))) {
        bool neg = (a < 0 ^ b < 0);
        if (neg) return (-sol);
        return sol;
    return rec_mult(a, b, sol + abs(max(a, b)), ++count);

int mult(int a, int b) {
    return rec_mult(a, b, 0, 0);

int main() {
    cout << mult(10, 3) << endl;
    cout << mult(2, -3) << endl;
    cout << mult(23, -10) << endl;
    cout << mult(-500, 0) << endl;
    cout << mult(10, -1) << endl;

Last updated