Divide Two Integers

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

If it is overflow, return MAX_INT.

tags: math, binary search

8/10/2015 update

Reference http://yucoding.blogspot.com/2013/01/leetcode-question-28-divide-two-integers.html

class Solution {
public:
    int divide(int dividend, int divisor) {
        int flag = 1;
        long ldividend = dividend;
        long ldivisor = divisor;
        if(ldividend < 0){
            ldividend = -ldividend;
            flag *= -1;
        }
        if(ldivisor < 0){
            ldivisor *= -1;
            flag *= -1;
        }
        long quotient = 0;
        while(ldividend >= ldivisor){
            long thisQuotient = 1;
            long d = ldivisor;
            while(d <= ldividend){
                d = d << 1;
                thisQuotient = thisQuotient << 1;
            }
            d = d >> 1;
            thisQuotient = thisQuotient >> 1;
            ldividend -= d;
            quotient += thisQuotient;
        }
        quotient *= flag;
        if(quotient == (long)0x80000000){
            return 0x7fffffff;
        }
        else{
            return quotient;
        }
    }
};

tag中的binarysearch应该值在移位dividend时，通过比较reminder和divisor的大小决定给quotient赋值1还是0.

实际上，通过二分查找整个32位int的空间，仅需32次二分查找操作。

需要注意的是：按位与(&)的优先级小于逻辑等于(==)，所以要在&加上括号以保证正确的运算顺序。

class Solution {
public:
    int divide(int dividend, int divisor) {
        int flag = 1;
        int overflow = 0;
        if(divisor == 0){
            return INT_MAX;
        }
        if(dividend == 0x80000000){// minimal 32-bit integer
            if(divisor == -1){
                return INT_MAX;//overflow
            }
            else{
                dividend = 0x7FFFFFFF;
                overflow = 1;
                flag *= -1;
            }
        }
        else if(dividend < 0){
            dividend *= -1;
            flag *= -1;
        }
        if(divisor == 0x80000000){// minimal 32-bit integer
            if(dividend == 0x7FFFFFFF && overflow == 1){
                return 1; // 0x80000000 / 0x80000000
            }
            else{
                return 0;//any other 32-bit integers divided by 0x80000000 would be 0
            }
        }
        else if(divisor < 0){
            divisor *= -1;
            flag *= -1;
        }
        
        //article begin
        int bit = 0x40000000;
        int reminder = 0;
        int quotient = 0;
        while(bit > 0){
            reminder = reminder << 1;
            if((bit & dividend) > 0){//parenthese is IMPORTANT!
                reminder += 1;
            }
            bit = bit >> 1;
            if(reminder >= divisor){
                reminder -= divisor;
                quotient = quotient << 1;
                quotient += 1;
            }
            else{
                quotient = quotient << 1;
            }
        }
        
        //deal with overflow and flag
        reminder += overflow;
        if(reminder >= divisor){
            quotient += 1;//no need to shift
        }
        quotient *= flag;
        return quotient;
    }
};