[LeetCode] Divide Two Integers

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


思路:

整数近似除法：32/3 = 10

显然求近似除法可以用乘法来二分查找：32 ~ 3*10 = 3*[1*(2^3) + 0*(2^2) + 1*(2^1) + 0*(2^0)]

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);}

...

但题目不允许用乘法，可以用移位代替：x*2^i = x<<i：

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<<i) { dvd -= dvs<<i; res += 1<<i; } i--; } return isNeg ? 0-res : res; } };

总结：

这题要考虑到所有corner case并写对不容易。另外还有一个非常容易犯错的地方：

找到a使x*2^a <= y < x*2^(a+1)，这一步对应程序里的while(dvs<<(i+1) <= dvd) i++;

这里dvs和dvd必须将原来的dividend和divisor转化成unsigned long long类型。不然divisor左移时可能会变成负数从而陷入死循环。