leetcode Question 28: Divide two integers

Divide two integers

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


Analysis:

Note that is the dividend < divisor as they all integer and the return value is also integer, the return value would be 0.  (e.g. 3/4=0)

Without using the *, /, and % operator, what we can use is +,-, and <<, >> .
<< 1 is to multiply 2,e.g. 2<<1  = 4;
>> 1 is to divide 2 e.g.    8>>1 = 4;

Originally, the divide operation can use - only, but this is time-consuming, especially when the dividend is large and the divisor is small. e.g. 123456789/1.

So, use << to speed up.
1. Keep  multiply 2 (<<1) to the divisor, until it is greater than the dividend. Store the times of shift operation.
2. if dividend > divisor, then dividend = dividend - divisor/2(>>1). Until dividend< original divisor. Store the   result.
3. Output the result.

e.g. 13/3

3*2*2*2=24>15,

15 - 24/2 = 3 - 12/2/2=0 < 3, end.
                  res = 4,        res = 4+1,   res=5

Another concern is the negative and positive integer and the range of integer. The pos and neg problem can be solved using abs function and the unsigned type cast. The later one we can use the long long type.

In C++ integer type, from small to large:
short (unsigned)  2 Bytes
int (unsigned)      4 Bytes
long (unsigned)   4 Bytes
long long (unsigned) 8 Bytes






Source code:

class Solution {
public:
    int divide(int dividend, int divisor) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int sign = 1;
        if (dividend<0){sign = -sign;}
        if (divisor<0){sign = -sign;}
        
        unsigned long long tmp = abs((long long)dividend);
        unsigned long long tmp2 = abs((long long)divisor);
               
        unsigned long c = 1;
        while (tmp>tmp2){
            tmp2 = tmp2<<1;    
            c = c<<1;
        }
        
        int res = 0;
        while (tmp>=abs((long long)divisor)){
            while (tmp>=tmp2){
                tmp -= tmp2;
                res = res+c;
            }
            tmp2=tmp2>>1;
            c=c>>1;    
        }
        
        return sign*res;
    }
};