Lintcode414 Divide Two Integers solution 题解 96
发布在lintcode 题解2018年4月24日view:311
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

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

If it is overflow, return 2147483647

将两个整数相除,要求不使用乘法、除法和 mod 运算符。

如果溢出,返回 2147483647 。

【题目链接】

www.lintcode.com/en/problem/divide-two-integers/

【题目解析】

这道题要求不用乘,除和模操作完成除法操作。

基本思想是不断地减掉除数,直到为0为止。但是这样会太慢。

我们可以使用2分法来加速这个过程。不断对除数 * 2,直到它恰好比被除数小(即再乘2就会比被除数大)为止。加倍的同时,也记录下cnt,将被除数减掉加倍后的值,并且结果+cnt。因为是2倍地加大,所以速度会很快,指数级的速度。

但是因为不能用乘除操作,因此只能用位运算的方法,即左移1位 = * 2。

首先讨论一些边界情况:

如果除数为0,则被除数为正时,结果为正无穷,否则为负无穷

如果被除数为0,则返回0

如果被除数为正无穷除数为1或者被除数为负无穷除数为-1,则返回正无穷

如果被除数为正无穷除数为-1或者被除数为负无穷除数为1,则返回负无穷

记录一下结果的符号(即除数和被除数同号为+,异号为负),然后对除数和被除数取绝对值。注意:因为int最大2147483647,最小-2147483648,最小值直接abs后会溢出,所以要先讲被除数与除数转换为long之后再取绝对值,以防出现溢出的情况。

每次将b左移一定的位数,比如i位,使得b恰好小于a(即b< a),此时相当于b 2^i,然后再对剩下的数(即a-b2^i)做刚才的操作,直到剩下的数小于b为止。看b总共乘以了多少power of 2,将其加和即可。

【参考答案】

www.jiuzhang.com/solutions/divide-two-integers/

评论
发表评论
暂无评论
WRITTEN BY
Jennyckx
做个有趣的人(>人<;)
TA的新浪微博
PUBLISHED IN

我的收藏