# 0029. Divide Two Integers
###### tags: `Leetcode` `FaceBook` `Medium`
Link: https://leetcode.com/problems/divide-two-integers/
## 思路 $O(logN)$ $O(1)$
做法是先把$divisor, divisor*2, divisor*4,...$算出来，一直算到下一个比dividend大，把对应的系数$1,2,4...$也存起来，然后用dividend从后往前减

有很多关于overflow的edge case要处理
由于Integer.MIN_VALUE/-1要写成Integer.MAX_VALUE，所以当作特殊情况处理
由于dividend有可能是Integer.MIN_VALUE，如果把dividend和divisor都变成正数就会overflow，所以两个全都变成负数处理
## Code

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        int a = dividend, b = divisor;
        if(a>0) a = -a;
        if(b>0) b = -b;
        List<Integer> powerOfTwo = new ArrayList<>();
        List<Integer> power = new ArrayList<>();
        int num = b;
        int p = 1;
        while(num>=a){
            powerOfTwo.add(p);
            power.add(num);
            if(num >= Integer.MIN_VALUE/2){
                num *= 2;
                p *= 2;
            }
            else{
                break;
            }
        }
        int res = 0;
        int index = power.size()-1;
        while(index>=0 && a<0){
            while(index>=0 && power.get(index)<a){
                index--;
            }
            if(index<0) break;
            a -= power.get(index);
            res += powerOfTwo.get(index);
            index--;
        }
        return ((dividend>0)&&(divisor>0))||((dividend<0)&&(divisor<0))?res:-res;
    }
}