414-两个整数相除
将两个整数相除,要求不使用乘法、除法和 mod 运算符。
如果溢出,返回 2147483647 。样例
给定被除数 = 100 ,除数 = 9,返回 11。
标签
二分法
思路
不用乘除法和模运算求来做除法,很容易想到的一个方法是一直做减法,然后计数,除此之外,一种更快速的方法是:
利用位运算,意思是任何一个整数可以表示成以2的幂为底的一组基的线性组合,即 num = a_02^0 + a_12^1 + a_22^2 + … + a_n2n。基于以上这个公式以及左移一位相当于乘以2,我们先让除数左移直到大于被除数之前得到一个最大的基n的值,说明被除数中至少包含2n个除数,然后减去这个基数,再依次找到n-1,…,1的值。将所有的基数相加即可得到结果。
code
class Solution {
public:
/*
* @param dividend: the dividend
* @param divisor: the divisor
* @return: the result
*/
int divide(int dividend, int divisor) {
// write your code here
bool isNeg = false;
if (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0) {
isNeg = true;
}
long long result = 0;
long long d1 = abs((long long)dividend);
long long d2 = abs((long long)divisor);
while (d1 >= d2) {
long long temp = d2;
long long cnt = 1;
while (d1 >= temp) {
d1 -= temp;
result += cnt;
cnt = cnt << 1;
temp = temp << 1;
}
}
if (isNeg) {
result *= -1;
}
if (result < INT_MIN || result > INT_MAX) {
return INT_MAX;
}
return result;
}
};