两数相除

给定两个整数，被除数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

Solution

超时~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (divisor == 0 || dividend == 0) {
            return 0;
        }
        int sum = 0;
        unsigned count = 0;
        int flagend = (dividend < 0) ? -1 : 1;
        int flagsor = (divisor < 0) ? -1 : 1;
        while (1) {
            if (flagend < 0 && flagsor < 0 && (sum <= (INT_MIN - divisor) || sum < dividend - divisor)) {
                return count;
            }
            if (flagend < 0 && flagsor > 0 && (sum >= (INT_MAX - divisor) || -sum < dividend + divisor)) {
                return -count;
            }
            if (flagend > 0 && flagsor > 0 && (sum >= (INT_MAX - divisor) || sum > dividend - divisor)) {
                return count;
            }
            if (flagend > 0 && flagsor < 0 && (sum <= (INT_MIN - divisor) || -sum > dividend + divisor)) {
                return -count;
            }
            sum += divisor;
            count++;
        }
        count--;
        return count * flagend * flagsor;
    }
};

int main() {
    std::cout << Solution().divide(10, 3)  << std::endl; // 3
    std::cout << Solution().divide(7, -3)  << std::endl; // -2
    std::cout << Solution().divide(0, 1)  << std::endl; // 0
    std::cout << Solution().divide(1, 1)  << std::endl; // 1
    std::cout << Solution().divide(-1, 1)  << std::endl; // -1
    std::cout << Solution().divide(-2147483648, -1) << std::endl; // 2147483647 
}