目录

lc29.两数相除

Shen 收录于每日一题

2021-10-12 约 318 字预计阅读 1 分钟

目录

29.两数相除

二分查找+快速乘

快速乘：根据每一位的权重进行乘法。
对于$y/x$查找第一个$x*?<y$的数。
$T:O(log^2n)$,快速乘$log(n)$，二分查找$log(n)$,$n$为32位数字表示的最大的数字。

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


class Solution {
public:
    using ll = long long;
    int divide(int dividend, int divisor) 
        bool neg = false;
        if((dividend ^ divisor) < 0) {
            neg = true;
        }

        ll x = dividend, y = divisor;
        if(x < 0) {
            x = -x;
        }
        if(y < 0) {
            y = -y;
        }

        // 找到最后一个y*? <= x
        ll l = 0, r = x;

        while(l < r) {
            ll mid = (r - l + 1 >> 1) + l;
            cout << mid << endl;
            if(mul(mid, y) <= x) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        
        l = neg ? -l : l;

        if(l > INT_MAX) return INT_MAX;
        return l;
    }
    ll mul(ll x, ll y) {
        ll ans = 0;
        while(x) {
            if(x & 1) {
                ans += y;
            } 
            x >>= 1;
            y += y;
        }

        return ans;
    }
    
};