算法数学算法

限制运算符的数字运算

字数统计: 1.1k字   |   阅读时长: 5分
, ,

摘要: 限制运算符的数字运算问题，四道题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

有时我们会遇到实现某种运算的问题，但是限制某些运算符的使用。这类问题主要考察的是对各个运算符的特性的理解，以及对运算数字的溢出，正负号等细节处理方法。本文简要串讲一下力扣上相关的四道题。

371. 两整数之和

问题

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

代码(C++)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int getSum(int a, int b) {
        using uint = unsigned int;
        if(!b) return a;
        int s = a ^ b;
        int carry = uint(a & b) << 1;
        return getSum(s, carry);
    }
};

面试题 08.05. 递归乘法

问题

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

分析

快速乘法的递归实现。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int multiply(int A, int B) {
        if(A < B) return multiply(B, A);
        if(B == 1) return A;
        int x = multiply(A, B >> 1);
        if(B & 1)
            return x + x + A;
        return  x + x;
    }
};

剑指 Offer 65. 不用加减乘除做加法

问题

写一个函数，求两个整数之和，要求在函数体内不得使用 "+","-","*","/" 四则运算符号。

代码(C++)

1
2
3
4
5
6
7
class Solution {
public:
    int add(int a, int b) {
        if(b == 0) return a;
        return add(a ^ b, (unsigned int)(a & b) << 1);
    }
};

面试题 16.09. 运算

问题

请实现整数数字的乘法、减法和除法运算，运算结果均为整数数字，程序中只允许使用加法运算符和逻辑运算符，允许程序中出现正负常数，不允许使用位运算。

你的实现应该支持如下操作：

  • Operations() 构造函数
  • minus(a, b) 减法，返回a - b
  • multiply(a, b) 乘法，返回a * b
  • divide(a, b) 除法，返回a / b

提示：

1
2
你可以假设函数输入一定是有效的，例如不会出现除法分母为0的情况
单个用例的函数调用次数不会超过1000次

分析

先实现取相反数，进而可以实现减法。

预处理下面两个数组，取反和判断溢出时使用：

1
2
poss:  0,  2,  4,  8, ...,  2^30
negs: -1, -2, -4, -8, ..., -2^30

乘除法通过快速乘法实现即可。

代码(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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
class Operations {
public:
    Operations() 
    {
        // 构造poss和negs
        int p = 1, n = -1;
        poss.push_back(p);
        negs.push_back(n);

        for(int i = 0; i < 30; i++) 
        {
            p += p;
            n += n;
            poss.push_back(p);
            negs.push_back(n);
        }
    }

    int minus(int a, int b) 
    {
        return a + neg(b);
    }

    int multiply(int a, int b) 
    {
        if(a == 0 || b == 0) 
            return 0;
        if(a == 1) 
            return b;        // 这一步是针对 b = INT_MIN 的情况，防止下一步取 neg 时溢出
        if(b < 0) 
            return neg(multiply(a, neg(b)));

        int ans = a;
        int cnt = 1;              // cnt 表示当前结果里已经累加了几个 a

        // cnt < poss[30]是为了防止溢出
        while(cnt < poss[30] && cnt + cnt <= b) 
        {
            ans += ans;
            cnt += cnt;
        }
        ans += multiply(a, minus(b, cnt));

        return ans;
    }

    int divide(int a, int b) 
    {
        if(a == 0) 
            return 0;

        int result = 1;
        // 只写同号的情况，非同号时用neg转化成同号，但是要注意溢出
        if(a > 0) 
        {
            if(b == INT_MIN) 
                return 0;          // 防止下一句取neg的时候溢出
            if(b < 0) 
                return neg(divide(a, neg(b)));
            if(a < b) 
                return 0;

            int acc = b;                        // 不断往acc里填充b，直到acc达到a
            while(acc < poss[30] && a >= acc + acc) 
            {
                result += result;               // result表示已经填充了几个b了
                acc += acc;
            }
            result += divide(minus(a, acc), b);
        } 
        else 
        {
            if(b == 1) r
                eturn a;                // 防止若a=INT_MIN造成下一句运算时溢出
            if(b > 0) 
                return neg(divide(a, neg(b)));
            if(a > b) 
                return 0;

            int acc = b;
            while(acc >= negs[30] && a <= acc + acc) 
            {
                result += result;
                acc += acc;
            }
            result += divide(minus(a, acc), b);
        }
        return result;
    }

private:
    vector<int> negs, poss; // 存的是[-1, -2, -4...]、[1, 2, 4...]，取反和判断溢出时用

    int neg(int a) 
    {
        if(a == 0) 
            return 0;

        int result = 0;

        if(a > 0) 
        {
            // 从绝对值最大的部分开始填充
            for(auto p = negs.rbegin(); p != negs.rend(); p++) 
            {
                if(*p + a < 0) continue;
                a += *p;
                result += *p;
            }
        } 
        else 
        {
            for(auto p = poss.rbegin(); p != poss.rend(); p++) 
            {
                if(*p + a > 0) continue;
                a += *p;
                result += *p;
            }
        }
        return result;
    }

};
Share