Divide Two Integers

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

这道题的想法是,既然不能用除法,就用减法。
但是一个一个减太慢,我们可以每次减divisor以后,如果dividend剩下的值比divisor大,那么divisor << 2 (相当于*2),然后再减,加快这个过程,如果divisor比dividend剩下的值大了,那么我们将divisor恢复到最初的divisor,再继续上面的过程,直到dividend剩下的比divisor小为止(这个数就是余数了,不过这道题中我们不care)

最后注意用abs函数的时候要用long,以免溢出。

public class Solution {
    public int divide(int dividend, int divisor) {
        int count = 0;
        int shift = 1;
        //long base = divisor;
        boolean sign = false; //positive 
        if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0 ))
            sign = true;
        long divd = Math.abs((long)dividend);
        long divs = Math.abs((long)divisor);
        long base = divs;
        while(divd >= base) {
            while (divd >= base) {
                divd -= base;
                count += shift;
                base = base << 1; //base *2 to speed up the calculation
                shift = shift << 1;
            }
            base = divs;
            shift = 1;
        }
        return sign?-1*count:count;
    }
}
public class Solution {
    public int divide(int dividend, int divisor) {
        boolean sign = ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0));
        long op1 = Math.abs((long)dividend); // need to cast long before use abs, otherwise wrong result because of overflow
        long op2 = Math.abs((long)divisor);
        long left = op1;
        long test = op2;
        int count = 0;
        int base = 1;
        while(left >= op2) { // include == for mod is 0
            test = test << 1;
            base = base << 1;
            if(test > left) { // test if we are trying a number too big that exceeds the top
                test = op2;
                base = 1;
            }
            left -= test;
            count += base;
        }
        return sign? (~count + 1) : count;
    }
}

Use a base to calculate the number of doubles of the divisor instead of the divisor itself


public class Solution {
    public int divide(int dividend, int divisor) {
        boolean sign = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0);
        long divid = Math.abs((long)dividend);
        long divis = Math.abs((long)divisor);
        if (divid == 0 || divid < divis)
            return 0;
        long left = divid - divis;
        long res = 1;
        int base = 1;
        while(left >= divis) {
            //try to double divisor
            if (left > divis * base * 2) {
                left -= divis * base * 2;
                res += base * 2;
                base *= 2;
            }
            else {
                base = 1;
                left -= divis;
                res++;
            }
        }
        return sign? (int)res : -1 * (int)res;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s