博文中会简要介绍Leetcode P0029题目分析及解题思路。
“Divide Two Integers”是一道比较巧妙的题目。这道题有两种思路，一种是纯粹的位运算思路，另一种是巧妙运用二分查找的思想。
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.
Note:
Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.
纯粹的位运算解法不再赘述，详细的信息可以看带有注释的C++代码。这里主要提一下巧妙运用二分法的解法。
一般我们提到二分法，很容易想到分而治之的思想，即在很多时候二分法和分而治之等价。这样一来反而容易陷入思维惯性，认为二分法就是不断地二分主体问题成子问题，通过解决子问题来解决主体问题，或者是不断地二分主体成两个部分，排除掉一个部分仅保留另一个部分来减少（优化）解空间。
但是在这题中，如果我们尝试自上而下二分主体，即被除数，会陷入很多边缘条件的判断，从而复杂化问题。所以这里我们需要巧妙运用二分想法。原先我们是在缩小解空间，我们能不能从一个最小满足解开始，指数地扩大满足的解空间，从而最终得到最大解空间，以此得到结果呢？
答案是肯定的，这道题里，我们可以令sum=divisor然后从一个sum出发以2为指数地扩大sum，即每次试探sum+sum，若满足条件，则sum+=sum从而扩大sum为原先的两倍，这样一来我们每次扩大和当前解空间相同的空间，从而减少试探次数，最终形成时间复杂度为O(logn)的解法。
以下是Java的题解代码实现。
class Solution {
public int divide(int dividend, int divisor) {
// Reduce the problem to positive long integer to make it easier.
// Use long to avoid integer overflow cases.
int sign = -1;
if ((dividend >= 0 && divisor >= 0) || (dividend < 0 && divisor < 0))
sign = 1;
long ldividend = Math.abs((long) dividend);
long ldivisor = Math.abs((long) divisor);
long quotient = this.ldivide(ldividend, ldivisor);
int ans = 0;
// Handle overflow.
if (quotient >= Integer.MAX_VALUE)
ans = (sign == 1)? Integer.MAX_VALUE: Integer.MIN_VALUE;
else
ans = (int) (sign*quotient);
return ans;
}
private long ldivide(long dividend, long divisor) {
// Recursion exit condition
if (dividend < divisor)
return 0;
// Find the largest multiple so that (divisor * multiple <= dividend),
// whereas we are moving with stride 1, 2, 4, 8, 16...2^n for performance reason.
// Think this as a binary search.
long sum = divisor, multiple = 1;
while ((sum+sum) <= dividend) {
sum += sum;
multiple += multiple;
}
// Look for additional value for the multiple from the reminder (dividend - sum) recursively.
return multiple+this.ldivide(dividend-sum, divisor);
}
}
以下是C++的题解代码实现。
class Solution {
public:
int divide(int dividend, int divisor) {
return this->divide_int64(dividend, divisor);
}
private:
int divide_int64(int64_t n, int64_t m) {
// determine sign of the quotient
int sign = n < 0 ^ m < 0 ? -1 : 1;
// remove sign of operands
n = abs(n), m = abs(m);
// q stores the quotient in computation
int64_t q = 0;
// test down from the highest bit
// accumulate the tentative value for valid bits
for (int64_t t = 0, i = 31; i >= 0; i--)
if (t + (m << i) <= n)
t += m << i, q += 1LL << i;
// assign back the sign
if (sign < 0)
q = -q;
// check for overflow and return
return ((q >= INT_MAX)? INT_MAX: ((q <= INT_MIN)? INT_MIN: q));
}
};