计算的本质探究 ——用逻辑运算模拟数学运算

上文提要:已知逻辑运算是数学运算的简化版,反过来,我们也可以用逻辑运算来模拟数学四则运算。

1)模拟加法:

C = A + B

如 2 + 5  = 7 在二进制中可以表示为

10 + 101 = 111

3 + 5 = 8在二进制中可以表示为

11 + 101 = 1000

从上面算式中可以看出

1.bit位计算的过程可以看作“按位异或运算”的过程,即相同为0,不同为1,如0+1=1,1+0=1,0+0=0;

2.进位的过程可以看作“按位与运算”的过程,即全1为1,有0为0。 如 1+1=1,因为进位是往高位+1,因此需要将进位结果左移一位。

将上述两个操作的结果再次重复1、2的步骤,这是一个递归的过程,也可以通过非递归即循环来实现。

如求a+b,等价于(a ^ b) + (a & b) << 1

相关代码如下:


1
2
3
4
5
6
7
8
int add(int a, int b) {
    if(0==b) {
        return a;//若进位为0,运算结束
    }
    int temp = a ^ b;
    int carry = (a & b) << 1;
    return add(temp,carry); //若存在不为0的进位,则重复运算
}

2)模拟减法:

C = A - B

可看作

C = A + (-B)

因此,模拟减法可以作为模拟加法运算,只需将A加上B的负值即可

二进制求-B运算:

先将B按位取反得到B的补码,再+1即可。

因此c = a - b可等效为c = a + (~b + 1)

相关代码如下:

 


1
2
3
int sub(int a, int b) {
    return add(a, add(~b, 1));
}

 

3) 模拟乘法:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int multiply(int a ,int b) {
    int sum = 0;
    map<int, int> m_map;
    for(int i = 0; i < 32; i++) {
        m_map.insert( pair<int,int>(1 << i, i));//将int类型的32位状态加入map容器
    }
    while(b != 0){
        int last_bit = m_map[b&~(b-1)];//取最后一个1的下标
        sum += (a << last_bit);//完全只用逻辑运算的话,该句可以调用加法函数实现
        b &= b-1;
    }
    if(a > 0 && b < 0 || a < 0 && b > 0) {
        sum = -sum;
    }
    return sum;
}

模拟除法:

 


1
2
3
4
5
6
7
8
9
10
11
12
13
int div( int a, int b){
    int left_num = a;
    int result = 0;
    while(left_num>=b){
        int mul=1;//乘数因子
        while(b*mul<=(left_num>>1)) {
            mul = mul << 1;
        }
        result+=mul;
        left_num-=b*mul;
    }
    return result;
}
博主

这货来去如风,什么鬼都没留下!!!

相关推荐

嗨、骚年、快来消灭0回复。

001650;您的ip地址是54.227.136.157; 当前围观人数:2

隐私政策

橘花2支持在线更新了,点我下更新支持文档然后托给橘花,再点SSP面板右键更新