如何用位运算实现加减乘除？

Satklomi · 2021-08-12 08:34:18 · 个人记录

众所周知，我们所使用的加减乘除，一般都是直接一个命令完成的：

int a = 1;
int b = 2;
System.out.println(a + b);

就这一个加号，计算机要费多大劲呢？

1.我们是如何实现十进制加法的？

先抛开计算机不谈，我们是怎么实现的加法，想必大家都自认为很熟悉了：列竖式，每位相加，计算进位，完成。

一般每位相加和算进位是一起进行的，那如果分开呢？

举个栗子：27+13

首先，每一位相加：2+1=3, 7+3=0 ，合起来就是 30 。

然后，进位：进了一位，所以是 10 。

最后加起来： 30+10=40，也是 27+13 的结果。

那么，放到计算机里，也合适吗？

2.照猫画虎，实现二进制加法

那么，不还是一样，每位相加算进位吗？

只是在二进制里，每一步都变得简单了很多。

我们可以再来个栗子： 2+3 。

首先转二进制：2=(10)_2， 3=(11)_2 。

然后相加：0+1=1 ， 1+1=0，从“二位”往“四位”进一位，合起来是 01 。

进位：1+1=0 从“二位”进到“四位”，进位是 100。

用 100+01=101 ，而 (101)_2=5 ，2+3 也等于 5 。

然而，这和位运算有什么关系？

3.如何用位运算来表达

不着急，先来看看不进位加法的运算表：

等等？

这不是和异或的运算表……

一模一样吗？

也就是说，不进位加法，实际上就是异或！

那么，进位呢？

一样看个表：（0表示不进，1表示进）

而这也是与的运算表。

由于是进位，所以实际上还要左移一位才算进。

那再用异或和与实操一遍 2+3 。

3.加减法，end

那么，加法我们就会了。

至于减法，由我们在小学二年级初中一年级学到的知识可知，a-b=a+(-b) ，而 -b= (\text{not }b) + 1。

也就是说，减法可以完全用加法实现。

放个代码：

int add(int a, int b) {//加法
    int sum = a ^ b; //和，100行
    int carry = (a & b) << 1; //进位
    while (carry) { //直到进位=0
        int osum = sum;
        sum = sum ^ carry; // 同样的结构再来一遍
        carry = (osum & carry) << 1;
    }
    return sum;//没有进位了，sum就是结果
}
int sub(int a, int b) {//减法
    int negate_b = add(~b, 1); //使用纯位运算实现的加法
    return add(a, negate_b); //保证了减法的位运算实现性（？）
}

4.乘法，最容易想到版

那么，由于乘法是加法的简便运算，所以完全可以通过迭代来实现乘法。

思路清晰，直接coding。

int mul(int a, int b) {//乘法
    int abs_a = a > 0 ? a : add(~a, 1);//保证纯位运算
    int abs_b = b > 0 ? b : add(~b, 1);
    int product = 0, count = 0;//已累加的次数与乘积
    while (count < abs_b) {//累加a
        product = add(product, abs_a);
        count = add(count, 1);//同样保证纯位运算
    }
    //随后确定符号
    if ((a ^ b) < 0) {//若a与b一正一负，则前面一堆0和1会异或成1导致结果小于0
        product = add(~product, 1);//取负
    }
    return product;//完成
}

5.乘法，优化版

很明显，在 b 较大的情况下，上述算法即使有位运算的速度I buff加成，但是受到一个缓慢III debuff的情况下还是会很慢。

那么，整个过程可以怎么搞呢？

简单看一下：

由此可以归纳：