使用位运算实现加减乘除
加法
加法可以拆分成几个步骤,首先是每位上的数对应相加,将结果与对应的基数取模,设置为当前位,然后处理相加之后产生进位的位,给它们的上一个拥有更大权值的位加上一,如果又产生进位,就如此循环,直到没有进位为止。
对于二进制来说,第一步相加取模是这样的:1
2
31 + 1 = 0
1 + 0 = 1
0 + 0 = 0
可以看到,只有两位数不一样的情况下,值才为1。这正和异或运算
的结果相同。
而在二进制中,只有1+1才有可能产生进位,也就是说,我们需要找出两个数中都为1的位,这一点可以使用与运算
实现。然后,将与运算的结果左移一位,与第一步的结果相加,就能得到最终的结果。
可以注意到最后又产生了一次加法,这里可以使用递归的思想来处理。不断递归,直到第二步的结果为0,也就是说,没有在需要进位的位,就意味着计算完毕。
于是,加法可以使用异或和与运算实现。递归的C语言实现如下:1
2
3
4
5
6
7
8
9
10int add(int a, int b) {
if (b == 0) {
return a;
}
int add_xor = a ^b;
int add_carry = (a & b) << 1;
return add(add_xor, add_carry);
}
尾递归也可以很容易优化为迭代形式:1
2
3
4
5
6
7
8
9
10
11int add_by_loop(int a, int b) {
int add_xor = 0;
while (b) {
add_xor = a ^ b;
b = (a & b) << 1;
a = add_xor;
};
return a;
}
减法
实现了加法,接可以直接将减法视为加上它的逆元。对于以补码形式表示的有符号数来说,一个数x的逆元为~x+1
。这是因为,对于一个w位的数x来说,x + ~x = 2^(w) - 1。所以 x + ~x + 1 = 2^(w) = 0(截断)。所以 ~x + 1为 x的逆元。
因此,减法可以如下实现:1
2
3int sub(int a, int b) {
return add(a, add(~b, 1));
}
乘法
abc * def 这种形式的乘法,实际上可以转化为加法和移位的结合。因为对于abc * def,实际上对于def中的每一位(例如e),都有对应个(e个)的abc相加,然后将结果提升当前位的权值(假如是十进制,对于e,提升10^1)。这样每一位运算的结果加起来,就是最终的结果。
二进制比十进制更简单,因为其每一位只可能为0或1,要么不加,要么加一次。
因此,乘法可以如下实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14int mul(int a, int b) {
int result = 0;
while (b) {
if (b & 0x1) {
result = add_by_loop(result, a);
}
b >>= 1;
a <<= 1;
}
return result;
}
除法
除法则可以视为乘法的逆运算。对于二进制来说,从高到低的每一位,将除数提升到当前位的权值(即,乘以2^k,等同于左移k位),如果此时被除数扔大于除数,就说明结果在这个位上商1。然后从被除数减掉除数提升后的值。遍历每一位,即为最终的结果。
因此,除法可以这样实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21int divi(int a, int b) {
int result = 0;
int length = sizeof(a);
bool flag = (a < b)||(b < 0);
a = (a < 0)? -a:a;
b = (b < 0)? -b:b;
// 避开正负数表示形式不同这一点
for(int i = sub(mul(length, 8), 1); i >= 0; i = sub(i, 1)){
if((a >> i) >= b){
// 这个地方使用 a 右移来比较,而不是将 b 左移的原因是因为:
// 有符号数在机器中以补码的形式表示,首位为1的字将被诠释为负数,导致结果错误
// 右移则可以回避这一点
result = add(result, 1 << i);
a = sub(a, b << i);
// (a >> i) >= b,意味着 b << i 不会导致首位为1,所以可以直接运算
}
}
return flag?-result:result;
}
这样做除法,得到的不是精确结果,而是将真正值进行向下舍入的结果。这是因为,对于 p/q,我们的运算会产生一个结果a,和直到最后都没能减尽的b。p除以q等于a余b,即p=q*a+b,p/q=a+b/q,b < q。即为a加一个小数,我们丢掉了这个小数,即向下舍入。(对于,负数结果来说,就成了向上舍入)。
需要注意的地方
需要注意的是,减法只适用于数是用定长方法表示时的情况。因为求逆元用到了两个数相加后溢出截断的原理。因此,对于不定长表示的数,例如Python中的整数表示,无法得到正确的结果。