# Divide Two Integers

> 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

```cpp
/*
 * @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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/math/divide-two-integers.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.