29. Divide Two Integers

题目：

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

If it is overflow, return MAX_INT.

链接：https://leetcode.com/problems/divide-two-integers/#/description

4/13/2017

没做出来，时间超了

以下是我没做出来的答案,通不过OA

public class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0) return Integer.MAX_VALUE;
        if (dividend == 0 || dividend > 0 && divisor > 0 && dividend < divisor || dividend < 0 && divisor < 0 && dividend > divisor) return 0;
        if (divisor == 1) return dividend;
        else if (divisor == -1) {
            if (dividend == Integer.MIN_VALUE) return Integer.MAX_VALUE;
            return -dividend;
        }
        if (dividend == divisor) return 1;
        else if (dividend == -divisor) return -1;

        int sign = 1;

        if (dividend > 0 && divisor < 0) {
            divisor = -divisor;
            sign = -1;
        } else if (dividend < 0 && divisor > 0) {
            dividend = -dividend;
            sign = -1;
        }

        int initDivisor = divisor;
        int quotient = 0;
        int times = 0;

        while (dividend >= initDivisor) {
            while (dividend > divisor) {
                divisor <<= 1;
                if (times == 0) times = 1;
                else             times <<= 1;
            }
            quotient += times;
            dividend -= divisor >> 1;
            divisor = initDivisor;
            times = 0;
        }
        return sign == 1? quotient: -quotient;
    }
}

需要再研究这道题，可以参考：

http://www.cnblogs.com/yrbbest/p/4435159.html

别人的做法，很喜欢这么详细的解释。

不过要注意他在中间把signed int变成了unsigned int解决了中间计算溢出的问题，我认为最好还是不要这么做。

we assure the factor ret's binary fomula is

ret = a0 + a1*2 + a2*2^2 + ...... + a29*2^29 + a30*2^30 + a31*2^31; ai = 0 or 1, i = 0......31

the dividend B and divisor A is non-negative, then

A(a0 + a1*2 + a2*2^2 + ...... + a29*2^29 + a30*2^30 + a31*2^31) = B; Eq1

(1) when Eq1 divided by 2^31, we can get A*a31 = B>>31; then a31 = (B>>31)/A;

if (B>>31) > A, then a31 = 1; else a31 = 0;

(2) when Eq1 divided by 2^30, we can get A*a30 + A*a30*2 = B>>30; then a30 = ((B>>30) - a30*A*2)/A; and (B>>30) - a31*A*2 can be rewritten by (B-a31*A<<31)>>30, so we make B' = B-a31*A<<31, the formula simplified to a30 = (B'>>30)/A

if (B'>>31) > A, then a30 = 1; else a30 = 0;

(3) in the same reason, we can get a29 = ((B-a31*A<<31-a30*A<<30)>>29)/A, we make B'' = B' - a30*A<<30, the formula simplified to a29 = (B''>>29)/A;

do the same bit operation 32 times, we can get a31 ..... a0, so we get the ret finally.

the C solution with constant time complexity

int divide(int dividend, int divisor) {
    //special cases
    if(divisor == 0 || (dividend == INT_MIN && divisor == -1))
        return INT_MAX;
    
    // transform to unsigned int
    bool sign = (dividend > 0)^(divisor > 0);
    unsigned int A = (divisor < 0) ? -divisor : divisor;
    unsigned int B = (dividend < 0) ? -dividend : dividend;
    int ret = 0;
    
    // shift 32 times
    for(int i = 31; i >= 0; i--)
    {
        if((B>>i) >= A)
        {
            ret = (ret<<1)|0x01;
            B -= (A<<i);   // update B
        }
        else
            ret = ret<<1;
    }
    
    if(sign)
        ret = -ret;
    
    return ret;
}

https://discuss.leetcode.com/topic/17600/32-times-bit-shift-operation-in-c-with-o-1-solution

更多讨论：

https://discuss.leetcode.com/category/37/divide-two-integers 

4/27/2017

36ms, 97%

自己重新做了一遍并且参考别人的答案。

思路：

按照之前的意思，通过计算最高位的系数来算答案。

1. 当除数和被除数没有Integer.MIN_VALUE时，dividend, divisor都转化成positive来计算。

当前剩余dividend >>i 和divisor比较，如果大于divisor，答案＊2 ＋ 1，并且dividend减去divisor；如果小于divisor，答案*2，不做额外加减。最后一步通过最初的符号来判断

2. 当除数和被除数有一个是Integer.MIN_VALUE时

转化为positive会造成overflow，需要用负数来计算。

当除数divisor是Integer.MIN_VALUE，答案只有1（被除数也是MIN_VALUE）或者0（其他所有任何数）

其他情况，将divisor也变成负数，所以这时除数和被除数都是负数。

负数的判断，谁的值大，谁的绝对值小，根据第1中情况

当前剩余dividend >>i 和divisor比较，如果大于divisor，答案＊2 ＋ 1，并且dividend减去divisor；如果小于divisor，答案*2，不做额外加减。最后一步通过最初的符号来判断

当dividend >> i大于divisor时，其实当前高位应该是0，答案＊2不做额外加减，当小于divisor时，dividend>>i绝对值大，当前高位应该是1，答案＊2 ＋ 1.

特别重要的一点，移位运算，建议强制加括号，运算级太低了。

第43行，注意，其实dividend的值是越来越大的（绝对值越来越小）不会溢出，因为divisor是负数，divisor << i变成了一个绝对值更大的负数。dividend的值也越来越从负的接近于0

public class Solution {
    /**
     * @param dividend the dividend
     * @param divisor the divisor
     * @return the result
     */
    public int divide(int dividend, int divisor) {
        // Write your code here
        if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        } else if (dividend == 0) {
            return 0;
        } else if (divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return -dividend;
        }

        boolean isNegative = (dividend > 0)^(divisor > 0);

        int ret = 0;
        if (dividend != Integer.MIN_VALUE && divisor != Integer.MIN_VALUE) {
            dividend = Math.abs(dividend);
            divisor = Math.abs(divisor);
            for (int i = 31; i >= 0; i--) {
                if ((dividend >> i) >= divisor) {
                    ret = (ret << 1) + 1;
                    dividend -= (divisor << i);
                } else {
                    ret <<= 1;
                }
            }
        } else {
            if (divisor == Integer.MIN_VALUE) {
                return dividend == Integer.MIN_VALUE? 1: 0;
            }
            if (divisor > 0) {
                divisor = - divisor;
            }            
            for (int i = 31; i >= 0; i--) {
                if ((dividend >> i) <= divisor) {
                    ret = (ret << 1) + 1;
                    dividend -= (divisor << i);
                } else {
                    ret <<= 1;
                }
            }            
        }
        return isNegative? -ret: ret;
    }
}