博客

题目链接

1、思路：

最简单的思路就是用被除数不断减去除数，看最多减去几次，但是如果在被除数很大，除数是1的时候，时间复杂度可以达到O(n)，简化的思想是用循环判断

判断被除数是不是大于除数的1倍、2倍、4倍、8倍，(累加实现)①

确定最大的倍数后重复①，知道被除数小于除数，得到的倍数求和即可

这样可以把时间复杂度调整到O(logn)

2、注意

何时溢出：负数比正数大1，所以Integer.Min/-1时会溢出

循环时一定要判断，被除数是不是大于0xc0000000(最小负数的一半)，防止累加溢出

由于存在符号问题，所以需要先判断符号，然后把他们全部转成负的最后再加上符号

负数右移，最高位永远是1

为什么是0xc0000000 这是因为最高位是符号位,因为是负数所以是1，然后最小负数为-2^ 31，一半就是-2^30，所以此时最高四位是1100(补码表示)，也就是c

递归代码

class Solution {
   //表示结果的符号
    int flag = 1;

    public int divide(int a, int b) {
        if (Integer.MIN_VALUE == a && -1 == b)
            return Integer.MAX_VALUE;

        flag = (a ^ b) < 0 ? -1 : 1;

        //全部变负数进行计算
        if (a > 0)
            a = ~a + 1;
        if (b > 0)
            b = ~b + 1;

        int quotient = divide_recursion(a, b, 0);
        return flag == 1 ? quotient : -quotient;
    }

    private int divide_recursion(int a, int b, int mul) {

        if (a > b)
            return mul;

        int quotient = 1, value = b;
        while (value > 0xc0000000 && a < value + value) {
            quotient += quotient;
            value += value;
        }

        return divide_recursion(a - value, b, quotient + mul);
    }
}

非递归代码



精髓在于内部while循环的判定条件

class Solution {
   //表示结果的符号
    int flag = 1;

    public int divide(int a, int b) {
        if (Integer.MIN_VALUE == a && -1 == b)
            return Integer.MAX_VALUE;

        flag = (a ^ b) < 0 ? -1 : 1;

        //全部变负数进行计算
        if (a > 0)
            a = ~a + 1;
        if (b > 0)
            b = ~b + 1;

        int quotient = sup_divide(a, b);
        return flag == 1 ? quotient : -quotient;
    }

    private int sup_divide(int a, int b){

        int result = 0;

        while(a <= b){
            int quotient = 1 , value = b;

            while (a <= value + value && value >= 0xc0000000){
                value += value;
                quotient += quotient;
            }
            result += quotient;
            a -= value;
        }

        return result;
    }
}