Divide Two Integers

Description

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

If it is overflow, return 2147483647 (INT_32MAX)

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

Link

Lintcode_ladder

Method

1. Binary Search, find the range of xxx>= dividend >= xxx
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param dividend the dividend
     * @param divisor the divisor
     * @return the result
     */
    int divide(int dividend, int divisor) {
        // Write your code here
        // unit the sign
        long long a = dividend >= 0 ? dividend : -(long long)dividend;
        long long b = divisor >= 0 ? divisor : -(long long)divisor;
        long long result = 0;
        long long shift  = 31;
        // first: find the first  b * 2^shift < a
        // second: get the a =a - b * 2^shift
        // then repeat: test the rest by b * 2^(shift-1) < a
        while (shift >= 0) {
            // when b * 2^shift < a
            // a = rest 
            // result = 2^shift
            if (a >= b << shift) {
                a -= b << shift;
                // 1LL = (long long) 1
                //result += 1LL << shift;
                result += (long long)0x01 << shift;
                // below may cause 0x1000000... means MIN_32INT
                //result += 0x01 << shift;
            }
            shift--;
        }
        // ((dividend ^ divisor) >> 31) get the sign digit
        result = ((dividend ^ divisor) >> 31) ? -result : result;
        if (result > INT32_MAX) {
            return INT32_MAX;
        }
        return result;
    }
};

Similar problems

x

Tags

x