# 整数除法
 [](https://imhuay.gitbook.io/studies/algorithms/..#中等) [](https://imhuay.gitbook.io/studies/algorithms/..#剑指offer2) [](https://imhuay.gitbook.io/studies/algorithms/..#二分查找) [](https://imhuay.gitbook.io/studies/algorithms/..#经典)
**问题简述**
```
给定两个整数 a 和 b ，求它们的除法的商 a/b。
要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%'。
```
详细描述
```
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%'。
注意：
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31−1]。本题中，如果除法结果溢出，则返回 2^31 − 1
示例 1：
输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7
示例 2：
输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2
示例 3：
输入：a = 0, b = 1
输出：0
示例 4：
输入：a = 1, b = 1
输出：1
提示:
-2^31 <= a, b <= 2^31 - 1
b != 0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xoh6Oh
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```
**思路1：减法（超时）**
* 用 a 循环减 b，直到为负；
* 越界讨论：因为是整数除法，实际的越界情况就一种，就是 `a=-2^31,b=-1`
* 极端情况：`a=2^31-1, b=1` 要循坏 `2^31-1` 次；
Python
```python
class Solution:
def divide(self, a: int, b: int) -> int:
assert b != 0
MAX = 2 ** 31 - 1
if a == 0: return 0
if a == -2 ** 31 and b == -1: return MAX # 越界
# 转为两个整数操作
sign = 1
if a < 0:
sign *= -1
a = -a
if b < 0:
sign *= -1
b = -b
# 循坏减去 b
ret = -1
while a > 0:
a -= b
ret += 1
if a == 0: # 整除的情况
ret += 1
return sign * ret
```
**思路2：二分思想**
1. 初始化返回值 `ret = 0`
2. `a > b` 时，不断将 `b` 翻倍（乘 2），直到再翻倍一次就大于 `a`，记翻倍后的数为 `tmp_b`，翻的倍数为 `tmp`，然后将 `ret` 加上 `tmp`、`a` 减去 `tmp_b`；
3. `a` 减去 `tmp_b` 后循环以上过程，直到 `a` 小于 `b`；
```
以 a = 32, b = 3 为例，模拟过程如下：
初始化 ret = 0
第一轮：
32 / (3*2*2*2) = t1 / (1*2*2*2) # 再乘一个 2 会大于 32
32 / 24 = 1 = t1 / 8 -> t1 = 8
(32 - 24) / 3 = 8 / 3
ret += t1 -> 8
第二轮：
8 / (3*2) = t2 / (1*2)
8 / 6 = 1 = t2 / 2 -> t2 = 2
(8 - 6) / 3 = 0
ret += t2 -> 10
因为 2 < 3 退出循环
```
Python
```python
class Solution:
def divide(self, a: int, b: int) -> int:
assert b != 0
if a == 0: return 0
if a == -2**31 and b == -1: return 2 ** 31 - 1
sign = 1 if (a > 0 and b > 0) or (a < 0 and b < 0) else -1
a = a if a > 0 else -a
b = b if b > 0 else -b
# if a < b: return 0
ret = 0
while a >= b:
tmp, tmp_b = 1, b
while tmp_b * 2 < a:
tmp_b *= 2
tmp *= 2
ret += tmp
a -= tmp_b
return ret * sign
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://imhuay.gitbook.io/studies/algorithms/problems/2022/09/jian-zhi-offer2001-zhong-deng-zheng-shu-chu-fa.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.