在這個(gè)問題中，我們只需要將兩個(gè)整數(shù)相除，而不需要使用乘法、除法和取模運(yùn)算符。盡管我們可以使用加法、乘法或位操作。
問題陳述指出我們將得到兩個(gè)整數(shù) x 和 y。在不使用乘法、除法或取模運(yùn)算符的情況下，我們需要確定 x 除以 y 后的商。
示例
輸入：x=15，y=5
輸出：3
輸入：x=10，y=4
輸出：2
輸入：x=-20，y=3
輸出：-6
方法
方法1（使用簡(jiǎn)單的數(shù)學(xué)）
在這種方法中，我們將使用一個(gè)簡(jiǎn)單的數(shù)學(xué)算法。下面是我們要遵循的步驟的分步說(shuō)明 –
我們將從被除數(shù)（即 x）中不斷減去除數(shù)（即 y），直到 x 大于或等于 y。
當(dāng) y 大于 x 時(shí)，即除數(shù)大于被除數(shù)，被除數(shù)變?yōu)橛鄶?shù)，減法次數(shù)變?yōu)樯獭?/p>
將減法執(zhí)行的次數(shù)存儲(chǔ)在變量中并返回它，這是我們想要的輸出。
示例
下面是上述算法的 C++ 實(shí)現(xiàn) &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;
}
登錄后復(fù)制
輸出
-10737
登錄后復(fù)制
時(shí)間復(fù)雜度：O(a/b)
空間復(fù)雜度：O(1)
方法 2（使用位操作）
由于任何數(shù)字都可以用 0 或 1 的形式表示，因此可以使用移位運(yùn)算符以二進(jìn)制形式表示商。
使用 for 循環(huán)迭代除數(shù)從 31 到 1 的位位置。
找到除數(shù)即 b<<i 小于被除數(shù)成立的第一個(gè)位，然后繼續(xù)更新在變量 temp 中成立的第 i 個(gè)位位置。
驗(yàn)證下一個(gè)位置時(shí)，將結(jié)果添加到 temp 變量中，以確保 temp+(b<<i) 小于或等于被除數(shù)，即 a。
每次通過計(jì)算商來(lái)更新商OR 1<<i.
更新相應(yīng)符號(hào)后返回商。
示例
下面是上述方法的 C++ 實(shí)現(xiàn) –
#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;
}
登錄后復(fù)制
輸出
9 -3
登錄后復(fù)制
時(shí)間復(fù)雜度：O(log(a))
空間復(fù)雜度：O(1)，因?yàn)樗皇褂妙~外的空間。
方法 3（使用對(duì)數(shù)函數(shù)）
在這種方法中，我們將使用一個(gè)簡(jiǎn)單的對(duì)數(shù)函數(shù)來(lái)計(jì)算商。
眾所周知，
$$\mathrm{In(\frac{a}{b})\:=\:In(a)\:-\:In(b)}$$
可以進(jìn)一步修改為
$$\mathrm{\frac{a}{b}\:=\:e^{(In(a)\:-\:In(b))}}$$
因此，這是使用這種有效方法解決給定問題的基本思想。
下面是我們將要遵循的方法的分步說(shuō)明 –
如果其中一個(gè)（即被除數(shù)或除數(shù)）為 0，我們將返回 0。
現(xiàn)在，我們將使用異或函數(shù) (XOR) 檢查符號(hào)，以將符號(hào)存儲(chǔ)在變量中。
如果除數(shù)為 1，則直接返回被除數(shù)。
現(xiàn)在，聲明一個(gè)變量并使用 exp 函數(shù)和 log 函數(shù)。
Log 和 exp 是 C++ 中的內(nèi)置函數(shù)。 Log 函數(shù)返回輸入數(shù)字的自然對(duì)數(shù)值，exp 返回等于 e 加上輸入值的值。
示例
下面是上述方法的 C++ 實(shí)現(xiàn) –
#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;
}
登錄后復(fù)制
輸出
-5
登錄后復(fù)制
時(shí)間復(fù)雜度：O(1)，，因?yàn)閳?zhí)行該操作需要恒定的時(shí)間。
空間復(fù)雜度：O(1)，因?yàn)樗皇褂妙~外的空間。
結(jié)論
在本文中，我們學(xué)習(xí)在不使用乘法、除法或取模運(yùn)算符的情況下將兩個(gè)整數(shù)相除。我們學(xué)會(huì)了用不同的方法以不同的效率解決問題。他們使用簡(jiǎn)單的數(shù)學(xué)、位操作和對(duì)數(shù)函數(shù)。其中，使用對(duì)數(shù)函數(shù)是最有效的方法，因?yàn)樗臅r(shí)間復(fù)雜度為 O(1)，是所有方法中最小的。
我希望這篇文章可以幫助您解決有關(guān)該主題的所有概念。
以上就是不使用乘法、除法和取模運(yùn)算符來(lái)進(jìn)行兩個(gè)整數(shù)的除法的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注www.xfxf.net其它相關(guān)文章！
