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.

分析：

这本身并不难，难的是里面有很多想不到的test case。比如：

a = -2147483648 && b = -1， 应该返回 2147483647

a = -2147483648 && b = 2  应该返回1073741824

1 public class Solution { 2     /** 3      * @param dividend the dividend 4      * @param divisor the divisor 5      * @return the result 6      */ 7     public int divide(int a, int b) { 8          9         if (b == 0 || (a == -2147483648 && b == -1)) return 2147483647;10         if (b == 1) return a;11         if (b == -1) return 0 - a;12         13         int count = 0;14         for(long i = abs(a); i >= abs(b); i -= abs(b)) {15             count++;16         }17 18         if (positive(a, b) == true) 19             return count;20         else 21             return 0 - count;22     }23     24     public boolean positive(int a, int b) {  25         if ((a > 0 && b > 0) || (a < 0 && b < 0)) 26             return true;  27         else 28             return false;  29     }  30     31     public long abs(long value) {  32         if (value >= 0 ) 33             return value;  34         else 35             return 0 - value;  36     }37 }

 在leetcode里进行测试，发现超时。这题的终极解法应该是用bit operators.  原理是快速找出最大的以divisor为底数的值，当然这值必须要小于dividend。假设那个值是K， 那么我们可以确定。 dividend / divisor =  K / divisor + (dividend - K) / divisor.

如何快速找出最大的以divisor为底数的值呢，用 << Operator.

1 public class Solution { 2     /** 3      * @param dividend the dividend 4      * @param divisor the divisor 5      * @return the result 6      */ 7     public int divide(int dividend, int divisor) { 8         if (divisor == 0) { 9              return dividend >= 0? Integer.MAX_VALUE : Integer.MIN_VALUE;10         }11         12         if (dividend == 0) {13             return 0;14         }15         16         if (dividend == Integer.MIN_VALUE && divisor == -1) {17             return Integer.MAX_VALUE;18         }19         20         boolean isNegative = (dividend < 0 && divisor > 0) || 21                              (dividend > 0 && divisor < 0);22                              23         long a = Math.abs((long)dividend);24         long b = Math.abs((long)divisor);25         int result = 0;26         while(a >= b){27             int shift = 0;28             while(a >= (b << shift)){29                 shift++;30             }31             a -= b << (shift - 1);  //剩余部分32             result += 1 << (shift - 1); // 1 << (shift - 1) = (b << (shift - 1)) / b33         }34         return isNegative? -result: result;35     }36 }

Reference:

http://www.jiuzhang.com/solutions/divide-two-integers/