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

If it is overflow, return 2147483647

 

Example

Given dividend = 100 and divisor = 9, return 11.

 

基本思想就是把除数向左移位(×2)然后与被除数比较，直到发现恰好仅次于被除数的那个值，减去该值后递归继续。

除法的答案就是每次得到shift位移后把1向左移位同样的距离，加起来。（除数向左移位，相当于（除数*1）向左移位，相当于除数*（1向左移位））。

1.这题细节非常多，主要在正负计算，计算过程int越界，答案本身int越界，除数为0的问题。数值处理的题目这几个都很重要。

2.处理越界一个简单的方法是转化为long来计算，切记这个常用方法！不过这道题最负数和-1还是不能这样解决，因为最后输出定死了int，所以这个case不能解决，要if做。

3.negative的处理学学样例，isNegative是布尔类型，直接赋值即可不要if。最后返回的时候可以用？符号来简单处理。

4.int 转 long得这样写：long a = Math.abs((long)dividend); 里面的long不加的话 -2...8会变不了正的，因为Math.abs(int)函数当输入-2...8时输出-2...8。

5. << 优先级比 <, == 高，所以可以写divisor << shift < dividend 这种。

 

样例代码：

/**     * 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。     * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。     * - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，     * - Big Data 项目实战班，算法面试高频题班, 动态规划专题班     * - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code     */ public class Solution {    /**     * @param dividend the dividend     * @param divisor the divisor     * @return the result     */    public int divide(int dividend, int divisor) {        if (divisor == 0) {             return dividend >= 0? Integer.MAX_VALUE : Integer.MIN_VALUE;        }                if (dividend == 0) {            return 0;        }                if (dividend == Integer.MIN_VALUE && divisor == -1) {            return Integer.MAX_VALUE;        }                boolean isNegative = (dividend < 0 && divisor > 0) ||                              (dividend > 0 && divisor < 0);                                     long a = Math.abs((long)dividend);        long b = Math.abs((long)divisor);        int result = 0;        while(a >= b){            int shift = 0;            while(a >= (b << shift)){                shift++;            }            a -= b << (shift - 1);            result += 1 << (shift - 1);        }        return isNegative? -result: result;    }}

 

自己写的：

public class Solution {    /*     * @param dividend: the dividend     * @param divisor: the divisor     * @return: the result     */    public int divide(int dividend, int divisor) {        // ！！！处理溢出        if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1){            return Integer.MAX_VALUE;        }                if (dividend == Integer.MIN_VALUE && divisor == 1){            return Integer.MIN_VALUE;        }        // ！！！处理负数        boolean isNegative = false;        if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0){            isNegative = true;        }        long dividendL = Math.abs((long)dividend);        long divisorL = Math.abs((long)divisor);                int result = 0;        long sum = 0;        int currentIdx = findIdx(dividendL, divisorL);        while (currentIdx >= 0){            result += 1 << currentIdx;            sum += divisorL << currentIdx;            currentIdx = findIdx(dividendL - sum, divisorL);        }        return isNegative? -result : result;    }    // return the exact index n so divisor * 2^n <= dividend < divisor * 2^(n + 1).    // if dividend < divisor, return -1.    private int findIdx(long dividend, long divisor){        int index = 0;        while ((divisor << index) <= dividend){            index++;        }        index--;        return index;    }}