【原】628，两数相除

数据结构和算法 2023-06-10 发布于上海

展开全文

问题描述

来源：LeetCode第29题

难度：中等

给定两个整数，被除数dividend和除数divisor。将两数相除，要求不使用乘法、除法和mod运算符。返回被除数dividend除以除数divisor得到的商。

整数除法的结果应当截去(truncate)其小数部分，例如truncate(8.345)=8以及truncate(-2.7335)=-2

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：

被除数和除数均为32位有符号整数。
除数不为 0。
假设我们的环境只能存储32位有符号整数，其数值范围是[−2^31,2^31−1]。本题中，如果除法结果溢出，则返回2^31−1。

解法一

这题说的不能使用*，/，%等符号，那么只能使用减法了，一种方式就是不停的减，比如20/3，用20不停的减去3，但这种效率太差。可以用20减去3的倍数，我们发现20减去6要比减去3更快，当不够减的时候再用他减去3。我们还发现用20减去12的时候要比减去6更快，所以发现一个规律，就是把除数不停的往左移，当除数离被除数最近的时候就用被除数减去除数。

这里要注意的是他们的符号，可以先把他们转化为正数，还有一点要注意就是Integer.MIN_VALUE转化为正数的时候会溢出，可以都转化为long类型。

public int divide(int dividend, int divisor) {
    int sign = (dividend ^ divisor) >= 0 ? 1 : -1;//判断符号
    long dividendTemp = Math.abs((long) dividend);//求绝对值
    long divisorTemp = Math.abs((long) divisor);
    long res = 0;
    while (dividendTemp >= divisorTemp) {
        long tmp = divisorTemp;
        long times = 1;//除数divisor的倍数
        while (dividendTemp >= (tmp << 1)) {
            tmp <<= 1;
            times <<= 1;
        }
        //被除数减去除数的times倍
        dividendTemp -= tmp;
        //累加times
        res += times;
    }
    //添加符号
    res = sign > 0 ? res : -res;
    //需要判断是否有溢出
    return res > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) res;
}

解法二

上面的解法有一定的局限性，为了防止溢出我们可以把int转化为long类型，但如果题中给的数据是long类型，就束手无策了。实际上也可以不用转，我们看一下int类型的范围

-2147483648 到 2147483647

也就是说如果我们把一个负数转化为正数可能会出现溢出，但把一个正数转化为一个负数就不会出现溢出。所以我们可以先把被除数和除数转化为负数，然后让他们相减。

public int divide(int dividend, int divisor) {
    int sign = (dividend ^ divisor) >= 0 ? 1 : -1;//判断符号
    dividend = -Math.abs(dividend);//都转换为负数
    divisor = -Math.abs(divisor);//都转换为负数
    int res = 0;
    //阈值，越界警告值
    int threshold = Integer.MIN_VALUE >> 1;
    while (dividend <= divisor) {
        int tmp = divisor;
        int times = 1;
        //tmp >= threshold，防止tmp一直往左移导致溢出
        while (tmp >= threshold && dividend <= (tmp << 1)) {
            tmp <<= 1;
            times <<= 1;
        }
        dividend -= tmp;
        res -= times;
    }
    //是否有溢出
    if (res == Integer.MIN_VALUE && sign == 1)
        return Integer.MAX_VALUE;
    return sign < 0 ? res : -res;
}

难度升级

这题说的是不能使用乘法，除法，求余运算符。如果在限制一下，除了上面3种运算符以外，还不能使用“+”，“-”符号，看下该怎么解，我们来把上面第二种答案修改一下，如下所示，没有使用任何加减乘除符号

public int divide(int dividend, int divisor) {
    boolean sign = (dividend ^ divisor) >= 0;//判断符号
    dividend = dividend < 0 ? dividend : ~subtraction(dividend, 1);
    divisor = divisor < 0 ? divisor : ~subtraction(divisor, 1);
    int res = 0;
    int threshold = Integer.MIN_VALUE >> 1;
    while (dividend <= divisor) {
        int tmp = divisor;
        int times = 1;
        //tmp >= threshold，防止tmp一直往左移导致溢出
        while (tmp >= threshold && dividend <= (tmp << 1)) {
            tmp <<= 1;
            times <<= 1;
        }
        dividend = subtraction(dividend, tmp);
        res = subtraction(res, times);
    }
    //是否有溢出
    if (res == Integer.MIN_VALUE && sign)
        return Integer.MAX_VALUE;
    return !sign ? res : ~subtraction(res, 1);
}

private int subtraction(int a, int b) {
    if (b == 0)
        return a;
    int c = a & b;
    a ^= c;
    b ^= c;
    return subtraction(a | b, b << 1);
}