【leetcode】Divide Two Integers

Question ：

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

Anwser 1 ：

class Solution {
public:
    int divide(int dividend, int divisor) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int ret = 0;
        
        if(dividend == 0 || divisor == 0) return 0;
        
        int sign = 1;   // 1 : positive; -1 : negative
        if(dividend < 0) sign *= -1;
        if(divisor < 0) sign *= -1;
        
        long long tmpDiv = dividend;
        long long divL = abs(tmpDiv);
        long long tmpDivisor = divisor;
        long long divisorL = abs(tmpDivisor);
        
        while(divL >= divisorL){
            int count = 1;              // first: divL > divisorL 
            long long sum = divisorL;   // long long, cal divisorL
            while(sum + sum <= divL){
                count += count;
                sum += sum;
            }
            divL -= sum;
            ret += count;
        }
        
        return sign * ret;
    }
};

注意点：

1） 原理：累加除数，判断是否大于被除数

2） 设置符号位sign，判断符号

3） 对dividend和divisor都先转化成long long类型，防止负数转化成正整数时溢出

4） 除数之和sum，必须设置成long long，防止溢出（同2）

Anwser 2 ：

class Solution {
public:
    int divide(int dividend, int divisor) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        long long a = dividend;
        long long b = divisor;
        
        int sign = 1;
        if(a < 0){
            a = -a;
            sign *= -1;
        }
        
        if(b < 0){
            b = -b;
            sign *= -1;
        }
        
        int d = 0;
        while ( (b << d) <= a )
        {
            ++d;
        }
        
        --d;
        
        int res = 0;
        for (int i = d; i >= 0; --i) {
            if ( (b << i) <= a ) {
                res += (1 << i);    // high to low
                a -= (b << i);      // remaider
            }
        }

        return sign * res;
    }
};

Anwser 3：

class Solution {
 private:
     long long f[100];
 public:
     int bsearch(long long a[], int left, int right, long long key)
     {
         if (left > right)
             return -1;
             
         int mid = left + (right - left) / 2;
         if (a[mid] == key)
             return mid;
         else if (a[mid] < key)
         {
             int pos = bsearch(a, mid + 1, right, key);
             return pos == -1 ? mid : pos;
         }
         else
         {
             return bsearch(a, left, mid - 1, key);
         }
     }
     
     int divide(int dividend, int divisor) {
         // Start typing your C/C++ solution below
         // DO NOT write int main() function
         int sign = dividend < 0 ? -1 : 1;
         if (divisor < 0)
             sign *= -1;
         
         long long div = dividend;
         div = abs(div);
         long long divisorL = divisor;
         divisorL = abs(divisorL);
         f[0] = divisorL;
         int size = 1;
         while(true)
         {
             if (f[size-1] >= div)
                 break;
             f[size] = f[size-1] + f[size-1];
             size++;
         }
         
         int num = 0;
         long long sum = 0;
         while(div > 0)
         {
             int pos = bsearch(f, 0, size - 1, div);
             if (pos == -1)
                 break;
             div -= f[pos];
             num += (1 << pos);
         }
                 
         return num * sign;
     }
 };