1 题目
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
Math Binary Search2 思路
以前没见过,没思路。于是看别人的实现:https://leetcode.com/discuss/11358/simple-o-log-n-2-c-solution
使用的是移位操作:
例如:19 / 3
3 <<=1 ->6, 6<19 继续移位
6 <<=1 ->12, 12<19 继续移位
12 <<=1 ->24, 24 > 19不移位了
结果+ 4
19 - 12 = 7重复移位
3 <<=1 ->6, 6<7 继续移位
6 <<=1 ->12 , 12 > 6 ,不移位了
结果+ 2
7-6=1
再比较
3 <<=1 ->6 ,6>1,不移位了
所以最后结果是6。
详情边界处理以及过程见代码。
3 代码
public int divide(int dividend, int divisor) { if (divisor == 1) { return dividend; } //overflow if (dividend == Integer.MIN_VALUE && divisor == -1) { return Integer.MAX_VALUE; } int sign = ((dividend > 0) ^ (divisor > 0)) ? -1 : 1; int answer = 0; long former = Math.abs((long)dividend); long latter = Math.abs((long)divisor); while(former >= latter){ long n = latter; int m = 1; while((n<<1) < former){ n <<=1; m <<=1; } answer += m; former = former - n; } return sign * answer; }