Leetcode 29 Divide Two Integers 位操作的巧妙运用

triplebee

发布于 2018-01-12 15:08:26

7010

发布于 2018-01-12 15:08:26

文章被收录于专栏：计算机视觉与深度学习基础

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

If it is overflow, return MAX_INT.

题意很简单，实现两数除法，但是不能用乘法，除法和取模。

怎么样？第一感觉就是用减法，但是被除数很大，除数为1的时候肯定会超时，

那就模拟手工除法，按位减呗，这样每一位减的次数最多不会超过10次，

很好，问题又来了，在不允许乘除取模的情况下，如何获取高位？

卡住了。。。

我想了一种列出10，100，1000....位表的方法，通过对每一位反复减去对应位表的数的操作获取每一位的数字，可是这种方法实现起来细节太过繁琐了。

我看了一下discuss，他们用了一种类似进制转换的方法，用位操作代替了*2的操作，想法很好，

其实本质也是模拟除法，只不过它以除数为基，每次扩大为原来的两倍，精髓在于能想到位操作。

注意溢出的边界和中间变量的类型，已标在代码中。

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(divisor==0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;//两种溢出的情况
        int flag1=dividend<0?-1:1,flag2=divisor<0?-1:1;
        int pre=flag1==flag2?1:-1;
        long long dividend2=flag1==1?dividend:-(long long)dividend; //转正数，int类型在INT_MIN值下会炸
        long long divisor2=flag2==1?divisor:-(long long)divisor;
        int result=0;
        while(dividend2>=divisor2) 
        {
            long long rm=divisor2,base=1;
            while(dividend2>=rm)
            {
                rm<<=1;
                base<<=1;
            }
            rm>>=1;
            base>>=1;
            dividend2-=rm;
            result+=base;
        }
        result=pre==1?result:-result; //符号
        return result;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016-09-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除

division