首页 > 代码库 > 【leetcode刷题笔记】Divide Two Integers

【leetcode刷题笔记】Divide Two Integers

2024-07-13 19:17:49   220人阅读

Divide two integers without using multiplication, division and mod operator.

 

题解：要求不用乘除和取模运算实现两个数的除法。

那么用加减法是很自然的选择。不过如果一次只从被除数中剪掉一个除数会TLE。所以我们借助移位运算，依次从被除数中减去1个除数，2个除数，4个除数......当减不动的时候，再依次从被除数中减去......4个除数，2个除数，1个除数。

例如50除以5的计算过程如下：

dividend　　　　exp　　　　temp　　　　answer　　　　
50510
451021
352043
154087
152047
151027
5519
01010

要注意的一点是在计算过程中要把除数和被除数转换成long型，WA一次，输入是[-2147483648,1]，在java中最大正整数是2147483647，最小的负整数是-2147483648.所以如果给上述的例子，把被除数去绝对值的时候就去不了，所以要把被除数转换成long型再去绝对值。

代码如下：

 1 public class Solution { 2     public int divide(int dividend, int divisor) { 3         if(dividend == 0) 4             return 0; 5  6         boolean isNeg = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0); 7         long answer = 0; 8         long temp = 1; 9         long dividend_long = Math.abs((long)dividend);10         long divisor_long = Math.abs((long)divisor);11         long exp = divisor_long;12         13         while(dividend_long - exp >= 0){14             answer += temp;15             temp = temp << 1;16             dividend_long -= exp;17             exp = exp << 1;18         }19         temp = temp >> 1;20         exp = exp >> 1;21         while(temp >= 1 && dividend_long > 0){22             if(dividend_long - exp >= 0){23                 answer += temp;24                 dividend_long -= exp;25             }26             temp = temp >> 1;27             exp = exp >> 1;28         }29         30         if(isNeg)31             answer = -answer;32         return (int)answer;33     }34 }


联系
我们