Monday, November 25, 2013

Day 54 # 29, Divide Two Integers

Divide Two Integers
Divide two integers without using multiplication, division and mod operator. 
-----------------------------------------------------------------
keep multiplying divisor by 2 until divisor is larger than dividend, then divide it by 2
compute the difference between divisor and dividend, set it as the new dividend


class Solution {
public:
    int divide(int dividend, int divisor) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        
        long long a = abs((double)dividend);;
        long long b = abs((double)divisor);
        int sign = 1;
        if (dividend < 0) sign *= -1; 
        if (divisor < 0) sign *= -1; 
        
        int total = 0; 
        while (a >= b) {
            long long c = b;
            int count = 1;
            while (a >= (c<<1)) {
                c = c << 1;
                count = count << 1;
            }
            a = a - c;
            total += count;
        }
        return total*sign;
    }
};

Java, updated on Aug-6th-2018
原来同上,就是不断的对以下数组里的数进行循环相减,然后更新被除数
[divisor * 2, divisor * 2 ^ 2, divisor * 2 ^ 3, divisor * 2 ^ 4 ...]
注意处理溢出

class Solution {
    public int divide(int dividendInt, int divisorInt) {
        
        long dividend = Math.abs((long)dividendInt);
        long divisor = Math.abs((long)divisorInt);
        
        int sign = 1;
        if (dividendInt < 0) sign *= -1;
        if (divisorInt < 0) sign *= -1;
        
        long count = 0;
        while (dividend >= divisor) {
            int tempCount = 1;
            long tempDivisor = divisor;
            while ((tempDivisor << 1) < dividend) {
                tempCount <<= 1;
                tempDivisor <<= 1;
            }
            
            dividend -= tempDivisor;
            count += tempCount;
        }
        
        if (count > Integer.MAX_VALUE) {
            if (sign == 1) return Integer.MAX_VALUE;
            return Integer.MIN_VALUE; 
        }
        
        return (int) count * sign;
    }
}

No comments:

Post a Comment