Leetcode 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) {
            if(dividend==0){
                return 0;
            }
            long AbsDividend  = Math.abs((long)dividend);
            long AbsDivisor = Math.abs((long)divisor);
            long ans = 0;
            for(int i = 31; i >= 0; i--) {
                //比较dividend是否大于divisor的(1<<i)次方，不要将dividend与(divisor<<i)比较，而是用 (dividend>>i)与divisor比较，
                //效果一样，但是可以避免因(divisor<<i)操作可能导致的溢出，如果溢出则会可能dividend本身小于divisor，但是溢出导致dividend大于divisor
                if((AbsDividend >> i) >= AbsDivisor) {
                    ans = ans+(1<<i);
                    AbsDividend = AbsDividend-(AbsDivisor<<i);
                }
            }
            int c = dividend^divisor;
            if(c>=0){
                if(Math.abs(ans)>=Integer.MAX_VALUE){
                    return Integer.MAX_VALUE;
                }
                return (int)ans;
            }else{
                return -(int)ans;
            }
        }
  }