## Saturday, November 15, 2014

### [LeetCode] Divide Two Integers

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

res = 0

1. 先找到a使x*2^a <= y < x*2^(a+1)，res += 2^a，y = y - x*2^a

2. if(y >= x*2^(a-1) {res+=2^(a-1); y = y - x*2^(a-1);}

3. if(y >= x*2^(a-2) {res+=2^(a-2); y = y - x*2^(a-2);}

...

corner case，非常重要：

(1) x, y可能会是负数
(2) x可能为0时，返回INT_MAX或INT_MIN
(3) INT_MIN / -1 > INT_MAX，overflow

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27``` ```class Solution { public: int divide(int dividend, int divisor) { if(!divisor) return dividend>=0 ? INT_MAX : INT_MIN; if(dividend==INT_MIN && divisor==-1) return INT_MAX; //overflow problem bool isNeg = false; if((dividend<0 && divisor>0) || (dividend>0 && divisor<0)) isNeg = true; unsigned long long dvd = abs((long long)dividend); unsigned long long dvs = abs((long long)divisor); unsigned long long dvs_original = dvs; int i = 0; while(dvs<<(i+1) <= dvd) i++; int res = 0; while(dvd>=dvs_original) { if(dvd >= dvs<

#### 1 comment:

1. int res; 这个似乎有overflow的风险。
极端的case -0x80000000/1