Divide Two Integers

Description

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

If it is overflow, return2147483647

Example

Given dividend = 100 and divisor = 9, return 11.

Related problems

Plus One

Easy Add Binary

Implementation

Link: http://lintcode.com/en/problem/strstr/

class Solution {
public:
    /**
     * @param dividend the dividend
     * @param divisor the divisor
     * @return the result
     */
    int divide(int dividend, int divisor) {
        // Write your code here
       if (divisor == 0) {
             return INT_MAX;
        }

        if (dividend == 0) {
            return 0;
        }

        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }

        int sign = (dividend < 0) ? -1 : 1;
        sign = sign * ( (divisor < 0) ? -1 : 1);

        long a = abs((long)dividend);
        long b = abs((long)divisor);
        int result = 0;

        while(a >= b){
            int shift = 0;

            while(a >= b << shift){
                shift++;
            }

            a -= (b << (shift - 1));
            result += (1 << (shift - 1));

        }

        return sign < 0 ? -result: result;
    }
};