029 - Divide Two Integers

Divide Two Integers

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
Hide Tags
Math Binary Search

越是这种基础的东东，越是坑多。。。
--1.1 除数是 0，溢出；
--1.2 INT_MIN 除以 -1，无法表示，溢出；
--2.1 剪枝，相等返回 1；
--3.1 剪枝，被除数为 0，返回 0；
--3.2 剪枝，被除数为 INT_MIN，返回 0，因为没有 int 绝对值比它大 （INT_MAX不行，因为可能用 INT_MIN 来做被除数）；
          这条必须在 2.1 之后，不然两者都是 INT_MIN 就该返回 1.
--4.1 剪枝，两数相加为 0，返回 -1；这条必须在 1.1 之后，不然可能 0/0.
--5.1 剪枝，除数为 1， 返回被除数；
--5.2 剪枝，除数为 -1，返回 0 - 被除数；
-- 然后取绝对值，如果被除数小于除数，无需处理，返回 0；
         注意这期间所有的运算都要用 long 以防止移位或者加法的时候 int 不够用。
-- 反之处理，先是把除数不断左移（即乘 2），直到比被除数大，
         这期间商也不断左移。（注意商初始值是 0，第一次不是移位而是赋值为 1）
    然后在这个大一些的数和它的一半之间，二分查找被除数，
         这期间，商的增幅的步长（step）每次减半（右移），因为每次查找的范围缩小一半。
         被除数等于中间值，直接返回 rst （此时不需要再加上步长，因为没有进入下一次折半的过程）
         大于或者小于，则进入下一次折半查找的过程。
-- 最后根据两数的符号位，修正结果的符号位以便输出。

class Solution {
public:
    int divide(int dividend, int divisor) {
        if((!divisor) || (INT_MIN == dividend && -1 == divisor))     // 1.1，1,2 溢出
            return INT_MAX;
        if(dividend == divisor)                                      // 2.1，剪枝，必须在3.2之前
            return 1;
        if(!dividend || (INT_MIN == divisor))                        // 3.1,3.2 剪枝，肯定为0的情况
            return 0;
        if(0 == dividend + divisor)                                  // 4.1，剪枝，两数相反
            return -1;
        if(1 == divisor)                                             // 5.1，剪枝，没必要查找
            return dividend;
        if(-1 == divisor)                                            // 5.2，剪枝，没必要查找
            return -dividend;
        long p=abs((long)dividend), q=abs((long)divisor), rst=0;
        if(q<=p)
        {
            while(q<=p)
                q = q<<1, rst = (rst)? (rst<<1) : 1;
            if(q>p)
                bsearch(q>>1, q, p, (rst>>1), rst);
            if((0<dividend && 0>divisor)||(0>dividend && 0<divisor)) //可能是负数的情况
                rst = -rst;
        }
        return (int)rst;
    }
   
    void bsearch(long start, long end, long tgt, long step, long& rst)
    {
        if(start>end)
            return;
        long mid = ((start + end)>>1);
        rst += (mid < tgt) ? step : 0;                               //只有进入大的半区才需要补加一个步长
       
        if(mid > tgt)
            bsearch(start, mid-1, tgt, (step>>1), rst);
        if(mid < tgt)
            bsearch(mid+1, end, tgt, (step>>1), rst);
        return;
    }
};   

8 ms.

看了一下讨论区，有个不错的解法，代码相对简洁一些。
他的思路是找到除数移位之后，离被除数最近的那个数字，然后依次用被除数减去它，
然后用减过之后的结果，进入下一次循环，重复这个过程，
在这个过程中，把所有需要移位的 shift 值对应的 bit 位都置为 1，就得到了结果。
类似的做法，还有一个帖子分析得很仔细。

Use long long to avoid overflow in the calculation.
First, detect two corner cases : divide-0 and INTMIN/-1 and return INTMAX directly.
Then do the division via bit shift and minus operations. Say z = x/y and z in binary bit format is z31, z30, z29, ... z0, the while loop is to detect those non-zero bits of z and combine them to get z. (for example, x=11, y =2, z =5 = (0x101)) , Through while loop, we will get shift =2 (bit 2 of z is nonzero) first, then get shift = 0 (bit 0 of z is nonzero). so res = 1<<2 + 1<<0 = 5;

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(!divisor) return INT_MAX;
        if(dividend== INT_MIN && divisor==-1) return INT_MAX;
        long long x = dividend>0 ? dividend: -(long long)(dividend);
        long long y = divisor>0 ? divisor:-(long long)(divisor);
        int shift=32, res =0;
        bool neg = (dividend>0) ^ (divisor>0);
        while(x>=y)
        {
            while( x < (y<<shift))
                --shift;
            res |= 1<< shift;    
            x -= (y<<shift);
        }
        return neg?-res:res;
    }
};