leetcode第28题--Divide Two Integers

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

分析：题目意思很容易理解，就是不用乘除法和模运算求来做除法，很容易想到的一个方法是一直做减法，然后计数，超时。在网上找到一种解法，利用位运算，意思是任何一个整数可以表示成以2的幂为底的一组基的线性组合，即num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n。基于以上这个公式以及左移一位相当于乘以2，我们先让除数左移直到大于被除数之前得到一个最大的基n的值，说明被除数中至少包含2^n个除数，然后减去这个基数，再依次找到n-1，...，1的值。将所有的基数相加即可得到结果。具体代码如下：

class Solution {

public:

    int divide(int dividend, int divisor) {

        int res = ;

        int flag = ;

        if((dividend< && divisor>) || (dividend> && divisor<))

            flag = -;

        long long d = abs((long long)dividend); // 为什么只有 long long才可以

        long long s = abs((long long)divisor);

        while(s<=d)

        {

            int cnt = ;

            long long  tmp = s; // 只有long long才可以

            tmp<<=;

            while(tmp<=d)

            {

                cnt<<=;

                tmp<<=;

            }

            res+=cnt;

            d-=(tmp>>=);

        }

        return (int)flag*res;

    }

};

很巧妙，学会利用位运算。还有要用long long。tem<<=1 是tmp= tmp<<1 的意思。 &&的优先级比||的高。

巴特西

leetcode第28题--Divide Two Integers

最新文章

热门文章