Comment on page

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;
}