Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Divide Two Integers

Leetcode algorithms 第 29 题:Divide Two Integers

题目

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

If it is overflow, return MAX_INT.

解答

不使用乘法、除法、取模实现除法运算,最直接就是不断地使用减法,知道不能再减为止。但这样的效率非常低,特别是在被除数很大而除数很小的情况。

虽然不能使用乘法,但可以使用位移运算增加效率,因为左移一位相当于乘以2,于是, 在每次循环中,不是直接减去除数,而是把除数左移,直到除数刚好不大于被除数时才进行减法,同时把此时左移的次数对应的乘数加到最终结果中。

同时,需要注意正负数的问题,首先记录下结果的正负号,然后把所有的数字转成正数,就可以进行正数的运算。另外,把一个负数转成正数可能会溢出,因为最小负数的绝对值比最大整数的绝对值大一,为了避免溢出,这里统一把所有的数字转化成long long再进行处理,并且返回之前再判断一次是否溢出。

具体代码如下:

class Solution {
public:
    int divide(int dividend, int divisor) {
        bool neg = (dividend>0 && divisor<0) || (dividend<0 && divisor>0); //记录结果的正负
        long long a = abs((long long)dividend), b = abs((long long)divisor), ans = 0; //转成正数
        while (a >= b)
        {
            long long t = b, cnt = 1;
            while (t < a) t <<= 1, cnt <<= 1; //左移直到除数大于被除数再进行减法
            if (t > a) t >>= 1, cnt >>= 1;
            a -= t, ans += cnt;
        }
        ans = neg ? -ans : ans;
        return ans > INT_MAX ? INT_MAX : ans; //判断溢出
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论