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.
Example 1:
Input: dividend = 10, divisor = 3 Output: 3 Explanation: 10/3 = truncate(3.33333..) = 3.Example 2:
Input: dividend = 7, divisor = -3 Output: -2 Explanation: 7/-3 = truncate(-2.33333..) = -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: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
两数相除。思路是给两个数字做除法，但是有一些限制条件。不能用乘法，除法和模（%）；两个数字只能在int范围内，除数不会为0，并且操作环境只能接受int型（也就是说不能转换成long型做计算）。
我参考的是官方答案其中一个比较朴素的思路。首先注意到，整型的最大值其实是2^31 - 1，最小值是-2^31。如果是-2^31 / -1就会越界，这个case需要单独处理一下。同时为了避免运算过程中出现overflow，就暂且将所有运算先放到负数环境中计算。因为这样做既保证了不会overflow，最后得出正确的结果也就是增减一个负号的功夫。接着来看一下除数和被除数的正负情况，记录有几个数字被添加了负号，这个在最后要还回去。
当被除数和除数都被改成负数之后，除数此时会大于被除数。此时需要通过除数 + 除数的方式，尽快找到一个足够大的除数。举个例子，93706 / 157。既然题目规定了不能用乘法，除法和模，那么比较粗暴的办法是想到用减法，看看93706被减去多少个157就小于0了。但是这样做，遇到数字很大的case会超时。这里优化的办法是每次减去157如果还是没有碰到0，就减去157 + 157 = 314，之后会遍历到的数字如下
157 - 1 * 157 314 - 2 * 157 628 - 4 * 157 1256 - 8 * 157 2512 - 16 * 157 5024 - 32 * 157 10048 - 64 * 157 - 2^6 * 157 20096 - 128 * 157 40192 - 256 * 157 80384 - 512 * 157 - 2^9 * 157 160768 # Too big
当被除数被加到80384的时候就可以停下了，此时余数 = 93706 - 80384 = 13322。如果再加，就会超过93706。注意80384有一个特点，他是2的9次方个（512个）157的和。所以最后的商里面一定是512再加上一些别的数的和。此时再按照之前这个方式去计算到底13322除以157等于多少，得出2^6 * 157 = 10048，余数是13322 - 10048 = 3274。其中10048是以此循环，直到余数小于157为止。此时的商 = 512 + 64。再往下循环，直到余数小于157为止。
时间O(logn * logn) - 找最大除数的动作，找一次就需要O(logn)，找到之后余数还要接着往下递归，所以是O(logn)的平方
空间O(1)
Java实现
1 class Solution {
2 private static int HALF_INT_MIN = -1073741824;
3
4 public int divide(int dividend, int divisor) {
5
6 // Special case: overflow.
7 if (dividend == Integer.MIN_VALUE && divisor == -1) {
8 return Integer.MAX_VALUE;
9 }
10
11 /* We need to convert both numbers to negatives.
12 * Also, we count the number of negatives signs. */
13 int negatives = 2;
14 if (dividend > 0) {
15 negatives--;
16 dividend = -dividend;
17 }
18 if (divisor > 0) {
19 negatives--;
20 divisor = -divisor;
21 }
22
23 int quotient = 0;
24 /* Once the divisor is bigger than the current dividend,
25 * we can't fit any more copies of the divisor into it. */
26 while (divisor >= dividend) {
27 /* We know it'll fit at least once as divivend >= divisor.
28 * Note: We use a negative powerOfTwo as it's possible we might have
29 * the case divide(INT_MIN, -1). */
30 int powerOfTwo = -1;
31 int value = divisor;
32 /* Check if double the current value is too big. If not, continue doubling.
33 * If it is too big, stop doubling and continue with the next step */
34 while (value >= HALF_INT_MIN && value + value >= dividend) {
35 value += value;
36 powerOfTwo += powerOfTwo;
37 }
38 // We have been able to subtract divisor another powerOfTwo times.
39 quotient += powerOfTwo;
40 // Remove value so far so that we can continue the process with remainder.
41 dividend -= value;
42 }
43
44 /* If there was originally one negative sign, then
45 * the quotient remains negative. Otherwise, switch
46 * it to positive. */
47 if (negatives != 1) {
48 return -quotient;
49 }
50 return quotient;
51 }
52 }