Multiply two numbers without using a multiplication operator or loops
Given two integers, multiply them without using the multiplication operator or conditional loops.
1. Using Recursion
The idea is that for given two numbers a and b, we can get a×b by adding an integer a exactly b times to the result. This approach is demonstrated below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> using namespace std; int mul(int a, int b) { // base cases if (a == 0 || b == 0) { return 0; } if (b == 1) { return a; } if (a == 1) { return b; } return a + mul(a, b - 1); } int multiply(int a, int b) { int m = mul(a, abs(b)); return (b < 0) ? -m : m; } int main() { cout << multiply(3, 4) << " " << multiply(-3, -4) << " " << multiply(-3, 4) << " " << multiply(3, -4); return 0; } |
Output:
12 12 -12 -12
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Main { public static int mul(int a, int b) { // base cases if (a == 0 || b == 0) { return 0; } if (b == 1) { return a; } if (a == 1) { return b; } return a + mul(a, b - 1); } public static int multiply(int a, int b) { int m = mul(a, Math.abs(b)); return (b < 0) ? -m : m; } public static void main(String[] args) { System.out.print(multiply(3, 4) + " " + multiply(-3, -4) + " " + multiply(-3, 4) + " " + multiply(3, -4)); } } |
Output:
12 12 -12 -12
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
def mul(a, b): # base cases if a == 0 or b == 0: return 0 if b == 1: return a if a == 1: return b return a + mul(a, b - 1) def multiply(a, b): m = mul(a, abs(b)) return -m if (b < 0) else m if __name__ == '__main__': print(multiply(3, 4)) print(multiply(-3, -4)) print(multiply(-3, 4)) print(multiply(3, -4)) |
Output:
12
12
-12
-12
2. Iterative solution using Bitwise operators
If loops are allowed, we can use the following relation:
multiply(a, b) = | multiply(a*2, b/2) if b is even
| b + multiply(a*2, b/2) if b is odd
| b + multiply(a*2, b/2) if b is odd
The implementation can be seen below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <iostream> using namespace std; int multiply(int a, int b) { // flag to store if the result is positive or negative bool isNegative = false; // if both numbers are negative, make both numbers // positive since the result will be positive anyway if (a < 0 && b < 0) { a = -a, b = -b; } // if only `a` is negative, make it positive // and mark the result as negative if (a < 0) { a = -a, isNegative = true; } // if only `b` is negative, make it positive // and mark the result as negative if (b < 0) { b = -b, isNegative = true; } // initialize result int result = 0; // run till `b` becomes 0 while (b) { // if `b` is odd, add `b` to the result if (b & 1) { result += a; } // multiply `a` by 2 a = a << 1; // divide `b` by 2 b = b >> 1; } return (isNegative) ? -result : result; } int main() { cout << multiply(3, 4) << " " << multiply(-3, -4) << " " << multiply(-3, 4) << " " << multiply(3, -4); return 0; } |
Output:
12 12 -12 -12
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
class Main { public static int multiply(int a, int b) { // flag to store if the result is positive or negative boolean isNegative = false; // if both numbers are negative, make both numbers // positive since the result will be positive anyway if (a < 0 && b < 0) { a = -a; b = -b; } // if only `a` is negative, make it positive // and mark the result as negative if (a < 0) { a = -a; isNegative = true; } // if only `b` is negative, make it positive // and mark the result as negative if (b < 0) { b = -b; isNegative = true; } // initialize result by 0 int result = 0; // run till `b` becomes 0 while (b != 0) { // if `b` is odd, add `b` to the result if ((b & 1) == 1) { result += a; } a = a << 1; // multiply `a` by 2 b = b >> 1; // divide `b` by 2 } return (isNegative) ? -result : result; } public static void main(String[] args) { System.out.print(multiply(3, 4) + " " + multiply(-3, -4) + " " + multiply(-3, 4) + " " + multiply(3, -4)); } } |
Output:
12 12 -12 -12
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
def multiply(a, b): # flag to store if the result is positive or negative isNegative = False # if both numbers are negative, make both numbers # positive since the result will be positive anyway if a < 0 and b < 0: a = -a b = -b # if only `a` is negative, make it positive # and mark the result as negative if a < 0: a = -a isNegative = True # if only `b` is negative, make it positive # and mark the result as negative if b < 0: b = -b isNegative = True # initialize result by 0 result = 0 # run till `b` becomes 0 while b: # if `b` is odd, add `b` to the result if b & 1: result += a a = a << 1 # multiply `a` by 2 b = b >> 1 # divide `b` by 2 return -result if isNegative else result if __name__ == '__main__': print(multiply(3, 4)) # 12 print(multiply(-3, -4)) # 12 print(multiply(-3, 4)) # -12 print(multiply(3, -4)) # -12 |
The recursive version of the above solution is left as an exercise to the readers.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)