首页 > 代码库 > 【leetcode刷题笔记】Divide Two Integers
【leetcode刷题笔记】Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
题解:要求不用乘除和取模运算实现两个数的除法。
那么用加减法是很自然的选择。不过如果一次只从被除数中剪掉一个除数会TLE。所以我们借助移位运算,依次从被除数中减去1个除数,2个除数,4个除数......当减不动的时候,再依次从被除数中减去......4个除数,2个除数,1个除数。
例如50除以5的计算过程如下:
dividend | exp | temp | answer |
50 | 5 | 1 | 0 |
45 | 10 | 2 | 1 |
35 | 20 | 4 | 3 |
15 | 40 | 8 | 7 |
15 | 20 | 4 | 7 |
15 | 10 | 2 | 7 |
5 | 5 | 1 | 9 |
0 | 1 | 0 | 10 |
要注意的一点是在计算过程中要把除数和被除数转换成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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。