Divide Two Integers

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

If it is overflow, return MAX_INT.

Analysis

• 不可以用*,/,mode，可以用+
• 注意换算成long，不然容易overflow
• 注意sign
• 每次把divisor*2,知道大于dividend，记录乘了多少数
• Example:
  • 16/5: 5x2x2>16,记录divide为2
  • 16-5x2 = 6
  • 6/5: 5x2>6,记录divide为1
  • 答案为所有divide相加 1+2=3

Code

public class Solution {
    public int divide(int dividend, int divisor) {
        long result = divideLong(dividend, divisor);
        return result>Integer.MAX_VALUE?Integer.MAX_VALUE:(int)result;
    }

    private long divideLong(long dividend, long divisor){
        boolean sign = dividend < 0 != divisor < 0;

        if(dividend<0){dividend = - dividend;}
        if(divisor<0){divisor = -divisor;}

        if(dividend<divisor) {return 0;}

        long sum = divisor;
        long divide = 1;
        while((sum+sum) <= dividend){
            sum += sum;
            divide += divide;
        }

        return sign ? -(divide+divideLong((dividend-sum),divisor)):(divide+divideLong((dividend-sum), divisor));
    }
}

Reference

Leetcode