数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学不用乘法、除法和取模运算符来除两个整数
在这个问题中，我们只需要不用乘法、除法和取模运算符来除两个整数。虽然我们可以使用加法、乘法或位操作。
问题陈述指出，我们将得到两个整数 x 和 y。不用乘法、除法或取模运算符，我们需要确定 x 除以 y 后的商。
示例
输入：x=15 , y=5
输出: 3
输入：x=10 , y=4
输出: 2
输入：x=-20 , y=3
输出: -6
方法
方法一（使用简单的数学方法）
在这种方法中，我们将使用一个简单的数学算法。以下是我们将遵循的步骤的逐步说明：
我们将不断从被除数 x 中减去除数 y，直到 x 大于或等于 y。
当 y 大于 x（即除数大于被除数）时，被除数变成余数，减法的次数变成商。
将减法执行的次数存储在一个变量中并返回它，这就是我们想要的输出。
示例
以下是上述算法的 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
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)
方法二（使用位操作）
由于任何数字都可以表示为 0 或 1 的形式，因此可以使用移位运算符以二进制形式表示商。
使用 for 循环迭代除数的从 31 到 1 的位位置。
找到除数 (b<
在验证下一个位置时，将结果添加到 temp 变量中，以确保 temp+(b<
每次通过计算商 OR 1<
更新相应的符号后返回商。
示例
以下是上述方法的 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)，因为它不使用额外的空间。
方法三（使用对数函数）
在这种方法中，我们将使用一个简单的对数函数来计算商。
众所周知，
$$\mathrm{In(\frac{a}{b})\:=\:In(a)\:-\:In(b)}$$
这可以进一步修改为
$$\mathrm{\frac{a}{b}\:=\:e^{(In(a)\:-\:In(b))}}$$
所以这是使用这种有效方法解决给定问题的基本思想。
以下是我们将遵循的方法的逐步说明：
如果被除数或除数为 0，我们将返回 0。
现在，我们将使用异或函数 (XOR) 检查符号并将符号存储在一个变量中。
如果除数为 1，则只需返回被除数。
现在，声明一个变量，并使用 **exp** 函数和 **log** 函数将 $\mathrm{e^{(In(a)\:-\:In(b))}}$ 的值存储在其中。
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;
}
输出
-5
时间复杂度：O(1)，因为执行操作需要常数时间。
空间复杂度：O(1)，因为它不使用额外的空间。
结论
在本文中，我们学习了不用乘法、除法或取模运算符来除两个整数。我们学习了用不同方法解决问题，效率也不同。它们是使用简单的数学方法、使用位操作和使用对数函数。在所有这些方法中，使用对数函数是最有效的方法，因为它具有 O(1) 的时间复杂度，这是所有方法中最低的。
我希望这篇文章能帮助你解决所有关于这个主题的概念。
5K+ 次浏览
