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。

问题描述：

两数相除，就是看被除数 dividend 中有多少个 除数 divisor，可以使用减法来进行计算。计算过程中我们需要定义中间变量为long类型，以防止数值越界。

JAVA代码：

public int divide(int dividend, int divisor) {
 if(divisor == 0) return Integer.MIN_VALUE;
 if(dividend == 0) return 0;
 
 int sign = 1;
 
 if(dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0){
 sign = -1;
 }
 
 long ldividend = Math.abs((long) dividend);
 long ldivisor = Math.abs((long) divisor);
 
 long result = divide(ldividend,ldivisor);
 
 return sign == 1 ? (result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) result) : (result > Integer.MAX_VALUE ? Integer.MIN_VALUE : (int) (0 - result));
 }
 
 public long divide(long dividend, long divisor) {
 if(dividend < divisor){
 return 0;
 }
 
 long result = 1;
 long sum = divisor;
 
 while(sum + sum <= dividend){
 sum += sum;
 result += result;
 }
 
 return result + divide(dividend - sum,divisor);
 }