Leetcode(29) Divide Two Integers

发表于 | 更新于 | 分类于

Description:

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:

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

解法：

除法可以采用减法实现，未避免减法次数过多，采用二分法可减少运算次数。 不难想到用除数的2^31,2^30,…,2^2,2^1,2^0倍尝试去减被除数，如果减得动，则把相应的倍数加到商中；如果减不动，则依次尝试更小的倍数。这样就可以快速逼近最终的结果。 2的i次方其实就相当于左移i位，为什么从31位开始呢？因为int型数据最大值就是2^31啊。 注：左移x位相当于乘2的x次方，右移x位相当于除2的x次方 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) return Integer.MAX_VALUE;
        long a = dividend > 0 ? dividend : -(long) dividend;
        long b = divisor > 0 ? divisor : -(long) divisor;
        if (b == 1) {
            return divisor == 1 ? dividend : -dividend;
        }
        int result = 0;
        for (int i = 31; i >= 0; i--) {
            if ((a >> i) >= b) {
                result += (1 << i);
                a = a - (b << i);
            }
        }
        if ((dividend ^ divisor) < 0) {
            result = -result;
        }
        return result;
    }
}