不能用乘法，除法，取模
- 暴力办法
直接利用累加的方式，但是会超时
public int divide(int dividend, int divisor) {
int i = 0;
int tmp = 0;
if (dividend == 0) {
return 0;
}
int flag = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) ? -1 : 1;
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
while (true) {
if (tmp < dividend && (tmp + divisor) <= dividend) {
i++;
tmp += divisor;
continue;
}
if (tmp < dividend && (tmp + divisor) > dividend) {
break;
}
if (tmp == dividend) {
break;
}
}
return flag > 0 ? i : (0 - i);
}
- 利用位运算
暴力方法超时的根本原因是一个一个累加，如果能增加这个累加的跨度，是可以减少遍历次数的。有一个核心的原则是(2^k)*除数 <= 当前被除数 <(2^(k+1))*除数
废话不多说，直接用实例举例
dividend = 15;
divisor = 3;
第一波：
i = 0 时， 因为 2^0 * 3 < 15（(cc << i) <= Dividend）, 所以dividend = 15 - 2^0 * 3 = 12 ,此时res += 0 * 2^0 = 1, //解释成汉语就是，1 * 3 = 3 ，因为3 < 15, 所以，暂且把res置为1，把15-3=12 作为除数继续去除以 3
i = 1 时, 因为 2^1 * 3 < 12 （(cc << i) <= Dividend）,所以dividend = 12 - 2^1 * 3 = 6，此时res = 1 + 2^1 = 3.
i=3 时，因为2^2 * 3 > 6 （(cc << i) <= Dividend 这个条件不成立了）
所以当i=3时，内部的for循环就停止了，但是此时的Divided=6，还没除完，所以继续从外面的while循环，重新来一个for循环
第二波：
i=0时，因为 2^0 * 3 < 6 （(cc << i) <= Dividend）,所以dividend = 6 - 2^0 * 3 = 3 ,次数res = 3 + 1 = 4;
i=1时，因为 2^1 * 3 >6 （(cc << i) <= Dividend 这个条件不成立）
所以当i=1时，内部的for循环就停止了，但是此时的Divided=3，还没除完，所以继续从外面的while循环，重新来一个for循环
第三波：
i=0时，因为 2^0 * 3 = 6 （(cc << i) <= Dividend）,所以dividend = 3 - 2^0 * 3 = 0 ,次数res = 4 + 1 = 5;
i=1时，for循环终止，由于dividend =0 <= Divisor ,所以外层的while也终止，所以res=5.
/**
*
* @param dividend
* @param divisor
* @return
*/
public int divide2(int dividend, int divisor) {
int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
long Dividend = Math.abs((long) dividend);
long Divisor = Math.abs((long) divisor);
long res = 0;
while (Dividend >= Divisor) {
long cc = Divisor;
for (int i = 0; (cc << i) <= Dividend; i++) {
Dividend -= cc << i;
res += 1 << i;
}
}
if (sign < 0) {
res = -res;
}
if (res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
return (int)res;
}
