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。

题目

题目的主要难度在于不能使用除法，乘法，和取余。
然后只能使用Int来储存数字。
然后我先使用异或判断是否同号，然后使用取绝对值然后直接二分，来搜索这个数字。
这里的二分也不太一样， 因为不能使用除号，所以我每次按照减法来解决，设定一个count，count成倍增加，然后被除数tempDivisor也成倍增加。这样也实现了效率为$O(logn)$

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

        /** 符号位的处理参考了大佬的异或处理方法*/
        boolean negetive= (dividend ^ divisor)<0;
        // count计数现在除数是开始的几倍
        int res=0, count=1;
        long tempDividend = Math.abs((long)dividend);
        long tempDivisor = Math.abs((long)divisor);
        
        while (tempDividend >= tempDivisor) {
            // 题目不让使用乘除取模运算符
            tempDividend -= tempDivisor;
            res += count;

            if (tempDividend < Math.abs(divisor))
                break;
            
            if (tempDividend - tempDivisor < tempDivisor) {
                // System.out.println(count);
                // System.out.println(res);
                tempDivisor = Math.abs(divisor);
                count = 1;
                continue;
            }

            tempDivisor += tempDivisor;
            count += count;
        }
        return negetive ? 0-res: res;
    }
    public static void main(String[] args) {
        Solution s= new Solution();
        int ans = s.divide(37, 2);
        System.out.println(ans);
    }
}