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