02 Addition and Subtraction

加法就和我们手算一样，从右往左一位一位相加，需要进位的话，左边一位多加一。减法就是加上被减数的相反数，如果用补码表示，直接相加即可。

现在 CPU 最差情况只需要 $\lg_2 n$ 的复杂度就能完成加法的计算，其中 $n$ 是比特数。

下面是十进制 6 和 7 相加。

    111         7
+   110     +   6
-----------------
   1101        13

下面是直接做减法。

    111         7
-   110     -   6
-----------------
      1         1

如果使用补码表示 -6，那么就是加法操作。

  00111         7
+ 11010     +  -6
-----------------
  00001         1

什么时候发生溢出呢？如果加法的操作数的符号不一样，那么不会发生溢出，因为结果不会大于任意一个加数。

减法可以写成加上被减数的相反数，因此如果减法中的两个数符号一样，变成加法后两个操作数符号不一样，也就不会溢出。

如果两个操作数是 32 比特，而结果必须使用 33 比特来表示，此时就溢出了。当出现这种情况时，符号位是错误结果。当加两个整数时，结果是负数，那么就溢出了。反之亦然。

减法正好相反。一个正数减去一个负数，得到一个负数表示溢出了。反之，一个负数减去一个正数，得到一个正数表示溢出了。

下表整理了这几种情况。

操作	操作数 A	操作数 B	溢出结果
A+B	$\geq 0$	$\geq 0$	$<0$
A+B	$<0$	$<0$	$\geq 0$
A-B	$\geq 0$	$<0$	$<0$
A-B	$<0$	$\geq 0$	$\geq 0$

如果操作数是无符号数呢？通常，无符号数表示地址，会忽略溢出。

计算机中，执行加减法的模块我们称为算术逻辑单元（Arithmetic Logic Unit, ALU）。这个模块还可以执行逻辑运算，比如与、或。

对于 C 和 Java 而言，不会检查是否溢出，不过像 Ada 和 Fortran，需要知道是否溢出，所以 CPU 的设计者需要确定如何处理溢出。