给定两个整数，被除数 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的幂为底的一组基的线性组合.
class Solution {
public int divide(int dividend, int divisor) {
long absDividend = Math.abs((long) dividend);
long absDivisor = Math.abs((long) divisor);
if (absDividend < absDivisor) {
return 0;
}
long ret = 0;
//absDividend = absDivisor * (2^n + 2^(n-1) + ... )
while (absDividend >= absDivisor) {
int count = 0;
long tmp = absDivisor;
long halfAbsDividend = absDividend >> 1;
while (tmp < halfAbsDividend) {
tmp = tmp << 1;
count++;
}
ret = ret + (1 << count);
absDividend = absDividend - tmp;
}
boolean isNegative = dividend > 0 ^ divisor > 0;
boolean overflow = (isNegative && -ret < Integer.MIN_VALUE) || (!isNegative && ret > Integer.MAX_VALUE);
if (overflow) {
return Integer.MAX_VALUE;
}
return (int) (isNegative ? -ret : ret);
}
}
