思路原理

其中,$3 * 2^4 == 3 << 4$,因此将除数按31个比特位移位后保存下来, 即可找到商对应比特位上是否是1.

代码

class Solution {
    public int divide(int low, int up) {
        boolean is_neg = false;
        if(low < 0 && up > 0 || low > 0 && up < 0) is_neg = true;

        long a = Math.abs((long)low), b = Math.abs((long)up);
        // 将分子对应的比特位存下来, 不需要存31位,只需将小于分母的所有比特位保存下来就行
        List<Long> exp = new ArrayList();
        for(long i = b; i <= a; i = i << 1){
            exp.add(i);
        }

        long k = 0;
        //逆序遍历分子比特位, 如果被减数>=减数那么说明商的这一位是1, 对应比特位由1<<i位得到
        for(int i = exp.size() - 1; i >= 0; i--){
            if(a >= exp.get(i)) {
                a -= exp.get(i);
                k += (long)1 << i; 
            }
        }
        if(is_neg) k *= -1;
        if(k > Integer.MAX_VALUE || k < Integer.MIN_VALUE) return Integer.MAX_VALUE;
        return (int)k;
    }
}