《剑指 Offer》专项突破版 - 面试题 1 : 整数除法

发布时间:2023年12月31日

题目链接29. 两数相除 - 力扣(LeetCode)

题目

输入两个 int 型整数(整数范围为 -2^31 ~ 2^31 - 1?),它们进行除法计算并返回商,要求不得使用乘号 '*'、除号 '/' 及求余符号 '%'。当发生溢出时,返回最大的整数值。假设除数不为 0。例如,输入 15 和 2,输出 15 / 2 的结果,即 7。

分析

这个题目限制我们不能使用乘号和除号进行运算。一个直观的解法是基于减法实现除法。例如,为了求得 15 / 2 的商,可以不断地从 15 里减去 2,当减去 7 个 2 之后余数是 1,此时不能减去更多的 2,因此 15 / 2 的商是 7。我们可以用一个循环实现这个过程。

但这个直观的解法存在一个问题。当被除数很大但除数很小时,减法操作执行的次数会很多。例如,求 (2^31 - 1) / 1,减 1 的操作将执行 2^31 - 1 次,需要很长时间。如果被除数是 n,那么这种解法的时间复杂度为 O(n)。我们需要对这种解法进行优化。

可以将上述解法稍作调整。当被除数大于除数时,判断被除数是否大于除数的 2 倍,如果是,则继续判断被除数是否大于除数的 4 倍、8 倍等。如果被除数最多大于除数的 2^k 倍,那么将被除数减去除数的 2^k 倍,然后将剩余的被除数重复前面的步骤。由于每次将除数翻倍,因此优化后的时间复杂度为 O(logn)。

下面以 15 / 2 为例讨论计算的过程。15 大于 2,也大于 2 的 2 倍(即 4),还大于 2 的 4 倍(即 8),但小于 2 的 8 倍(即 16),于是先将 15 减去 8,还剩余 7。由于减去的是除数的 4 倍,减去这部分对应的商是 4。接下来对剩余的 7 和除数 2 进行比较,7 大于 2,大于 2 的 2 倍(即 4),但小于 2 的 4 倍(即 8),于是将 7 减去 4,还剩余 3。这一次减去的是除数的 2 倍,对应的商是 2。然后对剩余的 3 和除数 2 进行比较,3 大于 2,但小于 2 的 2 倍(即 4),于是将 3 减去 2,还剩余 1。这一次减去的是除数的 1 倍,对应的商是 1。最后剩余的数字是 1,比除数小,不能再减去除数了。于是 15 / 2 的商是 4 + 2 + 1,即 7

上述讨论假设被除数和除数都是正整数,如果有负数则可以将它们转化成正数,计算正数的除法之后再根据需要调整商的正负号。例如,如果计算 -15 / 2,则可以先计算 15 / 2,得到的商是 7。由于被除数和除数中有一个负数,因此商应该是负数,于是商应该是 -7

将负数转换成正数存在一个小问题。对于 32 位的整数而言,最小的整数是 -2^31,最大的整数是 2^31 - 1,因此,如果将 -2^31 转换为正数则会导致溢出。由于将任意正数转换为负数都不会溢出,因此可以先将正数都转换成负数,用前面优化之后的减法计算两个负数的除法,然后根据需要调整商的正负号

最后讨论可能的溢出。由于是整数的除法并且除法不等于 0,因此商的绝对值一定小于或等于被除数的绝对值。因此,int 型整数的除法只有一种情况会导致溢出,即 (-2^31) / (-1),这是因为最大的正数为 2^31 - 1,2^31 超出了正数的范围

代码实现

int divide(int dividend, int divisor)
{
    if (dividend == INT_MIN)
 ?  {
 ? ? ? ?if (divisor == -1)
 ? ? ? ? ? ?return INT_MAX;
 ? ? ? ?
 ? ? ? ?if (divisor == 1)
 ? ? ? ? ? ?return INT_MIN; 
 ?  }
?
    int negNum = 2;
    if (dividend > 0)
    {
        --negNum;
        dividend = -dividend;
    }
    if (divisor > 0)
    {
        --negNum;
        divisor = -divisor;
    }
?
    // 计算两个负数的除法
    int total = 0;
    while (dividend <= divisor)
    {
        int tmp = divisor;
        int quotient = 1; 
 ? ? ? ?// 0xc0000000 即 -2^30,是 -2^31 的一半
 ? ? ? ?// 注意:不得使用乘号 *
        while (tmp >= 0xc0000000 && dividend <= tmp + tmp) ?
        {
            quotient = quotient + quotient;
            tmp = tmp + tmp;
        }
        dividend -= tmp;
        total += quotient;
    }
?
    return negNum == 1 ? -total : total;
}
文章来源:https://blog.csdn.net/melonyzzZ/article/details/135317790
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。