29. Divide Two Integers

Let's see what we should do if we want 3 to divide 18 where 18 is dividend and 3 is divisor.
(1) We subtract 3 from 18 and we get 15. 15 is larger than 3, so we shift 3 to the left by 1 bit and we get 6 which means we have 2 of 3s.
(2) We subtract 6 from 18 again and we get 12. 12 is larger than 6, so we shift 6 to the left by 1 bit again and we get 12 which means we have 4 of 3s.
(3) We subtract 12 from 18 and we get 6. Now 6 is less than 12, so we stop here and add the 4 to the result and subtract 12 from 18 as new dividend and start from 3 again as divisor. Now we go back to step (1) again. At the end, we'll get 2 so the final result is 4+2 = 6.

When implementing, we should be careful about overflow. Since -INT_MIN will be overflowed, so we can't simply flip the sign for dividend or divisor if they are negative, for example at line 6 and 7.
We should either assign dvd by casted long long dividend or do labs(dividend).

1:  class Solution {  
2:  public:  
3:    int divide(int dividend, int divisor) {  
4:      if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;  
5:      int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;  
6:      long long dvd = labs(dividend);  
7:      long long dvs = labs(divisor);  
8:      int res = 0;  
9:      while (dvd >= dvs) {  
10:        long long multiple = 1;  
11:        long long temp = dvs;  
12:        while (dvd >= (temp << 1)) {  
13:          multiple <<= 1;  
14:          temp <<= 1;  
15:        }  
16:        dvd -= temp;  
17:        res += multiple;  
18:      }  
19:      return sign == -1 ? -res : res;  
20:    }  
21:  };