29.两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:
输入: dividend = 10, divisor = 3
输出: 3

示例 2:
输入: dividend = 7, divisor = -3
输出: -2

说明:
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

//效率太低超出时间限制
class Solution {
    public int divide(int dividend, int divisor) {
        int n = 0;
        if(dividend > 0 && divisor > 0) {
            while(dividend >= divisor) {
                dividend -= divisor;
                n++;
            }
            if(n < Integer.MAX_VALUE && n > Integer.MIN_VALUE) {
                return n;
            }
            return Integer.MAX_VALUE;
        }else if((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
            dividend = Math.abs(dividend);
            divisor = Math.abs(divisor);
            while(dividend >= divisor) {
                dividend -= divisor;
                n++;
            } 
            if(n < Integer.MAX_VALUE && n > Integer.MIN_VALUE) {
                return -n;
            }
            return Integer.MAX_VALUE;
        } else if(dividend < 0 && divisor < 0){
            while(dividend <= divisor) {
                dividend -= divisor;
                n++;
            }  
            if(n < Integer.MAX_VALUE && n > Integer.MIN_VALUE) {
                return n;
            }
            return Integer.MAX_VALUE;
        } else {
            return 0;
        }
        
        
    }
}

//位移法
/**
     * 我们可以把一个dividend（被除数）先除以2^n，n最初为31，不断减小n去试探,当某个n满足dividend/2^n>=divisor时，
     *
     * 表示我们找到了一个足够大的数，这个数*divisor是不大于dividend的，所以我们就可以减去2^n个divisor，以此类推
     *
     * 我们可以以100/3为例
     *
     * 2^n是1，2，4，8...2^31这种数，当n为31时，这个数特别大，100/2^n是一个很小的数，肯定是小于3的，所以循环下来，
     *
     * 当n=5时，100/32=3, 刚好是大于等于3的，这时我们将100-32*3=4，也就是减去了32个3，接下来我们再处理4，同样手法可以再减去一个3
     *
     * 所以一共是减去了33个3，所以商就是33
     */
class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean negative;
        negative = (dividend ^ divisor) <0;//用异或来计算是否符号相异
        long t = Math.abs((long) dividend);
        long d= Math.abs((long) divisor);
        int result = 0;
        for (int i=31; i>=0;i--) {
            if ((t>>i)>=d) {//找出足够大的数2^n*divisor
                result+=1<<i;//将结果加上2^n
                t-=d<<i;//将被除数减去2^n*divisor
            }
        }
        return negative ? -result : result;//符号相异取反
    }
}