29. Divide Two Integers

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

If it is overflow, return MAX_INT.

那么如果每次不仅仅减去1个除数，计算速度就会增加，但是题目不能使用乘法，因此不能减去k*除数，我们可以对除数进行左移位操作，这样每次相当于减去2^k个除数，如何确定k呢，只要使 (2^k)*除数 <=  当前被除数 <(2^(k+1))*除数.

class Solution {
public:
  int divide(int dividend, int divisor) {
    long long ddd = dividend;
    long long dvr = divisor;
    ddd = abs(ddd);
    dvr = abs(dvr);
    long long res = 0;
    while (ddd >= dvr){
      long long tmp = dvr;
      unsigned int i = 0;
      while (tmp <= ddd){
        tmp <<= 1;
        i++;
      }
      res += ((unsigned)1 << (i - 1));
      ddd -= (dvr << (i - 1));
    }
    return (dividend < 0 ^ divisor < 0) ? -res:(res>INT_MAX ? INT_MAX : res);
  }
};