29. 两数相除

29. 两数相除

题解：

1. a / b = y 等价于 b > a - (b * y) > 0 , 只要求出减了多少次b就好了。
2. 一个一个地减b，效率太低了，最坏情况下， a = 2^31 - 1 , b = 1 ,超时； 应该先预处理出 b * 2^k (最多不超过31个)， 然后从大到小被 a减， b > a - 2^k *b - 2 ^(k-1) * b - ... - 2^0 * b > 0 , 然后就可以求出y了
3. 符合和数值分开处理，注意 a = -2147483648（int 的最小值） b = -1 时， 会爆int

class Solution {
   public int divide(int x, int y) {
        List<Long> exp = new ArrayList<>();
        // 被除数和除数 异号
        boolean is_minus = false;
        if (x< 0 && y >0 || x > 0 && y < 0) is_minus = true;

        long a = Math.abs((long)x), b = Math.abs((long)y);
        // 初始化 2^0 * b 到 2^k * b 的数
        for(long i = b; i <= a; i = i + i) exp.add(i);
        long res = 0;
        for(int i = exp.size() - 1; i >= 0; i -- ) {
            if (a >= exp.get(i)) {
                a -= exp.get(i);
                res += 1L << i;
            }
        }
        if (is_minus) res = -res;
        if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) res = Integer.MAX_VALUE;
        return (int)res;
    }
}