Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

class Solution {
public:
    int binary_helper(int dividend, int divisor) {
        long divd = abs((long)dividend);
        long div = abs((long)divisor);
        int ans = 0;
        while (true) {
            int partial_ans = 0;
            long new_div = div;
            if (divd == div) {
                return ans + 1;
            } else if (divd < div) {
                return ans;
            }
            while(true) {
                if ((new_div << 1) > divd) {
                    break;
                }
                new_div <<= 1;
                partial_ans++;
            }
            if (partial_ans == 0) {
                ans += 1;
                break;
            }
            divd -= new_div;
            ans += (1 << partial_ans);
        }
        return ans;
    }
 
    int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return INT_MAX;
        }
             
        if (dividend == INT_MIN) {
            if (divisor == 1) {
                return INT_MIN;
            } else if (divisor == -1) {
                return INT_MAX;
            }
        }

        int sign_a = (dividend < 0 ? -1 : 1);
        int sign_b = (divisor < 0 ? -1 : 1);

        //int ans = linear_helper(dividend, divisor);
        int ans = binary_helper(dividend, divisor);
        return ans * sign_a * sign_b;
    }
 
    long linear_helper(int dividend, int divisor) {
        long divd = abs((long)dividend);
        long div = abs((long)divisor);
        long count = 0;
        while (divd >= div) {
            count++;
            divd -= div;
        }
        return count;
    }
};




============== Cleaner one ===========

public int divide(int dividend, int divisor) {
    //handle special cases
    if(divisor==0) return Integer.MAX_VALUE;
    if(divisor==-1 && dividend == Integer.MIN_VALUE)
        return Integer.MAX_VALUE;
 
    //get positive values
    long pDividend = Math.abs((long)dividend);
    long pDivisor = Math.abs((long)divisor);
 
    int result = 0;
    while(pDividend>=pDivisor){
        //calculate number of left shifts
        int numShift = 0;    
        while(pDividend>=(pDivisor<<numShift)){
            numShift++;
        }
 
        //dividend minus the largest shifted divisor
        result += 1<<(numShift-1);
        pDividend -= (pDivisor<<(numShift-1));
    }
 
    if((dividend>0 && divisor>0) || (dividend<0 && divisor<0)){
        return result;
    }else{
        return -result;
    }
}

============= Another ======

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        int sign = 1;
        if (dividend < 0) {
            sign *= -1;
        }
        if (divisor < 0) {
            sign *= -1;
        }
        // return sign;
        if (dividend == 0 || divisor == 0) {
            return 0;
        }
        
        long temp = labs(dividend);
        long tempDiv = labs(divisor);
        if (temp == tempDiv) {
            return sign;
        }
        
        long ans = 0;
        while (temp != 0) {
            int k = 0;
            while ((tempDiv << k) <= temp) {
                k++;
            }
            if (k == 0) {
                return sign * ans;
            }
            ans += (1 << (k - 1));
            temp -= (tempDiv << (k - 1));
        }
        return  sign == 1 ? ans : -ans;
    }
};