Qi

Cogito ergo sum

0%

leetcode 29 Solution

发表于 更新于 分类于 487 2 分钟

代码解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package com.demo.s29;

/**
 * 两数相除
 * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 *
 * 返回被除数 dividend 除以除数 divisor 得到的商。
 *
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/divide-two-integers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int divide(int dividend, int divisor) {

        if (dividend == -2147483648 && divisor == -1) return 2147483647;
        if (dividend == 2147483647 && divisor == 1) return 2147483647;
        // 对两种特殊情况的快速处理，大概算是偷鸡了吧
        int result = 0;
        boolean isNeg = (dividend < 0 ^ divisor < 0); // 异或运算确定结果正负性
        dividend = -Math.abs(dividend);
        divisor = -Math.abs(divisor);
        // 使用绝对值再取负，全部转化为负数进行运算
        // 特别的，在int范围内，-2147483648的正负数都是其自身，因此不会出错
        while (dividend <= divisor) {
            int d = divisor; // d为本轮所用的除数
            int cnt = 1; // cnt表示d为原除数的cnt倍
            while (dividend <= d && d >= -1073741824) {
                // 每次对d和cnt都进行翻倍，快速到达大于被除数的最小除数
                // 等效d=d*2，但题目禁用乘法，且位运算左移速度更快
                d = d << 1;
                cnt = cnt << 1;
            }
            // 当 dividend > d 时，表明此时d已经小于被除数了，不能继续
            // 当 d < -1073741824 时，表明此时d再翻倍会造成溢出，不能继续

            if (dividend <= d) {
                // 此时说明上一步d再翻倍会造成溢出
                // 可知d已经是大于被除数的最小除数，直接使用即可
                dividend -= d;
                result += cnt;
            } else {
                // 此时d是小于被除数的最大除数，需要右移补回一次
                // 才能成为大于被除数的最小除数，再进行使用
                dividend -= d >> 1;
                result += cnt >> 1;
            }
        }
        return isNeg ? -result : result;
        // result为所有倍数的和，需要补充正负性再返回

    }
}