> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/math/29.-divide-two-integers.md).

# 29. Divide Two Integers

Given two integers `dividend` and `divisor`, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing `dividend` by `divisor`.

The integer division should truncate toward zero.

**Example 1:**

```
Input: dividend = 10, divisor = 3
Output: 3
```

**Example 2:**

```
Input: dividend = 7, divisor = -3
Output: -2
```

**Note:**

* Both dividend and divisor will be 32-bit signed integers.
* The divisor will never be 0.
* Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: \[−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

```cpp
// Bit Manipulation
int divide(int dividend, int divisor) { // time: O(log(m)); space: O(1)
    if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;
    int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
    long m = labs(dividend), n = labs(divisor), res = 0;
    while (m >= n) {
        long tmp = n, cnt = 1;
        while (m >= (tmp << 1)) {
            tmp <<= 1;
            cnt <<= 1;
        }
        m -= tmp;
        res += cnt;
    }
    return sign == 1 ? res : -res;
}
```

{% hint style="info" %}
第二個方法是利用數學指數對數的關係。
{% endhint %}

$$
t = ln(m/n) = ln(m) - ln(n)
$$

$$
m/n = exp(t)
$$

```cpp
// Math
int divide(int dividend, int divisor) { // time: O(1); space: O(1)
    if (dividend == 0) return 0;
    if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;
    double ln_m = log(fabs(dividend)), ln_n = log(fabs(divisor));
    long res = double(exp(ln_m - ln_n));
    return (dividend > 0) ^ (divisor > 0) ? -res : res;
}
```