29. Divide Two Integers

题目：

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

If it is overflow, return MAX_INT.

链接： http://leetcode.com/problems/divide-two-integers/

题解：

最近在按照leetcode序号从小到大做题。刚做完strStr又要做这个，之后还有好几道hard，真的很恶心...不过对自己CS知识技巧和理解力不足的认识又上升到一个新的高度。看到这题首先想到的就是看答案，发现很多答案都使用long来解决溢出，碰到严格的面试官可能会吃亏，自己面微软时就吃过，所以我对自己的要求是 - 即使写得蠢笨，也不可以cheat。

核心是判断符号后使用bit shift以及减法。做题过程中要仔细处理各种corner case。比如:

　　divisor = 0
　　dividend 或者 divisor = Integer.MIN_vALUE
- divisor = Integer.MIN_VALUE
  - if dividend = Integer.MIN_VALUE, return 1
  - return 0
- dividend = Integer.MIN_VALUE
  - if divisor = -1, return Integer.MAX_VALUE
  - if divisor > 0, set divisor = - divisor - calculate everything in the range of negative int

Time Complexity - O(1), Space Complexity - O(1)。

public class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor == 0)                        //corner case:   divisor = 0
            return Integer.MAX_VALUE;
        boolean isNeg = false;                  //get sign of result
        if((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0))
            isNeg = true;
        int res = 0;                            //result
        if(dividend != Integer.MIN_VALUE && divisor != Integer.MIN_VALUE) {
            dividend = Math.abs(dividend);
            divisor = Math.abs(divisor);
            
            for(int i = 0; i < 32; i++) {
                res <<= 1;
                if((dividend >> (31 - i)) >= divisor) {       // shift right dividend and compare if >= divisor
                    dividend -= (divisor << (31 - i));
                    res++;
                }
            }
        } else {                                              
            if(divisor == Integer.MIN_VALUE)
                return dividend == Integer.MIN_VALUE ? 1 : 0;   //corner case: divisor = Integer.MIN_VALUE
            
            if(divisor == -1)                                   //corner case: Integer.MIN_VALUE / -1
                return Integer.MAX_VALUE;
            
            if(divisor > 0)                                     //calculate result in negative integer range
                divisor = -divisor;                         
            
            for(int i = 0; i < 32; i++) {
                res <<= 1;
                if((dividend >> (31 - i)) <= divisor) {         // shift right dividend and compare if <= divisor
                    dividend -= (divisor << (31 - i));
                    res++;
                }
            }    
        }
        
        return isNeg ? -res : res;
    }
}

另外的一个想法由于技术太渣没验证过，来自本科学过的电路知识。在学CRC冗余码时好像学过一种技术叫长除法，可以计算两个binary array相除的结果。可以使用库函数Integer.toBinaryString把两个input int转换为32-bit String，然后利用类似的减，shift，减, shift来得到结果和余数。有机会要验证试试。心得是后悔没学好电子工程...有很多知识和技巧可以和CS结合起来，比如LSD, MSD, 真值表，卡诺图，run-length，Huffman，FFT, DCT, 加法器减法器乘法器除法器等等。在新的领域继续努力吧。

Follow up 可以是不用四则运算符号求加法，减法，乘法和除法。要好好看一看Computer Arithmetic Algorithms

加法：

public int add(int a, int b) {
    while(b != 0) {
        int carry = a & b;      //carry
        a = a ^ b;              //sum
        b = carry << 1;
    }
    
    return a;
}

减法：

pubic int minus(int a, int b) {
    return plus(a, plus(~b, 1));
}

乘法：

也比较麻烦,待补充

除法：

二刷：

Java:

本来尝试优化旧程序，把dividend和divisor全部转化为负数然后计算。结果发现负数的位移操作比较复杂。比如 -5 >> 10 = -1, -5 >> 3 = -1， -5 >> 2 = -2。最小也就是-1了。所以最后还是用老办法来写。希望三刷的时候能够找到这个巧妙规律。

public class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return Integer.MAX_VALUE;
        }
        boolean hasSameSign = (dividend >= 0) ^ (divisor < 0); 
        int res = 0;
        if (dividend != Integer.MIN_VALUE  && divisor != Integer.MIN_VALUE) {
            dividend = Math.abs(dividend);
            divisor = Math.abs(divisor);
            for (int i = 0; i < 32; i++) {
                res <<= 1;
                if ((dividend >> (31 - i)) >= divisor) {
                    dividend -= (divisor << (31 - i));
                    res++;
                }
            }
        } else {
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
            if (divisor == Integer.MIN_VALUE) {
                return dividend == divisor ? 1 : 0;
            }
            if (divisor > 0) {
                divisor = -divisor;
            }
            for (int i = 0; i < 32; i++) {
                res <<= 1;
                if ((dividend >> (31 - i)) <= divisor) {
                    dividend -= (divisor << (31 - i));
                    res++;
                }
            }
        }
        return hasSameSign ? res : -res;
    }
}

三刷:

需要更熟练bit manipulation和比较，以及边界条件。

Java:

public class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0) return Integer.MAX_VALUE;
        if (dividend == 0) return 0;
        boolean hasSameSign = (dividend > 0) ^ (divisor < 0);
        int res = 0;
        if (dividend != Integer.MIN_VALUE && divisor != Integer.MIN_VALUE) {
            dividend = Math.abs(dividend);
            divisor = Math.abs(divisor);
            for (int i = 0; i < 32; i++) {
                res <<= 1;
                if ((dividend >> (31 - i)) >= divisor) {
                    dividend -= (divisor << (31 - i));
                    res++;
                }
            }
        } else {
            if (divisor == Integer.MIN_VALUE) return dividend == divisor ? 1 : 0;
            if (divisor == -1) return Integer.MAX_VALUE;
            if (divisor > 0) divisor = -divisor;
            for (int i = 0; i < 32; i++) {
                res <<= 1;
                if ((dividend >> (31 - i)) <= divisor) {
                    dividend -= (divisor <<(31 - i));
                    res++;
                }
            }
        }
        return hasSameSign ? res : -res;
    }
}

Update:

上面的 res <<= 1这些运算比较晦涩。

其实就是把除法结果变成 2的第i个bit位的减法。就像 15 = 2⁰ + 2¹ + 2² + 2³一样。

注意在dividend = Integer.MIN_VALUE的时候要特殊处理，这时候我们把divisor也变为负的，然后使用类似正数情况下的 shift and minus就可以了。

public class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0) return Integer.MAX_VALUE;
        if (dividend == 0) return 0;
        boolean sameSign = (divisor > 0) ^ (dividend < 0);
        int res = 0;
        if (divisor != Integer.MIN_VALUE && dividend != Integer.MIN_VALUE) {
            divisor = Math.abs(divisor);
            dividend = Math.abs(dividend);
            for (int i = 0; i < 32; i++) {
                if ((dividend >> (31 - i)) >= divisor) {
                    dividend -= (divisor << (31 - i));
                    res += (1 << (31 - i));
                }
            }
        } else {
            if (divisor == Integer.MIN_VALUE) return dividend == Integer.MIN_VALUE ? 1 : 0;
            if (divisor == -1) return Integer.MAX_VALUE;
            if (divisor > 0) divisor = -divisor;
            for (int i = 0; i < 32; i++) {
                if ((dividend >> (31 - i)) <= divisor) {
                    dividend -= (divisor << (31 - i));
                    res += (1 << (31 - i));
                }
            }
        }
        return sameSign ? res : -res;
    }
}

Reference:

https://leetcode.com/discuss/26270/no-use-of-long-java-solution

29. Divide Two Integers

相关推荐