leetcode--29--两数相除

题目：
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

链接：https://leetcode-cn.com/problems/divide-two-integers

思路：
1、我们可以用位移法，因为计算机在做位移时效率特别高，向左移1相当于乘以2，向右位移1相当于除以2
2、我们可以把一个dividend（被除数）先除以2^n， n最初为31，不断减小n去试探,当某个n满足dividend/2^{n>=divisor时，表示我们找到了一个足够大的数，这个数*divisor是不大于dividend的，所以我们就可以减去2}n个divisor，以此类推

Java代码：

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend==Integer.MIN_VALUE && divisor==-1){
            return Integer.MAX_VALUE;
        }

        boolean flag=true;
        if((dividend>0 && divisor<0) || (dividend<0 && divisor>0)){
            flag=false;
        }
        long a = Math.abs((long)(dividend));
        long b = Math.abs((long)(divisor));
        int result = 0;

        for(int i=32; i>=0; i--){
            if(a>>i>=b){
                result += 1<<i;
                a -= b<<i;
            }
        }
        if (flag){
            return result;
        }else{
            return -1*result;
        }
        
        
    }
}