[LeetCode] 29. Divide Two Integers

Posted on | In

Problem

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:

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

Example 2:

1
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 231 − 1 when the division result overflows.

Explanation

  1. We can use bit operation to solve this problem.

  2. Initialize res = 0. While divident is greater or equal than the divisor, we left shift the divisor. Each time we left shift the divisor, we multiple by 2 and add to the res. For example, if the divident is 32 and divisor is 3. Left shift one time, divisor becomes 6; left shift two time, it becomes 12; left shift three times, it becomes 24; left shift four times, it becomes 48. Now the divisor is greater than the divident, so we need left shift 3 times to keep the divisor less than divident, and the res = 2^3=8. If we left shift 3 times, the divisor is 24, we use divident subtract it, we get the new divident = 32-24 = 8. Repeat the same step with divident=8 and divisor=3. Now, we can only left shift 1 times since 3*2=6<8, and res will be 2^1=2, so we get res = 8+2 = 10.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        long dividendA = Math.abs((long)dividend);
        long divisorA = Math.abs((long)divisor);
        int res = 0;
        while (dividendA >= divisorA) {
            int numShift = 0;
            while (dividendA >= divisorA<<numShift) {
                numShift++;
            }
            res += 1<<(numShift-1);
            dividendA -= divisorA<<(numShift-1);
        }
        if ((dividend < 0 && divisor < 0) || (dividend > 0 && divisor > 0)) return res;
        return -res;
    }
}