给定两个整数，被除数 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。

 

 

 

思路：

任何一个整数可以表示成以2的幂为底的一组基的线性组合,就是把十进制转二进制的过程。比如：9=2^3 + 2^0

左移一位相当于乘以2,右移一位相当于除以2.（这里不考虑溢出啥的）
          
  解法如下：
先让除数一直左移，直到大于被除数之前得到一个最大的基数。然后接下来我们每次尝试减去这个基，
如果可以则结果增加加2^k,然后基继续右移迭代，直到基为0为止。因为这个方法的迭代次数是按2的幂

 public int divide(int dividend, int divisor) {
	        // 溢出处理
	        if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) {
	            return Integer.MAX_VALUE;
	        }
	        // 求结果的符号
	        int sign = (dividend ^ divisor) <0 ? -1 : 1;
	        // 求绝对值，为防止溢出使用long
	        long num1 = Math.abs((long) dividend);
	        long num2 = Math.abs((long) divisor);
	        // 记录结果
	        int result = 0;

	        // 被除数大于除数
	        while (num1 >= num2) {
	            // 记录除数
	            long tmp = num2;
	            // 记录商的大小
	            long mul = 1;
	            while (num1 >= (tmp << 1)) {
	                tmp <<= 1;
	                mul <<= 1;
	            }
	            // 减去最接近dvd的dvs的指数倍的值（值为tmp）
	            num1 -= tmp;
	            // 修正结果
	            result += mul;
	        }
	        return result * sign;
	    }