难度中等
给定两个整数,被除数 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
class Solution { public: long mul(long a, long k) { long ans = 0; while (k > 0) { if ((k&1) == 1) ans += a; //if ((k%2) == 1) ans += a; k = k >> 1; //k = k/2; a += a; } return ans; } int divide(int dividend_1, int divisor_1) { bool neg = false; long long dividend = dividend_1; long long divisor = divisor_1; if ((dividend^divisor) < 0) { neg = true; } if (divisor < 0) { divisor = -divisor; } if (dividend < 0) { dividend = -dividend; } long long low = 0; long long high = dividend; while(low<=high) { long long mid = low + (high-low)/2; //cout << mid << endl; if (mul(mid,divisor) > dividend) { high = mid -1; } else if (mul(mid,divisor) < dividend) { low = mid +1; } else { long res = neg?-mid:mid; if(res > INT_MAX) res = INT_MAX; if(res <= INT_MIN) res = INT_MIN; return res; } } int res = low-1; if(neg) res = -res; //cout << INT_MIN <<endl; if(res > INT_MAX) return INT_MAX; if(res <= INT_MIN) return INT_MAX; return res; } };
标签:divisor,truncate,res,29,long,mid,相除,dividend From: https://www.cnblogs.com/zle1992/p/16632753.html