76d0e62fe387fea051d3b3e0464cb41f
(难度Medium)Problem 29. Divide Two Integers(模拟除法)

链接

https://leetcode.com/problems/divide-two-integers/

难度等级

Medium

题干

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.

题意

给定两个数,被除数和除数,求出两数的商

要求:不能使用取模和除法操作

样例

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

  1. Both dividend and divisor will be 32-bit signed integers.

  2. The divisor will never be 0.

  3. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−$2^{31}-1$, $2^{31}-1$ − 1]. For the purpose of this problem, assume that your function returns $2^{31}-1$ when the division result overflows.

  4. 被除数和除数都是32位的int

  5. 除数不为0

  6. 对于超界的情况,返回$2^{31}-1$

题解

解法一: 减法模拟

既然不能用除法和取模的操作,想要求商,第一想到的就是通过减法来模拟。每次用被除数减去除数,当被除数小于除数时结束。

这里需要注意两点,第一点是被除数和除数可能不同号。这个问题看似比较麻烦,因为算一下排列组合一共有四种情况。但其实仔细想一下,只有同号和不同号两种情况。而且再深挖下去,会发现不论是否同号对于最终的结果唯一的影响就是正负号。

第二点是什么情况下会出现越界呢?很简单,由于计算机采用二进制补码,所以负数的上届是$-2^{31}$,而正数的上届是$2^{31}-1$,所以负数的上届比正数要大。所以如果被除数也是-1的话,则会出现超界,因此需要对这种情况进行特判。

综合一下,我们可以在开始操作之前,把被除数和除数都转化成负数,这样就避免了越界的情况。

代码并不难写:

```
class Solution {
public:
int divide(int dividend, int divisor) {
// 特判会超界的情况
if (dividend == INT_MIN) {
if (divisor == -1) return INT_MAX;
if (divisor == 1) return INT_MIN;
}
int ret = 0;
// 标记是否同号
bool mark = false;
if (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0) {
mark = true;
}

      // 全部转成负数
    if (dividend > 0)   dividend = -dividend;
    if (divisor > 0)    divisor = -divisor;
top Created with Sketch.