Divide Two Integers

https://leetcode.com/problems/divide-two-integers/description/

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

If it is overflow, return MAX_INT.

Thoughts

不用任何乘，除和mod操作实现实现除法。除法本质上是数dividend由多少个divisor相加可构成。比如32 = 24 + 8 = 3 * 2^3 + 3 * 2 + 2。而divisor * 2^i可以通过位左移得到，因此不断让divisor左移cnt次, 直到超过dividend，然后让dividend减去divisor * 2^(cnt - 1)，再重复此过程直到dividend比divisor还小。

Code

/*
 * @lc app=leetcode id=29 lang=cpp
 *
 * [29] Divide Two Integers
 */

// @lc code=start
class Solution {
public:
    int divide(int dividend, int divisor) {
        bool neg = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0);
        long d = labs(dividend), s = labs(divisor), res = 0;
        while (d >= s) {
            long tmp = s, count = 1;
            while (tmp <= d) {
                tmp <<= 1;
                count <<= 1;
            } 
            res += count >> 1;
            d -= tmp >> 1;
        } 
        if (neg) res = ~res + 1;
        return res > INT_MAX ? INT_MAX : (int) res;
    }
};
// @lc code=end

Analysis

divisor * 2 ^ t = dividend, 时间复杂度O(lgN)