# LeetCode 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, which means losing its fractional part. For example, `truncate(8.345) = 8` and `truncate(-2.7335) = -2`.

**Note:** Assume we are dealing with an environment that could only store integers within the **32-bit** signed integer range: `[−231, 231 − 1]`. For this problem, assume that your function **returns** `231 − 1` **when the division result overflows**.

**Example 1:**

```
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.
```

**Example 2:**

```
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.
```

**Example 3:**

```
Input: dividend = 0, divisor = 1
Output: 0
```

**Example 4:**

```
Input: dividend = 1, divisor = 1
Output: 1
```

**Constraints:**

* `-2^31 <= dividend, divisor <= 2^31 - 1`
* `divisor != 0`

[English Version in Youtube](https://youtu.be/7-_MeN35y6M)

[中文版解答Youtube Link](https://youtu.be/0BdG-hLtDZ4)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV16N41197Go/)

## Solution 1: Use Long

```
class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        bool positive = true;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
            positive = false;
        }

        long new_dividend = abs((long)dividend);
        long new_divisor = abs((long)divisor);
        long result = 0;

        int power = 0;
        while (new_divisor <= (new_dividend >> 1)) {
            new_divisor = new_divisor << 1;
            power++;
        }
        
        while (power >= 0) {
            if (new_dividend >= new_divisor) {
                result += (1 << power);
                new_dividend -= new_divisor;
            }
            power--;
            new_divisor = new_divisor >> 1;
        }
        
        return positive ? result : -result;
    }
};
```

## Solution 2: Don't use Long

```
class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN) {
            if (divisor == -1) {
                return INT_MAX;
            } 
            if (divisor > 0) {
                return -1 + divide(dividend + divisor, divisor);
            } else {
                return 1 + divide(dividend - divisor, divisor);
            }
        }
        if (divisor == INT_MIN) {
            return dividend == INT_MIN ? 1 : 0;
        }
        bool positive = true;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
            positive = false;
        }

        int new_dividend = abs(dividend);
        int new_divisor = abs(divisor);
        int result = 0;

        int power = 0;
        while (new_divisor <= (new_dividend >> 1)) {
            new_divisor = new_divisor << 1;
            power++;
        }
        
        while (power >= 0) {
            if (new_dividend >= new_divisor) {
                result += (1 << power);
                new_dividend -= new_divisor;
            }
            power--;
            new_divisor = new_divisor >> 1;
        }
        
        return positive ? result : -result;
    }
};
```