计算的本质探究 ——用逻辑运算模拟数学运算
上文提要:已知逻辑运算是数学运算的简化版,反过来,我们也可以用逻辑运算来模拟数学四则运算。
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回复。