不使用乘法、除法和取模运算符来进行两个整数的除法-C++-PHP中文网

不使用乘法、除法和取模运算符来进行两个整数的除法

WBOY

发布： 2023-09-21 12:41:02

转载

1831人浏览过

不使用乘法、除法和取模运算符来进行两个整数的除法

在这个问题中，我们只需要将两个整数相除，而不需要使用乘法、除法和取模运算符。尽管我们可以使用加法、乘法或位操作。

问题陈述指出我们将得到两个整数 x 和 y。在不使用乘法、除法或取模运算符的情况下，我们需要确定 x 除以 y 后的商。

示例

输入：x=15，y=5

输出：3

输入：x=10，y=4

输出：2

输入：x=-20，y=3

输出：-6

方法

方法1（使用简单的数学）

在这种方法中，我们将使用一个简单的数学算法。下面是我们要遵循的步骤的分步说明 -

我们将从被除数（即 x）中不断减去除数（即 y），直到 x 大于或等于 y。
当 y 大于 x 时，即除数大于被除数，被除数变为余数，减法次数变为商。
将减法执行的次数存储在变量中并返回它，这是我们想要的输出。

示例

下面是上述算法的 C++ 实现 &minnus;

#include <iostream>
#include <bits/stdc++.h>
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<<val<<endl;
   return 0;
}

登录后复制

输出

-10737

登录后复制

时间复杂度：O(a/b)

空间复杂度：O(1)

方法 2（使用位操作）

由于任何数字都可以用 0 或 1 的形式表示，因此可以使用移位运算符以二进制形式表示商。
使用 for 循环迭代除数从 31 到 1 的位位置。
找到除数即 b
验证下一个位置时，将结果添加到 temp 变量中，以确保 temp+(b
每次通过计算商来更新商OR 1
更新相应符号后返回商。

人声去除
用强大的AI算法将声音从音乐中分离出来

23

查看详情

示例

下面是上述方法的 C++ 实现 -

#include <iostream>
#include <bits/stdc++.h>
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<<val<<endl;
   a=-18,b=5;
   cout<<division(a,b);
   
   return 0;
}

登录后复制

输出

9
-3

登录后复制

时间复杂度：O(log(a))

空间复杂度：O(1)，因为它不使用额外的空间。

方法 3（使用对数函数）

在这种方法中，我们将使用一个简单的对数函数来计算商。

众所周知，

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

可以进一步修改为

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

因此，这是使用这种有效方法解决给定问题的基本思想。

下面是我们将要遵循的方法的分步说明 -

如果其中一个（即被除数或除数）为 0，我们将返回 0。
现在，我们将使用异或函数 (XOR) 检查符号，以将符号存储在变量中。
如果除数为 1，则直接返回被除数。
现在，声明一个变量并使用 exp 函数和 log 函数。
Log 和 exp 是 C++ 中的内置函数。 Log 函数返回输入数字的自然对数值，exp 返回等于 e 加上输入值的值。

示例

下面是上述方法的 C++ 实现 -

#include <iostream>
#include <bits/stdc++.h>
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<<ans<<endl;
   
   return 0;
}

登录后复制