Divide Two Integers

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

Naive Way:通常不让用这些数学运算符都是在指向比特运算符。除以2，4，8就好办了，可以通过移位实现，除以3怎么办呢。可不可以从结果开始想，除以3相当于先把结果左移1位(2)，再加上他自己(1)。那么除以7就相当于找到一个数左移2位，左移1位，左移0位之和为除数。如果不能整除，就是除数在（左移2位，左移1位，左移0位之和）和（左移2位，左移1位，左移1位之和）之间。好像可以用一个recursive的方法，每次都找都最高位的商，剩下的交给下一级recursive call。

还有负数，真是烦。因为Integer.MIN_VALUE没有对应的正数，写的时候特别麻烦。不能先全转成正数，于是我就打算全用负数做。

最后的最后，终于是全通过了，并且迫于无奈只能将dividend = Integer.MIN_VALUE, divisor = -1这个case单独列出了，因为它使唯一一个会超出表示范围的数。

复杂度上并没有使用binary search 找当前位，尝试过，很难，尤其是负数。 边界由
divisor << cur < 0 && cur < 31 控制，第一个是要保持负数形式，唯一一个例外就是Integer.MIN_VALUE除以1的时候，因为没有上限，-1移位成Integer.MIN_VALUE时下一个就只会移0位，因为java不让左移33位，会变回左移1位，所以有了第二个条件 cur <31。

 public class Solution {  
   public int divide(int dividend, int divisor) {  
     if(dividend==Integer.MIN_VALUE && divisor==-1) return Integer.MAX_VALUE;  
     if(dividend > 0 && divisor > 0) return divideHelper(-dividend, -divisor);  
     else if(dividend > 0) return -divideHelper(-dividend,divisor);  
     else if(divisor > 0) return -divideHelper(dividend,-divisor);  
     else return divideHelper(dividend, divisor);  
   }  
   private int divideHelper(int dividend, int divisor){  
     // base case  
     if(divisor < dividend) return 0;  
     // get highest digit of divisor  
     int cur = 0, res = 0;  
     while((divisor << cur) >= dividend && divisor << cur < 0 && cur < 31) cur++;  
     res = dividend - (divisor << cur-1);  
     if(res > divisor) return 1 << cur-1;  
     return (1 << cur-1)+divide(res, divisor);  
   }  
 }   

Improved Way:看到Discuss里大部分人都是用long做的，有人就问，如果让你divide的是两个long呢。long的做法完全可以用正数做了。我觉得应该能使用Binary search提高效率。记住要补上！