描述

给定两个整数a和b，求它们的除法的商a/b，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%'
注意：
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1

示例

  1. 输入：a = 15, b = 2
  2. 输出：7
  3. 解释：15/2 = truncate(7.5) = 7

提示

  • -231 <= a, b <= 231 - 1
  • b != 0

解题思路

  1. 问题分析：当被除数很大但除数很小，减法操作会执行次数很多。例如，2^31/1 执行2^31次减法。当被除数大于除数时，继续比较判断被除数是否大于除数的2倍。如果是，继续判断被除数是否大于除数的4倍，8倍，16倍，……如果被除数最多大于除数的2k倍，那么将被除数减去除数的2k倍，然后将剩余的被除数重复前面的步骤。
  2. 为了求得15/2的商，先从15里减去8 (2^3)，得到7；再从7里减去4(2^2),得到3；再从3里减去2(2^1),得到1，此时1小于2，因此商是3+2+1=7。
  3. 上述讨论被除数和除数都是正数。在计算的时候将负数转化为正数，对于32位整数而言，最小的正数是-2^31,将其转化为正数是2^31，导致溢出。因此将正数转化为负数不会导致溢出。
  4. 设置一个变量，用来记录正数个数，以便在最后的结果调整正负号。
  5. 特殊情况，可能溢出的情况讨论，由于是整数除法，除数不为0，商的值一定小于等于被除数的绝对值，因此，int型溢出只有一种情况，(-2^31)/(-1) = 2^31。
  6. 在计算两个负数的除法时，防止每次计算除数的2倍，会导致大数溢出，要保证计算2倍之后的数大于(-2^31)/2。如果时计算两个正数的除法，要保证计算2倍之后的数小于(2^31-1)/2。
  7. 特殊数值（16进制写法）：0x80000000表示32位int型最小负整数-2^31, 0x7FFFFFFF表示32位int型最大正整数 0xc0000000表示32位int型最小负整数的一半(-2^31)/2。
  8. 如果被除数是n，除数是1。时间复杂度O(logn)

代码

  public int divide(int dividend, int divisor) {
        //-2^31/ -1 = 2^31 溢出
        if(dividend == 0x80000000 && divisor == -1){
            return 0x7FFFFFFF; 
        }

        int negative = 2;//用于记录正数个数
        //由于负数转为正数 -2^31 -> 2^31 越界，所以采用正数转为负数
        if(dividend > 0){
            negative --;
            dividend = -dividend;
        }

        if(divisor > 0){
            negative --;
            divisor = -divisor;
        }

        //计算两个负数相除
        int result = 0;
        while(dividend <= divisor){
            int value = divisor;//统计减数
            int quotient = 1;//统计商
            while(value > 0xc0000000 && value + value >= dividend){//防止value*2溢出
                quotient += quotient;//如果可以用乘法 quotient*=2
                value += value;//如果可以用乘法 value*=2
            }

            result += quotient;
            dividend -= value;
        }
        return negative == 1 ? -result : result;

    }

总结

  1. 32 位 int 的数值范围是 [−231, 231−1]，负数转正数可能会溢出，将正数转化为负数不会导致溢出。
  2. 0x80000000表示32位int型最小负整数-2^31, 0x7FFFFFFF表示32位int型最大正整数 0xc0000000表示32位int型最小负整数的一半(-2^31)/2。
  3. 转为负数后，判断条件也要转变。
  4. 用累加优化算法