Divide Two Integers

29. Divide Two Integers

分析

用位运算模拟除法过程

例如，对于$\frac{x}{y}=k$，将k转换成2进制的形式，有$k = 2^{0} + 2^{1} + … + 2^{31}$

我们可以将每一位的值存下来，然后从高位向低位遍历，只要 x 大于当前位的值，x 就减去当前位的值

又因为$x=yk=y2^0+y2^1+…+y2^{31}$，所以每次 x 减去第i位的值时，最终要求得的商就加上 $2^{i}$

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
    int divide(int dividend, int divisor) {
        typedef long long LL;
        vector<LL> exp;
        bool is_minus = false;
        if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) is_minus = true;
        
        LL a = abs((LL)dividend), b = abs((LL)divisor);
        for (LL i = b; i <= a; i = i + i) exp.push_back(i);

        LL res = 0;
        for (int i = exp.size() - 1; i >= 0; i -- ) {
            if (a >= exp[i]) {
                a -= exp[i];
                res += (LL)1 << i;
            }
        }

        if (is_minus) res = -res;
        if (res > INT_MAX) res = INT_MAX;
        if (res < INT_MIN) res = INT_MIN;

        return res;
    }
};