剑指 Offer ll 001 整数除法-蒲公英云

剑指 Offer ll 001 整数除法

向右看齐 2024-03-27 09:22 134阅读 0赞

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 ‘*‘、除号 ‘/‘ 以及求余符号 ‘%’ 。

注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1

示例 1：

输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7
示例 2：

输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2
示例 3：

输入：a = 0, b = 1
输出：0
示例 4：

输入：a = 1, b = 1
输出：1

方法一：减法代替除法

假设是a = 15, b = 2，则15-2=13,13-2=11……..3-2=1最终再无法减(a<=b)就结束。

1.其中考虑符号的情况

全为正：符号没影响，直接进行计算
一正一负：这时候要考虑符号情况，但计算过程可以依照全为正数的来计算，因此保留符号，然后对数字进行绝对值后再按照全为正的计算。
- 正常的判断逻辑
- 通过用位运算来进行性能的优化
全为负：符号没影响，直接进行计算

2.同时也要考虑边界问题

因为int是四个字节，是32个bit位，但最大值和最小值不同；32位最大值：2^31-1=2147483647
32位最小值：-2^31 =-2147483648

因此将所有数字都取绝对值进行优化，因为正数和负数的操作都一样，但正数的最大值的绝对值比负数的最小值的绝对值小，所以都转化做负数来操作一定不越界

class Solution {
    public int divide(int a, int b) {
        //32位最大值：2^31-1=2147483647
        //32位最小值：-2^31 =-2147483648
        //当a取-2147483648，b取-1时，2147483648>2147483647就会出现数组越界的情况
        //但2147483647变为负数就不会
        if(a==Interger.MIN_VALUE&&b == -1)
            return Interger.MAX_VALUE;
        //优化前
        //if((a>0&&b<0)||(a<0&&b>0)){
        //    sign=-1;
        //}
        //优化后，采用位运算
        int sign = (a>0)^(b>0)?-1:1;
        //优化前
        //a = Math.abs(a);
        //b = Math.abs(b);
        //优化后
        //因为正数和负数的操作都一样，但正数的最大值的绝对值比负数的最小值的绝对值小
        //所以转化做负数来操作一定不越界
        if(a>0) a=-a;
        if(b>0) b=-b;
        int res = 0;
        //都改成负号之后要注意这里的条件符号要变
        while(a<=b){
            a -= b;
            res++;
        }
        return sign=1?res:-res;
    }
}

方法二：优化，降低时间复杂度每次尝试减去除数的倍数

a = 22，b = 3

22-3*2 k=1
22- 3*2*2= 10 k=2

22-3*2*2*2< 0 k=4
a = 10，b = 3

10-3*2= 4 k=1

10-3*2*2< 0 k=2
a= 4，b = 3 k=1

4-3*2<0
a= 1，b= 3

a-b*2^k ==0 ==>k

class Solution {
    public int divide(int a, int b) {
        //32位最大值：2^31-1=2147483647
        //32位最小值：-2^31 =-2147483648
        //当a取-2147483648，b取-1时，2147483648>2147483647就会出现数组越界的情况
        //但2147483647变为负数就不会
        if(a==Interger.MIN_VALUE&&b == -1)
            return Interger.MAX_VALUE;
        //优化前
        //if((a>0&&b<0)||(a<0&&b>0)){
        //    sign=-1;
        //}
        //优化后，采用位运算
        int sign = (a>0)^(b>0)?-1:1;
        //优化前
        //a = Math.abs(a);
        //b = Math.abs(b);
        //优化后
        //因为正数和负数的操作都一样，但正数的最大值的绝对值比负数的最小值的绝对值小
        //所以转化做负数来操作一定不越界
        if(a>0) a=-a;
        if(b>0) b=-b;
        int res = 0;
        //都改成负号之后要注意这里的条件符号要变
        while(a<=b){
           int value = b;
        int k = 1;
        // 0xc0000000 是十进制 -2^30 的十六进制的表示
        // 判断 value >= 0xc0000000 的原因：保证 value + value 不会溢出
        // 可以这样判断的原因是：0xc0000000 是最小值 -2^31 的一半，
        // 而 a 的值不可能比 -2^31 还要小，所以 value 不可能比 0xc0000000 小
        // -2^31 / 2 = -2^30
        while (value >= 0xc0000000 && a <= value + value) {
            value += value;
            // 代码优化：如果 k 已经大于最大值的一半的话，那么直接返回最小值
            // 因为这个时候 k += k 的话肯定会大于等于 2147483648 ，这个超过了题目给的范围
            if (k > Integer.MAX_VALUE / 2) {
                return Integer.MIN_VALUE;
            }
            k += k;
        }
        a -= value;
        res += k;
        }
        return sign=1?res:-res;
    }
}