题目

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

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

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

注意点

1、因为最小值为−231，最大值为231 − 1，将所有数处理成正数进行计算时，需要考虑结果为−231的特殊情况；
2、使用long计算和接收数据是为了便于对溢出情况的判断；
3、核心思想在函数div()，思路如下：求被除数和除数的商相等与计算多少个除数加起来等于被除数（因为一次一次计算会超时，所以一次增加一倍），然后将余数当成被除数和除数继续计算。

实现 public int divide(int dividend, int divisor) { if(dividend == 0) return 0; //处理结果为−2^31的特殊情况 if(divisor == 1) return dividend; //处理结果为−2^31的特殊情况 if(divisor == -1){ if(dividend == Integer.MIN_VALUE) return Integer.MAX_VALUE; return -dividend; } int sign = 1; //结果正负值标记 if((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) sign = -1;//使用long接收便于判断溢出情况 long a = dividend; long b = divisor; //全部处理为正数进行计算 a = a > 0 ? a : -a; b = b > 0 ? b : -b;//计算商 long result = div(a, b); //处理结果溢出 result = result > Integer.MAX_VALUE ? Integer.MAX_VALUE : result; if(sign == 1) return (int)result; return (int)-result; }//计算两数的商 public long div(long dividend, long divisor){ if(dividend < divisor) return 0; long count = 1l; long b = divisor; while((b << 1) <= dividend){ count = count << 1; b = b << 1; } return count + div(dividend – b, divisor); }