Divide Two Integers

Divide Two Integers

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

If it is overflow, return MAX_INT.

-------------------------------------- thinking -------------------------------------------
we always need to pay attention to corner cases:

[0xFFFFFFFF, ox8000000] which is [-2147****, -1]

-------------------------------------- codes -----------------------------------------------
class Solution {
   public:
       int divide(int dividend, int divisor) {
           if (divisor == 0) {
               return INT_MAX;
           }
           int sign = false;
           //bug here -> we should force the type to be long long, or (oxFFFFFFFF) will over flow
           long long d1 = dividend;
           long long d2 = divisor;
           if (dividend < 0) {
               sign = !sign;
               d1 = ~d1 + 1;
           }
           if (divisor < 0) {
               sign = !sign;
               d2 = ~d2 + 1;
           }

           if (d1 < d2) {
               return 0;
           }
           int result = 0;
           long long cur_bit = 1;
           while (d2 <= d1) {
               d2 = d2 << 1;
               cur_bit <<= 1;
           }
           d2 >>= 1;
           cur_bit >>= 1;
           while (d1 > 0 && cur_bit > 0) {
               if (d1 >= d2) {
                   result |= cur_bit;
                   d1 = d1 - d2;
               }
               cur_bit >>= 1;
               d2 >>= 1;              
           }
           if (sign) {
               int out = result;
               out = ~out + 1;
               return out;
           } else {
               //bug here -> it is possible that the result is 0xFFFFFFFF, if there is no sign, then the result will over flow
               if (result == INT_MIN) {
                   return INT_MAX;
               } else {
                   return result;
               }
           }
       }
   };