第一章 大数问题

刷题第一站

29. 两数相除

由于整数会有越界，因此用负数保存下一切。这个是可以得到正确结果的！
但是由于这里是一个一个减的，超时了。

class Solution {
    public int divide(int dividend, int divisor) {
        int flag = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0) ? -1 : 1;
        if (dividend > 0) dividend = -dividend;
        if (divisor > 0) divisor = -divisor;
        int res = 0;
        while (dividend <= divisor) {
            res -= 1;
            dividend -= divisor;
        }
        if (flag < 0) {
            return res;
        } else {
            if (res == Integer.MIN_VALUE) {
                return Integer.MAX_VALUE;
            }
            return -res;
        }
    }
}

现在用二分法和快速乘法解决！

class Solution {
    public static int divide(int dividend, int divisor) {
        long result = 0;
        long x = dividend;
        long y = divisor;
        boolean negative = (x < 0 && y > 0) || (x > 0 && y < 0);
        if (x < 0) {
            x = -x;
        }
        if (y < 0) {
            y = -y;
        }
        // 由于x/y的结果肯定在[0,x]范围内，所以对x使用二分法
        long left = 0;
        long right = x;
        while (left < right) {
            long mid = left + right + 1 >> 1; // 为什么呢？看答案
            if (quickMulti(mid, y) <= x) {
                // 相乘结果不大于x，左指针右移
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        result = negative ? -left : left;
        // 判断是否溢出
        if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        return (int)result;
    }
    /**
        * 快速乘法
        *
        * @param a 乘数
        * @param b 被乘数
        * @return 积
        */
    public static long quickMulti(long a, long b) {
        long result = 0;
        while (b > 0) {
            if ((b & 1) == 1) {
                // 当前最低位为1，结果里加上a
                result += a;
            }
            // 被乘数右移1位，相当于除以2
            b >>= 1;
            // 乘数倍增，相当于乘以2
            a += a;
        }
        return result;
    }
}