凌云的博客

LeetCode 算法题 29. 两数相除

分类：algorithm| 发布时间：2016-08-06 20:57:00

---

题目

给定两个整数，被除数 dividend 和除数 divisor。 将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2

解法 1

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(!divisor || (dividend == INT_MIN && divisor == -1)) return INT_MAX;

        int sign = ((dividend<0)^(divisor<0)) ? -1 : 1;
        long m = abs(long(dividend));
        long n = abs(long(divisor));
        int result = 0;
        while (m >= n) {
            long pow = 1, tmp = n;
            while ((tmp << 1) <= m) { pow <<= 1; tmp <<= 1; }
            result += pow;
            m -= tmp;
        }

        return sign * result;
    }
};

解法 2

class Solution {
public:
    int divide(int dividend, int divisor) {
        /** a/b = e^(ln(a))/e^(ln(b)) = e^(ln(a)-ln(b)) **/
        if (dividend == 0)  return 0;
        if(!divisor || (dividend==INT_MIN && divisor==-1)) return INT_MAX;

        int sign = ((dividend<0)^(divisor<0)) ? -1:1;
        double t1 = log(fabs(dividend));
        double t2 = log(fabs(divisor));
        long result = double(exp(t1 - t2));
        return sign * result;
    }
};