29. Divide Two Integers 两数相除

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

If it is overflow, return MAX_INT.

Difficulty: Medium

这道题让我们求两个数相除A/B,并且不让使用乘法,除法,取余运算.这样我们只能优先想到位运算和加减法了. 假设A>B,最容易想到的是把A-B赋值给A,并且结果+1,然后再把A-B赋值给A,结果+1.这样一直下去.不过如果是2147483647/1这种情况不会不会通过OJ,因为效率太低,会提示Time Limit Exceeded,不可行.回头想想上面的位运算还没用到,如果A>2*B那么结果是不是加2,如果A>2*2*2B结果是不是加2*2.定义t为除数,p为结果的计数m为被除数的绝对值,n为除数的绝对值.例如100/2

t
(除数)
p
(计数)
res
(结果)
m
(被除数)
t
(除数)
p
(计数)
res
(结果)
m
(被除数)
t
(除数)
p
(计数)
res
(结果)
m
(被除数)
2 1 32 36 2 1 48 4 2 1 50 0
4 2 4 2 4 2
8 4 8 4
16 8 16 8
32 16 32 16
64 32

解法1

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (divisor==0||(dividend==INT_MIN&&divisor==-1)) return INT_MAX;
        int sign = ((dividend<0)^(divisor<0))?-1:1;
        long long m = abs((long long)dividend),n = abs((long long)divisor), res = 0;
        if (n==1) return sign==1?m:-m;
        while (m>=n)
        {
            long long t = n,p = 1;
            while(m>=(t<<1))
            {
                t <<= 1;
                p <<= 1;
            }
            res += p;
            m -= t;
        }
        return sign==1?res:-res;
    }
};

上面去 long long 类型一时怕,INT_MAX取绝对值的时候会溢出,二是防止在位运算左移的时候溢出.

解法2

思路和上面一样,就是写法简洁下

class Solution {
public:
    int divide(int dividend, int divisor) {
        long long m = abs((long long)dividend),n = abs((long long)divisor), res = 0;
        if (m<n) return 0;
        while(m>=n)
        {
            long long t = n,p=1;
            while(m>(t<<1)){
                t<<=1;
                p<<=1;
            }
            res += p;
            m -= t;
        }
        if ((dividend<0)^(divisor<0)) res = -res;
        return res>INT_MAX?INT_MAX:res;
    }
};

解法3

采用递归,思路和解法1相同

class Solution {
public:
    int divide(int dividend, int divisor) {
        long long m = abs((long long)dividend),n = abs((long long)divisor),res = 0;
        if (m<n) return 0;
        long long t = n,p=1;
        while(m>=(t<<1))
        {
            t<<=1;
            p<<=1;
        }
        res += p+divide(m-t,n);
        if ((dividend<0)^(divisor<0)) res = -res;
        return res>INT_MAX?INT_MAX:res;
    }
};

参考资料:http://www.cnblogs.com/grandyang/p/4431949.html

 
comments powered by Disqus