题目形容
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不应用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 失去的商。
整数除法的后果该当截去（truncate）其小数局部，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
输出: dividend = 10, divisor = 3
输入: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输出: dividend = 7, divisor = -3
输入: -2
解释: 7/-3 = truncate(-2.33333..) = -2
解题思路
首先要思考到数字的正负问题，如果除数和被除数都为负数或者都为正数，后果也是负数，否则为正数。应用 sign 标记正负，而后将除数和被除数都转成负数：
int sign = 1;if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) { sign = -1;}int dividends = Math.abs(dividend);int divisors = Math.abs(divisor);要求不能应用乘法、除法和取余运算，算出两数相除的值，后果值取整。波及到运算，那就得应用到别的运算符，比方加法。比方 10/3 转成 10 始终减 3,直到被减的数小于被除数。
10 - 3 = 7 7 -3 = 4 4 - 3 = 1 < 3 下面一共减了三次，所以 10/3 = 3，依据思路写出上面代码：
public int divide(int dividend, int divisor) { int sign = 1; if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) { sign = -1; } int dividends = Math.abs(dividend); int divisors = Math.abs(divisor); int index = 0; while (dividends >= divisors) { dividends = dividends - divisors; index++; } return index * sign; }后果：
这里波及到数字范畴的问题，咱们发现 -2147483648，取相反数还是-2147483648，这是因为编码 int 占四个字节，一个字节八个位。
所以须要应用转成 long 类型，防止数据越界问题：
int sign = 1; if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) { sign = -1; } long dividends = Math.abs((long) dividend); long divisors = Math.abs((long) divisor); long index = 0; while (dividends >= divisors) { dividends = dividends - divisors; index++; } if (index > Integer.MAX_VALUE && sign == 1) { return Integer.MAX_VALUE * sign; } return (int) index * sign;后果:
后果超时，是因为一个个减，是须要反复次数，工夫复杂度是O(n)。
这里须要应用递进式的减法，比方
10/1 = 1010 - 1 = 9 index = 19 - 1 = 8 index = 28 - 1 = 7 index = 37 - 1 = 6 index = 46 - 1 = 5 index = 5....1 - 1 = 0 index = 10这下面是要进行十步操作，须要做的一个递进的操作，被除数做加倍，比方下面能够转成：
10 - 1= 9 index = 1 = 19 - 1*2 = 7 index = 1 + 1*2 = 37 - 1*2*2 = 3 index = 1 + 1*2 + 1 *2*2 = 7再匹配 3 - 1*2*2*2 < 0,还须要再进行下面的减操作3 - 1 = 2 index = 7 + 1 = 82 - 1*2 = 0 index = 7 + 1 + 1* 2 = 10具体流程：
依据以上思路可得如下代码：
int sign = 1; if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) { sign = -1; } long dividends = Math.abs((long) dividend); long divisors = Math.abs((long) divisor); long index = 0; while (dividends >= divisors) { long temp = divisors; long i = 1; while (dividends >= temp) { dividends = dividends - temp; index = index + i; temp = temp << 1; i = i << 1; } } if (index > Integer.MAX_VALUE && sign == 1) { return Integer.MAX_VALUE * sign; } return (int) index * sign;总结
- 此题解法开始想到将除法转成减法，一个一个累计减
- 须要思考 int 范畴溢出问题，这里对立换成
long类型 - 累减须要的工夫负复杂度是O(n),容易超时，这里须要转成递进减法，即每次都对被减数加倍
如果感觉文章对你有帮忙的话，请点个赞吧!