Divide two integers without using the multiplication, division, and modulo operators

WBOY
Release: 2023-09-21 12:41:02
forward
1207 people have browsed it

Divide two integers without using the multiplication, division, and modulo operators

In this problem, we only need to divide two integers without using multiplication, division and modulo operators. Although we can use addition, multiplication or bit operations.

The problem statement states that we will get two integers x and y. Without using multiplication, division, or the modulo operator, we need to determine the quotient of x divided by y.

Example

Input: x=15, y=5

Output: 3

Input: x=10, y=4

Output: 2

Input: x=-20, y=3

Output:-6

method

Method 1 (Using Simple Math)

In this method, we will use a simple mathematical algorithm. Here are the step-by-step instructions for what we will follow -

  • We will continue to subtract the divisor (i.e. y) from the dividend (i.e. x) until x is greater than or equal to y.

  • When y is greater than x, that is, the divisor is greater than the dividend, the dividend becomes the remainder, and the number of subtractions becomes the quotient.

  • Store the number of times the subtraction is performed in a variable and return it, this is the output we want.

Example

The following is the C implementation of the above algorithm &minnus;

#include  #include  using namespace std; long long division(long long a,long long b) // where a is dividend and b is divisor { long long sign=1; if((a<0) ^( b<0)) // - ^ - = +,+ ^ - = - , - ^ + = - , + ^ + = + { sign=-1; } long long m=abs(a); long long n=abs(b); long long count=0; // for storing the quotient while(m>=n){ m=m-n; count++; } if(sign==-1) // when sign is negative { count=-count; } return count; } int main(){ long long a=-21474; long long b=2; long long val=division(a,b); cout<
        
Copy after login

Output

-10737
Copy after login

Time complexity: O(a/b)

Space complexity: O(1)

Method 2 (using bit operations)

  • Since any number can be represented in the form of 0 or 1, the quotient can be represented in binary form using the shift operator.

  • Use a for loop to iterate the bit positions of the divisor from 31 to 1.

  • Find the first bit where the divisor, that is, b<

  • When verifying the next position, add the result to the temp variable to ensure that temp (b<

  • Update the quotient each time by calculating the quotientOR1<

  • Return to the quotient after updating the corresponding symbol.

Example

The following is the C implementation of the above method -

#include  #include  using namespace std; long long division(long long a,long long b) // where a is dividend and b is divisor { long long sign=1; if((a<0) ^( b<0)) // - ^ - = +,+ ^ - = - , - ^ + = - , + ^ + = + { sign=-1; } long long m=abs(a); long long n=abs(b); long long count=0; // for storing the quotient long long temp=0; for (int j = 31; j >= 0; --j){ if (temp + (n << j) <= m){ temp += n << j; count |= 1L << j; } } if(sign==-1) // when sign is negative { count=-count; } return count; } int main(){ long long a=49; long long b=5; long long val=division(a,b); cout<
        
Copy after login

Output

9 -3
Copy after login

Time complexity: O(log(a))

Space complexity: O(1),because it does not use extra space.

Method 3 (using logarithmic function)

In this method, we will use a simple logarithmic function to calculate the quotient.

As we all know,

$$\mathrm{In(\frac{a}{b})\:=\:In(a)\:-\:In(b)}$$

can be further modified to

$$\mathrm{\frac{a}{b}\:=\:e^{(In(a)\:-\:In(b))}}$$

So this is the basic idea to solve the given problem using this efficient method.

Below are step-by-step instructions for the method we will follow -

  • If one of them (i.e. dividend or divisor) is 0, we will return 0.

  • Now we will check the symbol using the exclusive OR function (XOR) to store the symbol in a variable.

  • If the divisor is 1, the dividend is returned directly.

  • Now, declare a variable and use theexp< 将等于 $\mathrm{e^{(In(a)\:-\:In(b))}}$ 的值存储在其中/b> function and thelogfunction.

  • Log and exp are built-in functions in C. The log function returns the natural logarithm of the input number, and exp returns a value equal to e plus the input value.

Example

The following is the C implementation of the above method -

#include  #include  using namespace std; long long int divide(long long int a,long long int b){ long long int sign=1; if(a==0||b==0) // when a is zero or b is zero { return 0; } if((a>0) ^ (b>0)) // - ^ - = +,+ ^ - = - , - ^ + = - , + ^ + = + { sign=-1; } if(b==1) // when b is 1 then it will return a example 51/1 = 51 { sign==-1?-a:a; return a; } long long int m=abs(a); long long int n=abs(b); //log function return the logarithmic value of the entered value with base e i.e. natural log of the entered value //exp function return the value equal to e^(entered value) long long int ans =exp(log(m) - log(n)) + 0.0000000001; // if it gives the value in decimal we will add from 0.0000000001 to account for accuracy errors if(sign==-1) // when sign is negative return the negative ans { return -ans; } return ans; } int main(){ long long int ans=divide(47,-9); cout<
         
Copy after login

Output

-5
Copy after login

Time complexity: O(1),, because it takes constant time to perform this operation.

Space complexity: O(1),because it does not use extra space.

in conclusion

In this article, we learn to divide two integers without using multiplication, division, or modulo operators. We learned to solve problems in different ways with different efficiencies. They use simple mathematics, bit operations, and logarithmic functions. Among them, using the logarithmic function is the most efficient method because its time complexity is O(1), which is the smallest among all methods.

I hope this article helped you solve all the concepts regarding this topic.

The above is the detailed content of Divide two integers without using the multiplication, division, and modulo operators. For more information, please follow other related articles on the PHP Chinese website!

source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!