Divide two integers without using multiplication, division and mod operator.
思路:这道题是在别人的提示下用二分搜索才想到的。设被除数为a,除数为b,主要是找出a落在[2^k*b,2^(k+1)*b]的区间,左侧小于a,右侧大于a。然后设置一个指针,为2^(k-1)*b,判断a落在[2^k*b, 2^k*b+2^(k-1)*b]、[2^k*b+2^(k-1)*b,2^(k+1)*b]的哪个区间,然后再设置指针为2^(k-2)*b,继续上述步骤,区间逼近于a。
class Solution { public: int toPositive(long long n, bool positive) { if (!positive) { n = 0 - n; } return n; } int divide(int dividend, int divisor) { bool positive = true; long long longDividend = dividend; long long longDivisor = divisor; if (dividend < 0 && divisor < 0) { longDividend = 0 - (long long)dividend; longDivisor = 0 - (long long)divisor; } else if (dividend < 0 && divisor > 0) { positive = false; longDividend = 0 - (long long)dividend; } else if (dividend >= 0 && divisor < 0) { positive = false; longDivisor = 0 - (long long)divisor; } long long i = 1; long long divid = longDivisor,num; long long res = 0; while(divid < longDividend) { i = i << 1; divid = divid << 1; } if (divid == longDividend) { return toPositive(i, positive); } divid = divid >> 1; i = i >> 1; num = divid; res = i; while(divid > longDivisor) { divid = divid >> 1; i = i >> 1; if (num + divid <= longDividend) { res += i; num += divid; } } return toPositive(res, positive); } };