不使用乘法、除法和mod运算符对两个整数进行除法-yiteyi-C++库

给定一个两个整数，比如a和b。在不使用乘法、除法和mod运算符的情况下，将a除以b后求出商。

null

例子：

Input : a = 10, b = 3Output : 3Input : a = 43, b = -8Output :  -5

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法： 继续从股息中减去除数，直到股息小于除数。被除数变成余数，减法的次数变成商。以下是上述方法的实施情况：

C++

                         // C++ implementation to Divide two                       
                         // integers without using multiplication,                       
                         // division and mod operator                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to divide a by b and                       
                         // return floor value it                       
                         int                                     divide(                                     int                                     dividend,                                     int                                     divisor) {                       
           
                                                 // Calculate sign of divisor i.e.,                       
                                                 // sign will be negative only if                       
                                                 // either one of them is negative                       
                                                 // otherwise it will be positive                       
                                                 int                                     sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;                       
           
                                                 // Update both divisor and                       
                                                 // dividend positive                       
                                                 dividend =                                     abs                                     (dividend);                       
                                                 divisor =                                     abs                                     (divisor);                       
           
                                                 // Initialize the quotient                       
                                                 int                                     quotient = 0;                       
                                                 while                                     (dividend >= divisor) {                       
                                                 dividend -= divisor;                       
                                                 ++quotient;                       
                                                 }                       
                                   
                                                 // Return the value of quotient with the appropriate sign.                       
                                                 return                                     quotient * sign;                       
                         }                       
           
                         // Driver code                       
                         int                                     main() {                       
                                                 int                                     a = 10, b = 3;                       
                                                 cout << divide(a, b) <<                                     ""                                     ;                       
           
                                                 a = 43, b = -8;                       
                                                 cout << divide(a, b);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         /*Java implementation to Divide two                       
                         integers without using multiplication,                       
                         division and mod operator*/                       
           
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                   
                                                 // Function to divide a by b and                       
                                                 // return floor value it                       
                                                 static                                     int                                     divide(                                     int                                     dividend,                                     int                                     divisor)                       
                                                 {                       
                                   
                                                 // Calculate sign of divisor i.e.,                       
                                                 // sign will be negative only if                       
                                                 // either one of them is negative                       
                                                 // otherwise it will be positive                       
                                                 int                                     sign = ((dividend <                                     0                                     ) ^                       
                                                 (divisor <                                     0                                     )) ? -                                     1                                     :                                     1                                     ;                       
                                   
                                                 // Update both divisor and                       
                                                 // dividend positive                       
                                                 dividend = Math.abs(dividend);                       
                                                 divisor = Math.abs(divisor);                       
                                   
                                                 // Initialize the quotient                       
                                                 int                                     quotient =                                     0                                     ;                       
                                   
                                                 while                                     (dividend >= divisor)                       
                                                 {                       
                                                 dividend -= divisor;                       
                                                 ++quotient;                       
                                                 }                       
                                                 //if the sign value computed earlier is -1 then negate the value of quotient                       
                                                 if                                     (sign==-                                     1                                     ) quotient=-quotient;                       
                                   
                                                 return                                     quotient;                       
                                                 }                       
                                   
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     a =                                     10                                     ;                       
                                                 int                                     b =                                     3                                     ;                       
                                   
                                                 System.out.println(divide(a, b));                       
                                   
                                                 a =                                     43                                     ;                       
                                                 b = -                                     8                                     ;                       
                                   
                                                 System.out.println(divide(a, b));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by upendra singh bartwal.                       

Python3

                         # Python 3 implementation to Divide two                       
                         # integers without using multiplication,                       
                         # division and mod operator                       
           
                         # Function to divide a by b and                       
                         # return floor value it                       
                         def                                     divide(dividend, divisor):                       
           
                                                 # Calculate sign of divisor i.e.,                       
                                                 # sign will be negative only if                       
                                                 # either one of them is negative                       
                                                 # otherwise it will be positive                       
                                                 sign                                     =                                     -                                     1                                     if                                     ((dividend <                                     0                                     ) ^  (divisor <                                     0                                     ))                                     else                                     1                       
                                   
                                                 # Update both divisor and                       
                                                 # dividend positive                       
                                                 dividend                                     =                                     abs                                     (dividend)                       
                                                 divisor                                     =                                     abs                                     (divisor)                       
                                   
                                                 # Initialize the quotient                       
                                                 quotient                                     =                                     0                       
                                                 while                                     (dividend >                                     =                                     divisor):                       
                                                 dividend                                     -                                     =                                     divisor                       
                                                 quotient                                     +                                     =                                     1                       
                                   
                                                 #if the sign value computed earlier is -1 then negate the value of quotient                       
                                   
                                                 if                                     sign                                     =                                     =                                     -                                     1                                     :                       
                                                 quotient                                     =                                     -                                     quotient                       
                                   
                                                 return                                     quotient                       
           
           
                         # Driver code                       
                         a                                     =                                     10                       
                         b                                     =                                     3                       
                         print                                     (divide(a, b))                       
                         a                                     =                                     43                       
                         b                                     =                                     -                                     8                       
                         print                                     (divide(a, b))                       
           
                         # This code is contributed by                       
                         # Smitha Dinesh Semwal                       

C#

                         // C# implementation to Divide two without                       
                         // using multiplication, division and mod                       
                         // operator                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Function to divide a by b and                       
                                                 // return floor value it                       
                                                 static                                     int                                     divide(                                     int                                     dividend,                                     int                                     divisor)                       
                                                 {                       
                                   
                                                 // Calculate sign of divisor i.e.,                       
                                                 // sign will be negative only if                       
                                                 // either one of them is negative                       
                                                 // otherwise it will be positive                       
                                                 int                                     sign = ((dividend < 0) ^                       
                                                 (divisor < 0)) ? -1 : 1;                       
                                   
                                                 // Update both divisor and                       
                                                 // dividend positive                       
                                                 dividend = Math.Abs(dividend);                       
                                                 divisor = Math.Abs(divisor);                       
                                   
                                                 // Initialize the quotient                       
                                                 int                                     quotient = 0;                       
                                   
                                                 while                                     (dividend >= divisor)                       
                                                 {                       
                                                 dividend -= divisor;                       
                                                 ++quotient;                       
                                                 }                       
                                   
                                                 //if the sign value computed earlier is -1 then negate the value of quotient                       
                                                 if                                     (sign==-1) quotient=-quotient;                       
                                                 return                                     quotient;                       
                                                 }                       
                                   
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                   
                                                 int                                     a = 10;                       
                                                 int                                     b = 3;                       
                                                 Console.WriteLine(divide(a, b));                       
                                   
                                                 a = 43;                       
                                                 b = -8;                       
                                                 Console.WriteLine(divide(a, b));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP implementation to Divide two                       
                         // integers without using multiplication,                       
                         // division and mod operator                       
           
                         // Function to divide a by b and                       
                         // return floor value it                       
                         function                                     divide(                                     $dividend                                     ,                                     $divisor                                     ) {                       
           
                                                 // Calculate sign of divisor i.e.,                       
                                                 // sign will be negative only if                       
                                                 // either one of them is negative                       
                                                 // otherwise it will be positive                       
                                                 $sign                                     = ((                                     $dividend                                     < 0) ^                       
                                                 (                                     $divisor                                     < 0)) ? -1 : 1;                       
                                   
                                                 // Update both divisor and                       
                                                 // dividend positive                       
                                                 $dividend                                     =                                     abs                                     (                                     $dividend                                     );                       
                                                 $divisor                                     =                                     abs                                     (                                     $divisor                                     );                       
                                   
                                                 // Initialize the quotient                       
                                                 $quotient                                     = 0;                       
                                                 while                                     (                                     $dividend                                     >=                                     $divisor                                     )                       
                                                 {                       
                                                 $dividend                                     -=                                     $divisor                                     ;                       
                                                 ++                                     $quotient                                     ;                       
                                                 }                       
                                                 //if the sign value computed earlier is -1 then negate the value of quotient                       
                                                 if                                     (                                     $sign                                     ==-1)                                     $quotient                                     =-                                     $quotient                                     ;                       
                                                 return                                     $quotient                                     ;                       
                         }                       
           
                         // Driver code                       
                         $a                                     = 10;                       
                         $b                                     = 3;                       
                         echo                                     divide(                                     $a                                     ,                                     $b                                     ).                                     ""                                     ;                       
           
                         $a                                     = 43;                       
                         $b                                     = -8;                       
                         echo                                     divide(                                     $a                                     ,                                     $b                                     );                       
           
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript implementation to Divide two                       
                         // integers without using multiplication,                       
                         // division and mod operator                       
           
                         // Function to divide a by b and                       
                         // return floor value it                       
                         function                                     divide(dividend, divisor) {                       
           
                         // Calculate sign of divisor i.e.,                       
                         // sign will be negative only if                       
                         // either one of them is negative                       
                         // otherwise it will be positive                       
                         let sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;                       
           
                         // Update both divisor and                       
                         // dividend positive                       
                         dividend = Math.abs(dividend);                       
                         divisor = Math.abs(divisor);                       
           
                         // Initialize the quotient                       
                         let quotient = 0;                       
                         while                                     (dividend >= divisor) {                       
                                                 dividend -= divisor;                       
                                                 ++quotient;                       
                         }                       
                         //if the sign value computed earlier is -1 then negate the value of quotient                       
                         if                                     (sign==-1) quotient=-quotient;                       
                         return                                     quotient;                       
                         }                       
           
                         // Driver code                       
                         let a = 10, b = 3;                       
                         document.write(divide(a, b) +                                     "<br>"                                     );                       
           
                         a = 43, b = -8;                       
                         document.write(divide(a, b));                       
           
                         // This code is contributed by Surbhi Tyagi.                       
           
                         </script>                       

输出

3-5

时间复杂性： O（a） 辅助空间： O（1） 有效方法： 使用位操作来找到商。除数和除数可以写成

股息=商*除数+余数

由于每个数字都可以用基数2（0或1）表示，所以使用移位运算符以二进制形式表示商，如下所示：

确定除数中的最高有效位。这可以通过迭代位位置来轻松计算我从31岁到1岁。
找到第一位 $divisor << i$ 少于股息，并不断更新 ^th 正确的位位置。
将结果添加到 临时雇员 用于检查下一个位置的变量，以便（温度+（除数< 不到股息 .
用相应的符号更新后返回商的最终答案。

以下是上述方法的实施情况：

C++

                         // C++ implementation to Divide two                       
                         // integers without using multiplication,                       
                         // division and mod operator                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to divide a by b and                       
                         // return floor value it                       
                         int                                     divide(                                     long                                     long                                     dividend,                                     long                                     long                                     divisor) {                       
           
                                                 // Calculate sign of divisor i.e.,                       
                                                 // sign will be negative only iff                       
                                                 // either one of them is negative                       
                                                 // otherwise it will be positive                       
                                                 int                                     sign = ((dividend < 0) ^                       
                                                 (divisor < 0)) ? -1 : 1;                       
           
                                                 // remove sign of operands                       
                                                 dividend =                                     abs                                     (dividend);                       
                                                 divisor =                                     abs                                     (divisor);                       
           
                                                 // Initialize the quotient                       
                                                 long                                     long                                     quotient = 0, temp = 0;                       
           
                                                 // test down from the highest bit and                       
                                                 // accumulate the tentative value for                       
                                                 // valid bit                       
                                                 for                                     (                                     int                                     i = 31; i >= 0; --i) {                       
           
                                                 if                                     (temp + (divisor << i) <= dividend) {                       
                                                 temp += divisor << i;                       
                                                 quotient |= 1LL << i;                       
                                                 }                       
                                                 }                       
                                                 //if the sign value computed earlier is -1 then negate the value of quotient                       
                                                 if                                     (sign==-1) quotient=-quotient;                       
                                   
                                                 return                                     quotient;                       
                         }                       
           
                         // Driver code                       
                         int                                     main() {                       
                                                 int                                     a = 10, b = 3;                       
                                                 cout << divide(a, b) <<                                     ""                                     ;                       
           
                                                 a = 43, b = -8;                       
                                                 cout << divide(a, b);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation to Divide                       
                         // two integers without using                       
                         // multiplication, division                       
                         // and mod operator                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         // Function to divide a by b                       
                         // and return floor value it                       
                         class                                     GFG                       
                         {                       
                         public                                     static                                     long                                     divide(                                     long                                     dividend,                       
                                                 long                                     divisor)                       
                         {                       
           
                         // Calculate sign of divisor                       
                         // i.e., sign will be negative                       
                         // only iff either one of them                       
                         // is negative otherwise it                       
                         // will be positive                       
                         long                                     sign = ((dividend <                                     0                                     ) ^                       
                                                 (divisor <                                     0                                     )) ? -                                     1                                     :                                     1                                     ;                       
           
                         // remove sign of operands                       
                         dividend = Math.abs(dividend);                       
                         divisor = Math.abs(divisor);                       
           
                         // Initialize the quotient                       
                         long                                     quotient =                                     0                                     , temp =                                     0                                     ;                       
           
                         // test down from the highest                       
                         // bit and accumulate the                       
                         // tentative value for                       
                         // valid bit                       
                         // 1<<31 behaves incorrectly and gives Integer                       
                         // Min Value which should not be the case, instead                       
                                                 // 1L<<31 works correctly.                       
                         for                                     (                                     int                                     i =                                     31                                     ; i >=                                     0                                     ; --i)                       
                         {                       
           
                                                 if                                     (temp + (divisor << i) <= dividend)                       
                                                 {                       
                                                 temp += divisor << i;                       
                                                 quotient |= 1L << i;                       
                                                 }                       
                         }                       
           
                         //if the sign value computed earlier is -1 then negate the value of quotient                       
                         if                                     (sign==-                                     1                                     )                       
                                                 quotient=-quotient;                       
                         return                                     quotient;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String args[])                       
                         {                       
                         int                                     a =                                     10                                     , b =                                     3                                     ;                       
                         System.out.println(divide(a, b));                       
           
                         int                                     a1 =                                     43                                     , b1 = -                                     8                                     ;                       
                         System.out.println(divide(a1, b1));                       
           
           
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by Akanksha Rai(Abby_akku)                       

Python3

                         # Python3 implementation to                       
                         # Divide two integers                       
                         # without using multiplication,                       
                         # division and mod operator                       
           
                         # Function to divide a by                       
                         # b and return floor value it                       
                         def                                     divide(dividend, divisor):                       
                                   
                                                 # Calculate sign of divisor                       
                                                 # i.e., sign will be negative                       
                                                 # either one of them is negative                       
                                                 # only iff otherwise it will be                       
                                                 # positive                       
                                   
                                                 sign                                     =                                     (                                     -                                     1                                     if                                     ((dividend <                                     0                                     ) ^                       
                                                 (divisor <                                     0                                     ))                                     else                                     1                                     );                       
                                   
                                                 # remove sign of operands                       
                                                 dividend                                     =                                     abs                                     (dividend);                       
                                                 divisor                                     =                                     abs                                     (divisor);                       
                                   
                                                 # Initialize                       
                                                 # the quotient                       
                                                 quotient                                     =                                     0                                     ;                       
                                                 temp                                     =                                     0                                     ;                       
                                   
                                                 # test down from the highest                       
                                                 # bit and accumulate the                       
                                                 # tentative value for valid bit                       
                                                 for                                     i                                     in                                     range                                     (                                     31                                     ,                                     -                                     1                                     ,                                     -                                     1                                     ):                       
                                                 if                                     (temp                                     +                                     (divisor << i) <                                     =                                     dividend):                       
                                                 temp                                     +                                     =                                     divisor << i;                       
                                                 quotient |                                     =                                     1                                     << i;                       
                                                 #if the sign value computed earlier is -1 then negate the value of quotient                       
                                                 if                                     sign                                     =                                     =                                     -                                     1                                     :                       
                                                 quotient                                     =                                     -                                     quotient;                       
                                                 return                                     quotient;                       
           
                         # Driver code                       
                         a                                     =                                     10                                     ;                       
                         b                                     =                                     3                                     ;                       
                         print                                     (divide(a, b));                       
           
                         a                                     =                                     43                                     ;                       
                         b                                     =                                     -                                     8                                     ;                       
                         print                                     (divide(a, b));                       
           
                         # This code is contributed by mits                       

C#

                         // C# implementation to Divide                       
                         // two integers without using                       
                         // multiplication, division                       
                         // and mod operator                       
                         using                                     System;                       
           
                         // Function to divide a by b                       
                         // and return floor value it                       
                         class                                     GFG                       
                         {                       
                         public                                     static                                     long                                     divide(                                     long                                     dividend,                       
                                                 long                                     divisor)                       
                         {                       
           
                         // Calculate sign of divisor                       
                         // i.e., sign will be negative                       
                         // only iff either one of them                       
                         // is negative otherwise it                       
                         // will be positive                       
                         long                                     sign = ((dividend < 0) ^                       
                                                 (divisor < 0)) ? -1 : 1;                       
           
                         // remove sign of operands                       
                         dividend = Math.Abs(dividend);                       
                         divisor = Math.Abs(divisor);                       
           
                         // Initialize the quotient                       
                         long                                     quotient = 0, temp = 0;                       
           
                         // test down from the highest                       
                         // bit and accumulate the                       
                         // tentative value for                       
                         // valid bit                       
                         for                                     (                                     int                                     i = 31; i >= 0; --i)                       
                         {                       
           
                                                 if                                     (temp + (divisor << i) <= dividend)                       
                                                 {                       
                                                 temp += divisor << i;                       
                                                 quotient |= 1LL << i;                       
                                                 }                       
                         }                       
                         //if the sign value computed earlier is -1 then negate the value of quotient                       
                                                 if                                     (sign==-1)                       
                                                 quotient=-quotient;                       
                         return                                     quotient;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                         int                                     a = 10, b = 3;                       
                         Console.WriteLine(divide(a, b));                       
           
                         int                                     a1 = 43, b1 = -8;                       
                         Console.WriteLine(divide(a1, b1));                       
           
                         }                       
                         }                       
           
                         // This code is contributed by mits                       

PHP

                         <?php                       
                         // PHP implementation to                       
                         // Divide two integers                       
                         // without using multiplication,                       
                         // division and mod operator                       
           
                         // Function to divide a by                       
                         // b and return floor value it                       
                         function                                     divide(                                     $dividend                                     ,                       
                                                 $divisor                                     )                       
                         {                       
           
                         // Calculate sign of divisor                       
                         // i.e., sign will be negative                       
                         // either one of them is negative                       
                         // only iff otherwise it will be                       
                         // positive                       
                         $sign                                     = ((                                     $dividend                                     < 0) ^                       
                                                 (                                     $divisor                                     < 0)) ? -1 : 1;                       
           
                         // remove sign of operands                       
                         $dividend                                     =                                     abs                                     (                                     $dividend                                     );                       
                         $divisor                                     =                                     abs                                     (                                     $divisor                                     );                       
           
                         // Initialize                       
                         // the quotient                       
                         $quotient                                     = 0;                       
                         $temp                                     = 0;                       
           
                         // test down from the highest                       
                         // bit and accumulate the                       
                         // tentative value for valid bit                       
                         for                                     (                                     $i                                     = 31;                                     $i                                     >= 0; --                                     $i                                     )                       
                         {                       
           
                                                 if                                     (                                     $temp                                     + (                                     $divisor                                     <<                                     $i                                     ) <=                                     $dividend                                     )                       
                                                 {                       
                                                 $temp                                     +=                                     $divisor                                     <<                                     $i                                     ;                       
                                                 $quotient                                     |= (double)(1) <<                                     $i                                     ;                       
                                                 }                       
                         }                       
                         //if the sign value computed earlier is -1 then negate the value of quotient                       
                         if                                     (                                     $sign                                     ==-1)                       
                                                 $quotient                                     =-                                     $quotient                                     ;                       
                         return                                     $quotient                                     ;                       
                         }                       
           
                         // Driver code                       
                         $a                                     = 10;                       
                         $b                                     = 3;                       
                         echo                                     divide(                                     $a                                     ,                                     $b                                     ).                                     ""                                     ;                       
           
                         $a                                     = 43;                       
                         $b                                     = -8;                       
                         echo                                     divide(                                     $a                                     ,                                     $b                                     );                       
           
                         // This code is contributed by mits                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript implementation to Divide                       
                         // two integers without using                       
                         // multiplication, division                       
                         // and mod operator                       
           
                         // Function to divide a by b                       
                         // and return floor value it                       
           
                         function                                     divide(dividend, divisor)                       
                         {                       
           
                         // Calculate sign of divisor                       
                         // i.e., sign will be negative                       
                         // only iff either one of them                       
                         // is negative otherwise it                       
                         // will be positive                       
                         var                                     sign = ((dividend < 0)?1:0 ^                       
                                                 (divisor < 0)?1:0) ? -1 : 1;                       
           
                         // remove sign of operands                       
                         dividend = Math.abs(dividend);                       
                         divisor = Math.abs(divisor);                       
           
                         // Initialize the quotient                       
                         var                                     quotient = 0, temp = 0;                       
           
                         // test down from the highest                       
                         // bit and accumulate the                       
                         // tentative value for                       
                         // valid bit                       
                         while                                     (dividend >= divisor) {                       
                                                 dividend -= divisor;                       
                                                 ++quotient;                       
                         }                       
                         //if the sign value computed earlier is -1 then negate the value of quotient                       
                         if                                     (sign==-1) quotient=-quotient;                       
                         return                                     quotient;                       
                         }                       
           
                         // Driver code                       
           
                         var                                     a = 10, b = 3;                       
                         document.write(divide(a, b) +                                     "<br>"                                     );                       
           
                         var                                     a1 = 43, b1 = -8;                       
                         document.write(divide(a1, b1) +                                     "<br>"                                     );                       
           
           
           
                         </script>                       

输出

3-5

时间复杂性： O（日志（a）） 辅助空间： O（1）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章