凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 29. Divide Two Integers

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


题目

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

题意

在不使用乘法,除法以及取模的情况下将两个整数相除。

如果发生溢出则返回 MAX_INT。

解法 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));
        int result = double(exp(t1 - t2));
        return sign * result;
    }
};