不使用乘法、除法和取模運算子來進行兩個整數的除法

在這個問題中，我們只需要將兩個整數相除，而不需要使用乘法、除法和取模運算子。儘管我們可以使用加法、乘法或位元操作。

問題陳述指出我們將得到兩個整數 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

• #更新對應符號後返回商數。

範例

下面是上述方法的 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;
}

輸出

-5

時間複雜度：O(1)，，因為執行該操作需要恆定的時間。

空間複雜度：O(1)，因為它不使用額外的空間。

結論

在本文中，我們學習在不使用乘法、除法或取模運算子的情況下將兩個整數相除。我們學會了用不同的方法以不同的效率解決問題。他們使用簡單的數學、位元操作和對數函數。其中，使用對數函數是最有效的方法，因為它的時間複雜度為 O(1)，是所有方法中最小的。

我希望這篇文章可以幫助您解決有關該主題的所有概念。

以上是不使用乘法、除法和取模運算子來進行兩個整數的除法的詳細內容。更多資訊請關注PHP中文網其他相關文章！