如何实现加法和减法

以前在面试候选人的时候，我总是喜欢先问一个问题：

-1 的补码是多少？

这么多次面试下来，结果令我很失望，绝大多数候选人，只是记住了大学时候学到的：取反加 1，接着就给出了 10000000001 这种错得离谱答案。

确实，二进制是一个容易被忽略的东西，你不了解它并不会导致你写不出业务代码，也不会让你觉得很沮丧。即使你写过 if (~arr.indexOf(x)) 这种类似的代码，但是这也不代表你就非常理解了二进制的兴趣。

本文的目的主要是为了揭示在计算机中，整数加法和减法是如何被表示的。有一定经验的人应该都清楚，CPU 其实就是一个非常复杂的集成电路，而集成电路的最小单位就是各种逻辑门。想必你也听过了类似与门，或门，与非门，或非门等等逻辑门的名称，但是并没有一个叫做 加法门，减法门的东西。所以可以联想到加法减法的实现最终是由这些逻辑门组成的。我们在知道如何加法运算后，接着会看如何用补码来计算减法。

加法

基本概念

首先需要明确的是，我们下面讨论的是二进制加法，它的真值表很简单，就下面 4 种情况：

0 x 0 = 0， 0 x 1 = 1 x 0 = 1，1 x 1 = 0

注意到它的真值表其实和 或门比较类似，只不过或门中，1 x 1 = 1，而它是 0。 同时它的真值表和 与非门 也很相似，也就是：0 x 0 = 1, 0 x 1 = 1 x 0 = 1, 1 x 1 = 0。他们的区别在 0 x 0 的结果上。

所以我们只要再把它们两个的结果，再取一次与，就得到了“加法”的真值。 看上去很复杂，经过了 四次转化（与门，或门，与非门 2 次），但因为这个逻辑实在太常见，所以也有一个专门的称呼叫做：异或门(XOR)。对就是我们非常熟悉的 ^

不过这里可以忽略了进位的问题，我们接下来单独再分析进位的情况

显而易见，只有 a 和 b 同时为 1 的时候才会进位。这能否让你联想到它的真值表和 与门(AND) 的真值表一模一样呢？ 所以呢，加法的本质其实分为了两步：XOR 得到相加不进位的结果，AND 得到进位不相加的结果。

处理进位

但这只是一个模糊的说法，因为最低位进位后，会将它交给下一个高位，这个时候参与加法的就不是之前的 2 个数，还是 3 个了。 具体在电路的实现的时候，会有所谓的半加器和全加器来组合完成这个过程。但好在我们不是电工，不需要太在乎这到底表示了什么，我们可以用编程语言的思路来模拟这个过程。

假设有一个函数 f，它的作用就是上面提到的，接受两个参数，返回当前位的结果， 和进位

function f(a, b) {
  return [a ^ b, a & b];
}

接着，因为在进入高位的时候还要计算上一次得到的进位，所以如果以 11 + 01 为例的话，就是这样。

const [r1, c1] = f(1, 1); // r1 = 0, c1 = 1

const [r2, c2] = f(1, 0); // r2 = 1, c2 = 0
const [r3, c3] = f(r2, c1); // r3 = 0. c3 = 1

const [r4, c4] = f(0, c3); // r4 = 1, c4 = 0

最后结果 r4r3r1 => 100

看上去似乎挺复杂的，一个简单的 2 位加法就要写 4 个表达式，如果改成 8 位的话，脑子都写炸了 🤯。好在上面的写法只是最底层的电路的思考方式，我们在使用计算机语言的时候，其实可以更加抽象的解决这个问题。

现在来仔细看，相加不进位 s 和进位不相加 c 这两个数字，c 本质上还是一个被加数。继续用上面 11 + 01 的例子，11 & 01 = 01，01 会给下一个高位使用，也就是说 01 其实表示了一个的 010 被加数。同时 11 ^ 01 = 10 ，所以我们再分别计算 s 和 c 10 ^ 10 = 00, 10 & 10 = 10。接着就是 00 ^ (10 < 1) = 100, 000 & 000 = 0。 因为这个时候进位为 0，所以不再需要计算算下去，最终结果就是 100，所以我们可以通过几行代码来实现加法。

function sum(a, b) {
  if (!b) return a;
  return sum(a ^ b, (a & b) << 1);
}

减法

补码

减法的难点在于借位。加法的时候，我们可以按顺序的从最低位往最高位计算，把进位留给下一位就行了。但是如果引入进位的话，就需要提前去读取下一位，这还算好办。如果出现连续结尾，比如十进制加法的中 10000 - 9 的话，这就让借位在低层运算中基本上不可能实现，因为这个时候还没有引入内存的概念。就因为这个，补码出现了。

首先，需要强调的是，因为翻译的问题，补码的英文其实是 two’s complement，字面意思是 2 的补数。同样的，其实还存在 10 的补数。接下来我们将通过 10 的补数来了解减法和加法的关系。

考虑下面这个例子：253 - 176 = 77，我们先求用 999 减去减数，999 - 176 = 823。接下来再把被减数和结果相加得到 253 + 823 = 1076。接着再把它加 1 并减去 1000 就得到最后的差值。同理，如果减数是 n 位数的话，它的补数就是 n 个 9 减去它的值。在这里 253 - 176 = 253 + 999 - 176 + 1 - 1000 = 77。而 176 的补数就是好 823 + 1 = 824 换句话说我们可以通过引入补数的概念，把减法转成一定不会出现借位的加减法运算，在一定程度上已经解决了上面提到借位难以实现的问题。

不过呢，这里忽略了另一种情况，如果我们改成 176 - 253 = -77 的话。上面的步骤如果还是按之前一样：

1. 999 - 253 = 746
2. 746 + 176 = 922
3. 922 - 999 = ???

我们可以很轻松地将它们的顺序互调，改成 999 - 922 = 77，接着再加上负号变成 -77。而加法器本身，在判断是否需要作出这些转换的时候，依赖两个标记位：SUB 和 CO。分别代表减法和进位的标记位。正常情况下，补数加上被减数应该是大于当前最高位的，就像 253 + 823 > 999 一样，所以会发生进位，如果没有发生，并且 SUB 标记被设置的话，就说明结果将会是负数。

接下来，我们再思考下二进制和十进制的区别，就能发现一个有意思的事情：二进制里最高位都是 1，它减去任何一个数的效果，就是按位取反，接着再 + 1 ，又因为在语言的实现中，天生具备了自动截断的功能，所以最后的那个减法是不需要去另外编码的，也就得到了最终的补码。这也是为什么总是会提到取反加一的原因。

通过上面的例子，也能理解为什么在语言中普遍使用最高位为 1 来表示负数了。以一个 4 位的例子来看：2 - 7 = 0010 - 0111 = 0010 + ~0111 + 1 = 0010 + 1001 = 1011 = -5。真正意义上地将减法变成了加法

换句话说：a - b = a + ~b + 1。所以减法的实现非常简单

function difference(a, b) {
  return sum(a, ~b + 1);
}

排列

我们将 4 位的二进制排开的话，会得到：

1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111,
0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,

分别对应

-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7;

如果我们暂且不考虑符号的话，就能发现它具有循环有序的性质。最大的数 7 的下一个是 8，但是要加上符号。通过这个性质，我们应该能够非常快地打出，-1 的补码就是全 1，这是毋庸置疑的。

题外话

虽然说，我们可以通过上面的方式模拟加减法，但是这不代表你在实际编程中应该使用它们。现代 CPU 再已经内置了加法器甚至减法器，所以根本不需要特意用位运算去模拟这个过程，本文主要还是为了揭示加法减法之间的关系。另外如果是浮点数的话，会变得更加特殊。

总结

1. 加法分为两步，异或表示只加不进位，与表示只进位不加
2. 因为借位的困难，减法可以通过补码的技巧来实现加法
3. 最高位是 1 表示负数，可以极大的简化减法的实现。