29. Divide Two Integers

29. Divide Two Integers

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

If it is overflow, return MAX_INT.

思路： 1、基本思想是不断地减掉除数，直到为0为止。但是这样会太慢。 2、我们可以使用2分法来加速这个过程。不断对除数*2，直到它比被除数还大为止。加倍的同时，也记录下cnt，将被除数减掉加倍后的值，并且结果+cnt。因为是2倍地加大，所以速度会很快，指数级的速度。 3、另外要注意的是：最小值的越界问题。对最小的正数取abs，得到的还是它。。。 因为最小的正数的绝对值大于最大的正数（INT）。所以，使用Long来接住这个集合就可以了。 4、返回值的时候，判断是不是越界，越界返回最大值。

class Solution { public int divide(int dividend, int divisor) { long a = Math.abs((long)dividend); long b = Math.abs((long)divisor); long ret = 0; while (a >= b) { for (long tmp = b, cnt = 1; a >= tmp; tmp <<= 1, cnt <<= 1) { ret += cnt; a -= tmp; } } ret = (((dividend ^ divisor) >> 31) & 1) == 1 ? -ret: ret; if (ret > Integer.MAX_VALUE || ret < Integer.MIN_VALUE) { return Integer.MAX_VALUE; } return (int)ret; }}

/** * @param {number} dividend * @param {number} divisor * @return {number} */var divide = function(dividend, divisor) { let sign = true if (dividend < 0) { dividend = 0 - dividend sign = !sign } if (divisor < 0) { divisor = 0 - divisor sign = !sign } if (divisor > dividend) { return 0 } let [res, mul_divisor] = [1, divisor] while (dividend > mul_divisor + mul_divisor) { res += res mul_divisor += mul_divisor } res = res + divide(dividend - mul_divisor, divisor) if (!sign) { res = 0 - res } res = res >= 2147483648 ? 2147483647 : res res = res <= -2147483648 ? -2147483648 : res return res};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。