LeetCode 29

一、问题描述

Description:

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

If it is overflow, return MAX_INT.

不使用乘法、除法与取余操作符（即*、/、%），实现两个整数相除，返回商。

如果溢出，返回 INT_MAX。

二、解题报告

不使用*、/和%实现两个整数相除，首先想到的一个思路：

将除数不停地一个一个累加，并记录累加次数，直到大于被除数为止。

但是这种方法超时了。

一个一个累加太慢了，那么我们可以换种思路：

使用 移位 操作——左移一位相当于乘以2，而被除数是可以表示成除数的一个线性组合的形式：

dividend=divisor∗2n1+divisor∗2n2+...+divisor∗2nx

其中0≤n1≤n2≤...≤nx，故我们所要求的结果就是：

result=2n1+2n2+...+2nx

代码如下：

class Solution {
public:
    int divide(int dividend, int divisor) {
        bool positive = true;                // 表示结果的正负
        if((dividend>0 && divisor<0) || (dividend<0 && divisor>0))
            positive = false;

        int64_t absDividend = abs((int64_t)dividend);
        int64_t absDivisor = abs((int64_t)divisor);
        int64_t result = 0;

        while(absDivisor <= absDividend) {
            int64_t tmp = absDivisor;
            int64_t count = 1;
            while((tmp<<1) <= absDividend) {
                tmp = tmp<<1;                // divisor*2^n
                count = count<<1;            // count = 2^n
            }
            result += count;                 // 系数累加
            absDividend -= tmp;
        }

        if(positive && result >= INT_MAX)
            return INT_MAX;

        return positive ? result:-result;
    }
};

int的范围是 [-2147483648，2147483647]，所以存在的溢出情况是：-2147483648除以-1，此时应该输出INT_MAX。

AC 时间 4ms！

LeetCode答案源代码：https://github.com/SongLee24/LeetCode