首页 > 代码库 > LeetCode: Divide Two Integers 解题报告
LeetCode: Divide Two Integers 解题报告
Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
SOLUTION 1
1. 基本思想是不断地减掉除数，直到为0为止。但是这样会太慢。
2. 我们可以使用2分法来加速这个过程。不断对除数*2，直到它比被除数还大为止。加倍的同时，也记录下cnt，将被除数减掉加倍后的值，并且结果+cnt。
因为是2倍地加大，所以速度会很快，指数级的速度。
3. 另外要注意的是：最小值的越界问题。对最小的正数取abs，得到的还是它。。。 因为最小的正数的绝对值大于最大的正数（INT）
所以，我们使用Long来接住这个集合就可以了。
1 public class Solution { 2 public int divide(int dividend, int divisor) { 3 long a = Math.abs((long)dividend); 4 5 // ref : http://blog.csdn.net/kenden23/article/details/16986763 6 // Note: 在这里必须先取long再abs，否则int的最小值abs后也是原值 7 long b = Math.abs((long)divisor); 8 9 int ret = 0;10 // 这里必须是= 因为相等时也可以减11 while (a >= b) {12 // 判断条件是 >=13 for (long deduce = b, cnt = 1; a >= deduce; deduce <<= 1, cnt <<= 1) {14 a -= deduce;15 ret += cnt;16 }17 }18 19 // 获取符号位。根据除数跟被除数的关系来定20 return (dividend > 0) ^ (divisor > 0) ? -ret: ret;21 }22 }
GitHub Code:
divide.java
Ref: http://blog.csdn.net/fightforyourdream/article/details/16899675
LeetCode: Divide Two Integers 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。