“模拟”的四则运算

学姐之前分享过一个问题，让我很感兴趣。在高级语言中，不使用 循环 和 if语句 能不能实现 +, -, *, / 呢？

我选择了最为习惯的语言：c/cpp，来实现

问题的关键是实现加减法，只要有了加减法，乘除法就有了。

限制：不使用循环语句和 if-else 语句。


思路：使用递归替代循环，使用短路的逻辑运算替代 if-else，表示状态的变量使用了全局表示。

下面分享我的设计思路：

可能有很多不够严谨的地方，仅供理解参考

加法：使用xor运算^ ，可以看成是无进位加法，即把两个整数的各各位数进行相加，而有进位的部分，使用与运算& 保存下来，并左移<<“补”上原本需要的进位，重复地进行& <<可以看成是把进位+回到数据里。

减法：

1. 其实没啥好说的，有加法就有减法，关键是理解了反码和补码的原理。我有个很好的思路理解这玩意，举个例子： -1可以看成是0+(-1) = -1，移0，-1 = -1 - 0，而因为-1表示的是负数，则-1 = ～1 +～ 0，因此～0实际上可以看成是二进制为1000 0000 ，则加法的结果为1111 1110，即-1的反码表示，于是乎我们似乎就知道了计算机规定最高位用来判断正负符号的原因了。
2. 因为负数在计算机内使用的是补码的方式存储和运算，因此把一个正数变成一个负数，就是从正数的原码变成对应负数补码的过程，再举个例子：1的原码0000 0001，各位取反～，得到1111 1110，-1的反码，同时是-2的补码，再加上1，可以得到1111 1111，我们成功了，那么也明白了-2+1 = -1，于是乎我们就知道了补码的作用，即方便计算机快捷地用加法实现减法。

乘除法：使用普通的累加思路比较低效，乘法复杂度O(n)， 除法复杂度O(n/m)（建立在add 上的复杂度，即把add当成O(1)，下同）
或许可以使用二分的思路把乘法优化到O(logn) 。(优化了orz)

使用全局变量的优势：在递归时，有“静态”特性且易修改，里层的递归可以把变化反应在变量上，很方便。

代码如下：

#include <iostream>

using namespace std;


int add_t;
int add(int n, int m){
    int a = n ^ m;
    int b = n & m;
    add_t = a;
    
    b && add(a, b << 1);

    /*
	循环的版本
    while (b){
        int t = a;
        b <<= 1;
        a ^= b;
        b &= t;
    }
    */
    return add_t;
}


int sub(int n, int m){
    return add(n, ~m+1);
}

// 乘法已优化
int mul_cnt, mul_sum, mul_tmp;
int mul_swap(int *a, int *b){
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
    return 0;
}
int saveTmp(int x, int *n){
    mul_tmp = add(mul_tmp, x);
    *n = sub(*n, 1);
    return 0;
}
int mul(int n, int m){
    n > m && mul_swap(&n, &m);	//交换大小数
    n & 1 && saveTmp(m, &n); 	//处理奇数情况
    
    mul_sum = add(m, m);
    n >>= 1;
    n == 1 || mul(n, mul_sum);
    
    
    return add(mul_sum, mul_tmp);
}

int divi_cnt, divi_tmp;
int setCnt(){
    divi_cnt = sub(divi_cnt, 1);
    divi_tmp = 0;
    return 0;
}
int divi(int n, int m){
    divi_tmp = sub(n, m);
    divi_cnt = add(divi_cnt, 1);
    
    divi_tmp <= 0 || divi(divi_tmp, m);
  
    divi_tmp < 0 && setCnt();	//被减为负数时，即被除数不够减，被除数小于除数，返回结果0
    
    return divi_cnt;
}


int main()
{
    int a, b;
    
    cin >> a >> b;
    
    cout << add(a, b) << endl;
    cout << sub(a, b) << endl;
    cout << mul(a, b) << endl;
    cout << divi(a, b) << endl;

    return 0;
}

我没怎么用数据测试过，应该没啥大问题吧，这个随笔的目的是分享这种有趣的思路过程，如果有更好的想法或问题，非常欢迎留言。 //w\\