29. Divide Two Integers

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

Return the quotient after dividingdividendbydivisor.

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: [−2 ^31, 2^31− 1]. For the purpose of this problem, assume that your function returns 2^31− 1 when the division result overflows.

Thoughts: Convert the definition of division to subtraction: iteratively shifting the divisor until it cannot be shifted to still be smaller or equal to the dividend. Subtract dividend from the subtractor and the shifted number to the current result. Repeat until the final dividend is the reminder (less than divisor)

Code:

class Solution {
public:
    int divide(int dividend, int divisor) {
        // 1. divisor = 0; 2. dividend = INT_MIN && divisor = -1
        if(!divisor || dividend == INT_MIN && divisor == -1) return INT_MAX;
        int sign = ((dividend < 0) ^ (divisor < 0))? -1: 1;

        long long dvd = labs(dividend), dvs = labs(divisor);
        int res = 0;
        while(dvd >= dvs){
            long long subtractor = dvs, multiplicand = 1;
            while(dvd >= (subtractor << 1)){
                subtractor <<= 1;
                multiplicand <<= 1;
            }

            dvd -= subtractor;
            res += multiplicand;
        }

        return sign == 1? res: -res;
    }
};