# 0029. 两数相除
### 题目地址(29. 两数相除)
### 题目描述
```
给定两个整数，被除数 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。
```
### 前置知识
* 二分法
### 公司
* Facebook
* Microsoft
* Oracle
### 思路
符合直觉的做法是，减数一次一次减去被减数，不断更新差，直到差小于 0，我们减了多少次，结果就是多少。
核心代码：
```js
let acc = divisor;
let count = 0;
while (dividend - acc >= 0) {
acc += divisor;
count++;
}
return count;
```
这种做法简单直观，但是性能却比较差. 下面来介绍一种性能更好的方法。
通过上面这样的分析，我们直到可以使用二分法来解决，性能有很大的提升。
### 关键点解析
* [二分查找](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/91/binary-search)
* 正负数的判断中，这样判断更简单。
```js
const isNegative = dividend > 0 !== divisor > 0;
```
或者利用异或：
```js
const isNegative = dividend ^ (divisor < 0);
```
### 代码
* 语言支持：JS, Python3, CPP
```js
/*
* @lc app=leetcode id=29 lang=javascript
*
* [29] Divide Two Integers
*/
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
var divide = function (dividend, divisor) {
if (divisor === 1) return dividend;
// 这种方法很巧妙，即符号相同则为正，不同则为负
const isNegative = dividend > 0 !== divisor > 0;
const MAX_INTERGER = Math.pow(2, 31);
const res = helper(Math.abs(dividend), Math.abs(divisor));
// overflow
if (res > MAX_INTERGER - 1 || res < -1 * MAX_INTERGER) {
return MAX_INTERGER - 1;
}
return isNegative ? -1 * res : res;
};
function helper(dividend, divisor) {
// 二分法
if (dividend <= 0) return 0;
if (dividend < divisor) return 0;
if (divisor === 1) return dividend;
let acc = 2 * divisor;
let count = 1;
while (dividend - acc > 0) {
acc += acc;
count += count;
}
// 直接使用位移运算，比如acc >> 1会有问题
const last = dividend - Math.floor(acc / 2);
return count + helper(last, divisor);
}
```
Python3 Code:
```python
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
"""
二分法
:param int divisor
:param int dividend
:return int
"""
# 错误处理
if divisor == 0:
raise ZeroDivisionError
if abs(divisor) == 1:
result = dividend if 1 == divisor else -dividend
return min(2**31-1, max(-2**31, result))
# 确定结果的符号
sign = ((dividend >= 0) == (divisor >= 0))
result = 0
# abs也可以直接写在while条件中，不过可能会多计算几次
_divisor = abs(divisor)
_dividend = abs(dividend)
while _divisor <= _dividend:
r, _dividend = self._multi_divide(_divisor, _dividend)
result += r
result = result if sign else -result
# 注意返回值不能超过32位有符号数的表示范围
return min(2**31-1, max(-2**31, result))
def _multi_divide(self, divisor, dividend):
"""
翻倍除法，如果可以被除，则下一步除数翻倍，直至除数大于被除数，
返回商加总的结果与被除数的剩余值；
这里就不做异常处理了；
:param int divisor
:param int dividend
:return tuple result, left_dividend
"""
result = 0
times_count = 1
while divisor <= dividend:
dividend -= divisor
result += times_count
times_count += times_count
divisor += divisor
return result, dividend
```
CPP Code:
```cpp
class Solution {
public:
int divide(int dividend, int divisor) {
if (!divisor) return 0; // divide-by-zero error
bool pos1 = dividend > 0, pos2 = divisor > 0, pos = !(pos1^pos2);
if (pos1) dividend = -dividend;
if (pos2) divisor = -divisor;
int q = 0, d = divisor, t = 1;
while (t > 0 && dividend < 0) {
if (dividend - d <= 0) {
dividend -= d;
q -= t;
if ((INT_MIN >> 1) < d) {
t <<= 1;
d <<= 1;
}
} else {
d >>= 1;
t >>= 1;
}
}
return pos? -q : q;
}
};
```
**复杂度分析**
* 时间复杂度：$O(logN)$
* 空间复杂度：$O(1)$
### 相关题目
* [875.koko-eating-bananas](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/875.koko-eating-bananas)
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 