整数除法

  • 原题链接：https://leetcode.cn/problems/xoh6Oh/
  • 编程语言可能会提供占据不同内存空间的整数类型，每种类型能表示的整数范围不同，
  • 无符号整数无论二进制表示的最高位是0还是1，其都表示一个正数，32位整数的范围为 ~ 。由于整数范围的限制，如果计算结果超出了范围，就会产生溢出。产生溢出时运行不会出错，但是计算结果可能会出乎意料。

1.减法

主要思路：为了求得dividend/divisor，可以不断的从dividend里减去divisor，当不能再减去更多的divisor时，循环执行的次数就是商

存在问题：

  1. 当除数很大时，减法操作执行的次数就会很多，导致程序超时，如
  2. 没有考虑除数与被除数，在32位int数据类型的范围溢出问题
  3. 没有考虑除法结果，在32位int数据类型的范围溢出问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int divide(int dividend, int divisor) {
        int flag = 0;
        int count = 0;
        if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) flag = 1;
        dividend = abs(dividend);
        divisor = abs(divisor);
        while (dividend - divisor >= 0) {
            dividend -= divisor;
            count++;
        }
        if (flag) count = -count;
        return count;
    }
};

2.减法的优化

主要思路：

  1. 当被除数大于除数时，继续比较判断被除数是否大于除数的2倍，如果是则继续判断是否大于除数的4倍、8倍、… 倍，

  2. 如果被除数最多大于除数的 倍，则将被除数减去除数的 倍，然后将剩余的被除数重复前面的步骤（由于每次除数翻倍，因此优化后的时间复杂度为 ）

  3. 除数与被除数范围溢出问题：如果将 转为正数则会导致溢出，故可以先将正数都全部转为负数，计算得到结果后再定符号

  4. 结果范围溢出问题：由于是整数的除法且除数不为0，因此商的绝对值一定小于等于除数的绝对值，

    因此结果溢出只有一种情况，即 结果为 超出正数的范围

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
56
//写法1: 将divide函数与divideCore函数合并（时间复杂度高、空间复杂度低）
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend == INT_MIN && divisor == -1) return INT_MAX;//除法结果溢出的处理
        int flag = 0;
        unsigned int count = 0;
        if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) flag = 1;
        //除数与被除数转为负数防止溢出
        if (dividend > 0) dividend = -dividend;
        if (divisor > 0) divisor = -divisor;
        
        while (dividend <= divisor) {//不可使用dividend - divisor <= 0否则发生溢出错误
            int temp = divisor;
            unsigned int quotient = 1;
            while (temp >= 0xc0000000 && dividend <= temp + temp) {
                quotient += quotient;
                temp += temp;
            }
            dividend -= temp;
            count += quotient;
        }

        return flag ? -count : count;
    }
};
//写法2: 将divide函数与divideCore函数分开（时间复杂度低、空间复杂度高）
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend == INT_MIN && divisor == -1) return INT_MAX;//除法结果溢出的处理
        int flag = 0;
        if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) flag = 1;
        //除数与被除数转为负数防止溢出
        if (dividend > 0) dividend = -dividend;
        if (divisor > 0) divisor = -divisor;
        
        unsigned int res = divideCore(dividend, divisor);
        return flag ? -res : res;
    }

    int divideCore(int dividend, int divisor) {
        int res = 0;
        while (dividend <= divisor) {//不可使用dividend - divisor <= 0否则发生溢出错误
            int temp = divisor;
            unsigned int quotient = 1;//int + int 超出范围 int范围
            while (temp >= 0xc0000000 && dividend <= temp + temp) {
                quotient += quotient;
                temp += temp;
            }
            res += quotient;
            dividend -= temp;
        }
        return res;
    }
};

3.位运算

  • num << 1 = num * 2
  • 1 << n = 2 ^ n

image-20230408110233386.png

比如这个例子是解64/3的商，实质上就是问64里有几个3。

如果用常规的减法，就是在64里，1个3，2个3 … n个3，这样找。

那如果是按照位运算呢，就是1个3，2个3，4个3，8个3，以2的n次方这样找

但是，被除数不一定是整的2的n次方个3。就想例子中，maxShift = 4，那其实64是大于2的4次方个3，但是小于2个5次方个3。这个时候我们再去细化64减去 个3的差，看看差里还有几个3。

当然这个过程也和上述的类似，在 里找，16可以有个 个3，剩下4，而4里可以有个 个3，最后把这 都加起来，就是21

出现问题：C++不支持负数的左移运算符

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//C++代码不支持左移运算 程序暂时有问题，之后再来排查
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend == INT_MIN && divisor == -1) return INT_MAX;//除法结果溢出的处理
        // 特殊情况，无需计算，直接返回
        if (dividend == 0 || divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return -dividend;
        }

        int flag = 0;
        if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) flag = 1;
        //除数与被除数转为负数防止溢出
        if (dividend > 0) dividend = -dividend;
        if (divisor > 0) divisor = -divisor;

        unsigned int res = divideCore(dividend, divisor);
        return flag ? -res : res;
    }

    int divideCore(int dividend, unsigned int divisor) {
        // 被除数 == 除数，直接返回结果为 1
        if (dividend == divisor) {
            return 1;
        }
        // 开始正式计算
        unsigned int result = 0;
        int shift = getMaxShift(divisor, dividend);

        while (dividend <= divisor) {
            while (dividend > (divisor << shift)) shift--;
            dividend -= (divisor << shift);
            result += (1 << shift);
        }
        return result;
    }

    int getMaxShift(int num, int min) {
        // num 是除数，min 是被除数，希望找到 num << shift < min 时，shift 的最大值
        int shift = 0;
        unsigned int temp = num;
        while (temp > min && temp >= (INT_MIN >> 1)) {
            temp <<= 1;
            shift++;
        }
        return shift;
    }
};
class Solution {
    public int divide(int a, int b) {
        //特殊情况1, b=1
        if (b == 1){
            return a;
        }
        //特殊情况2, b=-1
        if (b == -1){
            return a == Integer.MIN_VALUE ? Integer.MAX_VALUE : -a;
        }
        //特殊情况3, a=0
        if (a == 0){
            return 0;
        }

        //确定符号
        boolean positive = (a ^ b) >= 0;
        //为避免溢出, 转换为负数进行计算
        a = a < 0 ? a : -a;
        b = b < 0 ? b : -b;
        //快速相减
        int quotient = 0;
        while (a <= b){
            int base = 1;
            int divisor = b;
            //使用减法, 避免溢出
            while (a - divisor <= divisor){
                divisor <<= 1;
                base <<= 1;
            }
            quotient += base;
            a -= divisor;
        }
        return positive ? quotient : -quotient;
    }
}