solution.md

# 两数相除

<p>给定两个整数，被除数&nbsp;<code>dividend</code>&nbsp;和除数&nbsp;<code>divisor</code>。将两数相除，要求不使用乘法、除法和 mod 运算符。</p><p>返回被除数&nbsp;<code>dividend</code>&nbsp;除以除数&nbsp;<code>divisor</code>&nbsp;得到的商。</p><p>整数除法的结果应当截去（<code>truncate</code>）其小数部分，例如：<code>truncate(8.345) = 8</code> 以及 <code>truncate(-2.7335) = -2</code></p><p>&nbsp;</p><p><strong>示例&nbsp;1:</strong></p><pre><strong>输入:</strong> dividend = 10, divisor = 3<strong><br />输出:</strong> 3<strong><br />解释: </strong>10/3 = truncate(3.33333..) = truncate(3) = 3</pre><p><strong>示例&nbsp;2:</strong></p><pre><strong>输入:</strong> dividend = 7, divisor = -3<strong><br />输出:</strong> -2<strong><br />解释:</strong> 7/-3 = truncate(-2.33333..) = -2</pre><p>&nbsp;</p><p><strong>提示：</strong></p><ul>	<li>被除数和除数均为 32 位有符号整数。</li>	<li>除数不为&nbsp;0。</li>	<li>假设我们的环境只能存储 32 位有符号整数，其数值范围是 [&minus;2<sup>31</sup>,&nbsp; 2<sup>31&nbsp;</sup>&minus; 1]。本题中，如果除法结果溢出，则返回 2<sup>31&nbsp;</sup>&minus; 1。</li></ul>
<p>以下错误的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    int res;
    res = sol.divide(10, 3);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    int divide(int dividend, int divisor)
    {
        if (dividend == 0 || divisor == 1)
            return dividend;
        if (divisor == -1)
            return dividend == INT_MIN ? INT_MAX : -dividend;
        int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
        int res = div(-abs(dividend), -abs(divisor));
        return sign == 1 ? res : -res;
    }
    int div(int a, int b)
    {
        if (a > b)
            return 0;
        int cnt = 1, val = b;
        while (val - a + val >= 0)
        {
            cnt <<= 1;
            val += val;
        }
        return div(a - val, b);
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    int divide(int dividend, int divisor)
    {
        int signal = 1;
        unsigned int dvd = dividend;
        if (dividend < 0)
        {
            signal *= -1;
            dvd = ~dvd + 1;
        }
        unsigned int dvs = divisor;
        if (divisor < 0)
        {
            signal *= -1;
            dvs = ~dvs + 1;
        }
        int shift = 0;
        while (dvd > dvs << shift)
        {
            shift++;
        }
        unsigned int res = 0;
        while (dvd >= dvs)
        {
            while (dvd < dvs << shift)
            {
                shift--;
            }
            res |= (unsigned int)1 << shift;
            dvd -= dvs << shift;
        }
        if (signal == 1 && res >= INT_MAX)
        {
            return INT_MAX;
        }
        else
        {
            return res * signal;
        }
    }
};
```

### B

```cpp
class Solution
{
public:
    int divide(int dividend, int divisor)
    {
        if (dividend == INT_MIN && divisor == -1)
            return INT_MAX;
        if (dividend == 0)
            return 0;
        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
        long x = (dividend < 0) ? -(long)dividend : (long)dividend;
        long y = (divisor < 0) ? -(long)divisor : (long)divisor;
        long result = 0;
        while (x >= y)
        {
            long temp = y, mid = 1;
            while (x >= (temp << 1))
            {
                mid <<= 1;
                temp <<= 1;
            }
            result += mid;
            x -= temp;
        }
        return sign > 0 ? result : -result;
    }
};
```

### C

```cpp
class Solution
{
public:
    int divide(int dividend, int divisor)
    {
        int INI_MIN = -2147483648, INI_MAX = 2147483647;
        if (dividend == divisor)
            return 1;
        if (divisor == 1)
            return dividend;
        if (dividend == INI_MIN && divisor == -1)
            return INI_MAX;
        if (divisor == INI_MIN)
        {
            if (dividend == INI_MIN)
                return 1;
            else
                return 0;
        }

        bool sign = false;
        if (dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0)
        {
            sign = true;
        }

        int result_1 = 0;
        if (dividend == INI_MIN)
        {
            if (divisor > 0)
                dividend = dividend + divisor;
            else
                dividend = dividend - divisor;
            result_1++;
        }

        dividend = abs(dividend);
        divisor = abs(divisor);
        while (dividend >= divisor)
        {
            unsigned int temp = divisor, res = 1;

            while (dividend >= (temp << 1))
            {
                res <<= 1;
                temp <<= 1;
            }

            result_1 += res;
            dividend -= temp;
        }
        if (sign == true)
        {
            return result_1;
        }
        else
        {
            return -result_1;
        }
    }
};
```