Divide two integers without using multiplication and division operator

Try it on GfG Practice

Given two integers a and b, the task is to find the quotient after dividing a by b without using multiplication, division, and mod operator.

Note: If the quotient is strictly greater than 2³¹ - 1, return 2³¹ - 1 and if the quotient is strictly less than -2³¹, then return -2³¹.

Examples: 

Input : a = 10, b = 3
Output : 3

Input: a = 43, b = -8
Output:  -5 

[Naive Approach] By Repeated Subtraction - O(a/b) Time and O(1) Space

The basic idea is to first find the sign of quotient. The sign of the quotient will be negative only when the sign of dividend and divisor are different. Now, convert both the dividend and divisor to positive numbers and keep subtracting the divisor from the dividend until the dividend becomes less than the divisor. The dividend becomes the remainder, and the number of times subtraction is done becomes the quotient. Finally, we append the sign to the quotient to get the final result.

This approach fails for large values of quotient.

// C++ Program to divide two integers by repeated subtraction #include <bits/stdc++.h> using namespace std; // Function to divide a by b and // return floor value of the result long long divide(long long a, long long b) {  if(a == 0)  return 0;    // The sign will be negative only if sign of   // divisor and dividend are different  int sign = ((a < 0) ^ (b < 0)) ? -1 : 1;    // Convert divisor and dividend to positive numbers  a = abs(a);  b = abs(b);    // Initialize the quotient  long long quotient = 0;    // Perform repeated subtraction till dividend  // is greater than divisor  while (a >= b) {  a -= b;  ++quotient;  }  return quotient * sign; } int main() {  long long a = 43, b = -8;  cout << divide(a, b) << "\n";  return 0; } 

// C Program to divide two integers by repeated subtraction #include <stdio.h> #include <stdlib.h> // Function to divide a by b and // return floor value of the result long long divide(long long a, long long b) {  if(a == 0)  return 0;    // The sign will be negative only if sign of   // divisor and dividend are different  int sign = ((a < 0) ^ (b < 0)) ? -1 : 1;    // Convert divisor and dividend to positive numbers  a = abs(a);  b = abs(b);    // Initialize the quotient  long long quotient = 0;    // Perform repeated subtraction till dividend  // is greater than divisor  while (a >= b) {  a -= b;  ++quotient;  }  return quotient * sign; } int main() {  long long a = 43, b = -8;  printf("%lld\n", divide(a, b));  return 0; } 

// Java Program to divide two integers by repeated subtraction class GfG {    // Function to divide a by b and  // return floor value of the result  static long divide(long a, long b) {  if(a == 0)  return 0;  // The sign will be negative only if sign of   // divisor and dividend are different  int sign = ((a < 0) ^ (b < 0)) ? -1 : 1;  // Convert divisor and dividend to positive numbers  a = Math.abs(a);  b = Math.abs(b);  // Initialize the quotient  long quotient = 0;  // Perform repeated subtraction till dividend  // is greater than divisor  while (a >= b) {  a -= b;  ++quotient;  }  return quotient * sign;  }  public static void main(String[] args) {  long a = 43, b = -8;  System.out.println(divide(a, b));  } } 

# Python Program to divide two integers by repeated subtraction # Function to divide a by b and # return floor value of the result def divide(a, b): if a == 0: return 0 # The sign will be negative only if sign of  # divisor and dividend are different sign = -1 if (a < 0) ^ (b < 0) else 1 # Convert divisor and dividend to positive numbers a = abs(a) b = abs(b) # Initialize the quotient quotient = 0 # Perform repeated subtraction till dividend # is greater than divisor while a >= b: a -= b quotient += 1 return quotient * sign if __name__ == "__main__": a = 43 b = -8 print(divide(a, b)) 

// C# Program to divide two integers by repeated subtraction using System; class GfG {    // Function to divide a by b and  // return floor value of the result  static long divide(long a, long b) {  if (a == 0)  return 0;    // The sign will be negative only if sign of   // divisor and dividend are different  int sign = ((a < 0) ^ (b < 0)) ? -1 : 1;    // Convert divisor and dividend to positive numbers  a = Math.Abs(a);  b = Math.Abs(b);    // Initialize the quotient  long quotient = 0;    // Perform repeated subtraction till dividend  // is greater than divisor  while (a >= b) {  a -= b;  ++quotient;  }  return quotient * sign;  }  static void Main(string[] args) {  long a = 43, b = -8;  Console.WriteLine(divide(a, b));  } } 

// JavaScript Program to divide two integers by repeated subtraction // Function to divide a by b and // return floor value of the result function divide(a, b) {  if (a === 0)   return 0;  // The sign will be negative only if sign of   // divisor and dividend are different  const sign = ((a < 0) ^ (b < 0)) ? -1 : 1;  // Convert divisor and dividend to positive numbers  a = Math.abs(a);  b = Math.abs(b);  // Initialize the quotient  let quotient = 0;  // Perform repeated subtraction till dividend  // is greater than divisor  while (a >= b) {  a -= b;  ++quotient;  }  return quotient * sign; } const a = 43, b = -8; console.log(divide(a, b)); 

-5 

Time complexity: O(a/b), where a is the dividend and b is the divisor.
Auxiliary space: O(1)

[Expected Approach] Using Bit Manipulation - O(log(a)) Time and O(1) Space

The idea is similar to the previous approach with the only difference that instead of subtracting one unit of divisor from the dividend, we can subtract multiple units of divisor at once until the dividend becomes smaller than divisor.

This can be easily done by iterating on the bit position i = 30 to 0. For each bit position i, where (divisor << i) is less than dividend, set the ith bit of the quotient and subtract (divisor << i) from the dividend. After iterating over all the bits, return the quotient with the corresponding sign.

// C++ implementation to Divide two // integers using Bit Manipulation #include <iostream> #include <limits.h> using namespace std; // Function to divide a by b and // return floor value it long long divide(long long a, long long b) {  // Handle overflow  if(a == INT_MIN && b == -1) return INT_MAX;    // The sign will be negative only if sign of   // divisor and dividend are different  int sign = ((a < 0) ^ (b < 0)) ? -1 : 1;  // remove sign of operands  a = abs(a);  b = abs(b);  // Initialize the quotient  long long quotient = 0;  // Iterate from most significant bit to   // least significant bit  for (int i = 31; i >= 0; --i) {  // Check if (divisor << i) <= dividend  if ((b << i) <= a) {  a -= (b << i);  quotient |= (1LL << i);  }  }  return sign * quotient; } int main() {  long long a = 43, b = -8;  cout << divide(a, b);  return 0; } 

// C implementation to Divide two // integers using Bit Manipulation #include <stdio.h> #include <limits.h> // Function to divide a by b and // return floor value it long long divide(long long a, long long b) {  // Handle overflow  if (a == INT_MIN && b == -1)  return INT_MAX;    // The sign will be negative only if sign of   // divisor and dividend are different  int sign = ((a < 0) ^ (b < 0)) ? -1 : 1;  // remove sign of operands  a = llabs(a);  b = llabs(b);  // Initialize the quotient  long long quotient = 0;  // Iterate from most significant bit to   // least significant bit  for (int i = 31; i >= 0; --i) {  // Check if (divisor << i) <= dividend  if ((b << i) <= a) {  a -= (b << i);  quotient |= (1LL << i);  }  }  return sign * quotient; } int main() {  long long a = 43, b = -8;  printf("%lld\n", divide(a, b));  return 0; } 

// Java implementation to Divide two // integers using Bit Manipulation class GfG {    // Function to divide a by b and  // return floor value it  static long divide(long a, long b) {  // Handle overflow  if (a == Integer.MIN_VALUE && b == -1)  return Integer.MAX_VALUE;  // The sign will be negative only if sign of   // divisor and dividend are different  int sign = ((a < 0) ^ (b < 0)) ? -1 : 1;  // remove sign of operands  a = Math.abs(a);  b = Math.abs(b);  // Initialize the quotient  long quotient = 0;  // Iterate from most significant bit to   // least significant bit  for (int i = 31; i >= 0; --i) {  // Check if (divisor << i) <= dividend  if ((b << i) <= a) {  a -= (b << i);  quotient |= (1L << i);  }  }  return sign * quotient;  }  public static void main(String[] args) {  long a = 43, b = -8;  System.out.println(divide(a, b));  } } 

# Python implementation to Divide two # integers using Bit Manipulation # Function to divide a by b and # return floor value it def divide(a, b): # Handle overflow if a == -2**31 and b == -1: return 2**31 - 1 # The sign will be negative only if sign of  # divisor and dividend are different sign = -1 if (a < 0) ^ (b < 0) else 1 # remove sign of operands a = abs(a) b = abs(b) # Initialize the quotient quotient = 0 # Iterate from most significant bit to  # least significant bit for i in range(31, -1, -1): # Check if (divisor << i) <= dividend if (b << i) <= a: a -= (b << i) quotient |= (1 << i) return sign * quotient if __name__ == "__main__": a = 43 b = -8 print(divide(a, b)) 

// C# implementation to Divide two // integers using Bit Manipulation using System; class GfG {    // Function to divide a by b and  // return floor value it  static long divide(long a, long b) {    // Handle overflow  if (a == int.MinValue && b == -1)  return int.MaxValue;  // The sign will be negative only if sign of   // divisor and dividend are different  int sign = ((a < 0) ^ (b < 0)) ? -1 : 1;  // remove sign of operands  a = Math.Abs(a);  b = Math.Abs(b);  // Initialize the quotient  long quotient = 0;  // Iterate from most significant bit to   // least significant bit  for (int i = 31; i >= 0; --i) {    // Check if (divisor << i) <= dividend  if ((b << i) <= a) {  a -= (b << i);  quotient |= (1L << i);  }  }  return sign * quotient;  }  static void Main() {  long a = 43, b = -8;  Console.WriteLine(divide(a, b));  } } 

-5

Time Complexity: O(log(a)), as we are iterating over all the bits of a.
Auxiliary Space: O(1)