Russian Peasant (Multiply two numbers using bitwise operators)

Given two integers a and b, the task is to multiply them without using the multiplication operator. Instead of that, use the Russian Peasant Algorithm.

Examples:

Input: a = 2, b = 5
Output: 10
Explanation: Product of 2 and 5 is 10.

Input: a = 6, b = 9
Output: 54
Explanation: Product of 6 and 9 is 54.

Input: a = 8, b = 8
Output: 64
Explanation: Product of 8 and 8 is 64.

The idea is to break multiplication into a series of additions using the Russian Peasant Algorithm. Instead of directly multiplying a and b, we repeatedly halve b and double a, leveraging the fact that multiplication can be rewritten as repeated addition. If b is odd at any step, we add a to the result since that part of the multiplication cannot be handled by doubling alone. This process continues until b becomes zero.

Steps to implement the above idea:

• Initialize result to 0.
• Loop while b > 0.
• If b is odd, add a to result.
• Double a and halve b.
• Repeat until b becomes 0.
• Return result

How does this work?  The value of a*b is same as (a*2)*(b/2) if b is even, otherwise the value is same as ((a*2)*(b/2) + a). In the while loop, we keep multiplying ‘a’ with 2 and keep dividing ‘b’ by 2. If ‘b’ becomes odd in loop, we add ‘a’ to ‘res’. When value of ‘b’ becomes 1, the value of ‘res’ + ‘a’, gives us the result. 

// C++ Code to multiply 2 numbers // using Russian Peasant Algorithm #include <bits/stdc++.h> using namespace std; // Function to multiply two numbers using  // Russian Peasant Algorithm int multiply(int a, int b) {  int result = 0;    while (b > 0) {    // If b is odd, add a to result  if (b & 1) {  result += a;  }    // Double a and halve b  a <<= 1;  b >>= 1;  }    return result; } int main() {    int a = 2, b = 5;  cout << multiply(a, b) << endl;  return 0; } 

// Java Code to multiply 2 numbers // using Russian Peasant Algorithm import java.util.*; class GfG {    // Function to multiply two numbers using   // Russian Peasant Algorithm  static int multiply(int a, int b) {  int result = 0;    while (b > 0) {    // If b is odd, add a to result  if ((b & 1) == 1) {  result += a;  }    // Double a and halve b  a <<= 1;  b >>= 1;  }    return result;  }  public static void main(String[] args) {    int a = 2, b = 5;  System.out.println(multiply(a, b));  } } 

# Python Code to multiply 2 numbers # using Russian Peasant Algorithm # Function to multiply two numbers using  # Russian Peasant Algorithm def multiply(a, b): result = 0 while b > 0: # If b is odd, add a to result if b & 1: result += a # Double a and halve b a <<= 1; b >>= 1; return result if __name__ == "__main__": a, b = 2, 5 print(multiply(a, b)) 

// C# Code to multiply 2 numbers // using Russian Peasant Algorithm using System; class GfG {    // Function to multiply two numbers using   // Russian Peasant Algorithm  static int multiply(int a, int b) {  int result = 0;    while (b > 0) {    // If b is odd, add a to result  if ((b & 1) == 1) {  result += a;  }    // Double a and halve b  a <<= 1;  b >>= 1;  }    return result;  }  public static void Main() {    int a = 2, b = 5;  Console.WriteLine(multiply(a, b));  } } 

// JavaScript Code to multiply 2 numbers // using Russian Peasant Algorithm // Function to multiply two numbers using  // Russian Peasant Algorithm function multiply(a, b) {  let result = 0;    while (b > 0) {    // If b is odd, add a to result  if (b & 1) {  result += a;  }    // Double a and halve b  a <<= 1;  b >>= 1;  }    return result; } // Hardcoded input values let a = 2, b = 5; console.log(multiply(a, b)); 

10 

Time Complexity: O(log b), each iteration halves b, leading to logarithmic iterations.
Space Complexity: O(1), only a few integer variables are used, requiring constant space.