3.1　无符号整数的加减

计算机是在二进制数字系统中执行算术运算的。这些运算乍一看似乎不容易，但是如果你还记得手动演算十进制数的细节，二进制运算其实也不难。由于现在大多数人都使用计算器，让我们先回顾一下手动演算加法的所有步骤。然后再编写一个算法来完成二进制和十六进制的加法和减法。

注意

大多数计算机架构都提供了用于其他数字系统的算术指令，但这些指令比较特殊，我们不在本书中考虑。

3.1.1　十进制数字系统的加法

我们先将讨论限制在两位数的十进制加法。考虑两个2位十进制数， x =67和 y =79。在纸上对这两个数手动相加的过程如下：

从右开始，先把个位上的两个十进制数码相加。7 + 9 = 16，相加的结果比10多6。我们将6放在和的个位上并向十位进1。

然后，把十位上的3个十进制数码相加：1（来自个位的进位）+6+7。相加的结果比10多4，我们将4放在和的十位，然后记下最终的进位1。因为我们只使用了两位数，所以这里没有百位。

下列算法给出了两个十进制整数 x 和 y 相加的过程。在该算法中， x _i 和 y _i 分别是 x 和 y 的第 i 位数码（从右到左计数）：

Let carry = 0
Repeat for each i = 0,...,(n - 1)      // starting in ones place
    sumi = (xi + yi + carryi) % 10       // remainder
    carryi+1 = (xi + yi + carryi) / 10    // integer division

这种算法之所以有效，是因为我们在书写数字时使用了位置记数法——一个数码向左移动一个位置要多计数10倍。从当前位置向左的进位总是0或1。

我们在/和%运算中使用10，是因为在十进制数字系统中有10个数位：0，1，2，…，9。因为我们是在一个 N 位数制系统（ N -digit system）中工作，所以我们将结果限制在 N 个数码。最终进位要么是0，要么是1，连同 N 位总和作为最终结果。

3.1.2　十进制数字系统的减法

让我们转向减法运算。正如十进制数字系统中的减法，有时你必须从被减数（被减去的数字）的下一个高位数借位。我们使用先前的数字（67和79）来做减法。整个运算过程将分步演示。“演草”结果在两个数字上方的借位行（borrow row）中显示。

首先，我们需要从十位借1，将其与个位的7相加；然后从17中减去9，得到8：

接着，需要从已有的两位数之外再借位，我们通过在“进位”位置放置一个1来标记，十位上变成了15，然后从中减去7：

这个过程显示在下面的算法中，其中 x 是被减数， y 是从中被减去的数（减数）。如果在这个算法结束时borrow为1，则表明你不得不从两个值的 N 位数之外借位，所以 N 位数的结果是不正确的。尽管名为进位标志，但它的目的是表明运算结果何时不适合数据类型的位数。因此，进位标志包含的就是减法运算完成时的借位值（超出数据类型的大小）。

Let borrow = 0
Repeat for i = 0,···,(N − 1)
  ➊ If yi ≤ xi
         Let differencei = xi − yi
     Else
       ➋ Let j = i + 1
       ➌ While (xj = 0) and (j < N)
              Add 1 to j
       ➍ If j = N
           ➎ Let borrow = 1
              Subtract 1 from j
              Add 10 to xj
       ➏ While j > i
              Subtract 1 from xj
              Subtract 1 from j
              Add 10 to xj
           ➐ Let differencei = xi – yi

该算法并不像看起来那么复杂（但是我花了很长时间才弄明白！）。如果相同数位上的被减数等于或大于减数➊，就将该数位相减。否则，需要向左边借位➋。如果我们试图借位的下一位是0，那么继续向左移动，直到我们找到某一个非0位，或是到达数字的最左端➌。对于后一种情况➍，我们通过将borrow设置为1来表明这一点➎。

从左借位之后，我们再回到要处理的数位➏并执行减法➐。当你在纸上演算减法时，这一切都是在你脑子里自动完成的，但在二进制和十六进制系统中，可能就没那么直观了。这里，我把中间借位写成了十进制。

如果你理解上有困难，也不要担心。并不是非得弄明白这个算法才能阅读本书。但我认为，它可以帮助你学习如何为其他计算问题开发算法。将日常操作转化为编程语言所使用的逻辑语句往往是一项困难的任务。

3.1.3　无符号二进制整数的加法和减法

在本节中，你将学习无符号二进制整数的加法和减法，但是在此之前，请仔细阅读表 3-1，尤其是其中的二进制位模式。一开始你可能记不住这个表，没关系，当你接触二进制和十六进制数字系统一段时间后，你会很自然地认为10、a或1010是相同的数字，只是数字系统不同而已。

现在你已经熟悉了表3-1，让我们来讨论一下无符号整数。同时别忘了，只要是数值，不管是十进制、十六进制还是二进制，它们在数学上都是等价的。然而，我们可能好奇，当计算机执行二进制算术时能否得到与我们执行十进制算术时同样的结果。下面让我们来仔细观察一些具体的运算。

二进制加法

在下列例子中，我们使用4位值。首先，考虑两个无符号整数2和4的加法：

十进制数2和4表示为二进制分别为0010和0100。进位标志CF等于0，因为两个数相加的结果依然为4位。和十进制加法一样，我们对相同位进行相加（以二进制和十六进制显示，不过进位仅以二进制显示）。

接下来，考虑两个更大的整数，依然使用4位的存储空间。我们将两个无符号整数4和14相加：

在本例中，进位标志等于1，相加的结果超出了为存储整数准备的4位存储空间，因此产生了错误。如果我们将进位标志纳入结果，就得到了一个5位值，即10010 ₂ = 18 ₁₀ ，这个结果是正确的。在编写软件时必须要考虑进位标志。

二进制减法

现在，让我们计算4减14，或0100减1110：

CPU通过将进位标志设置为1，表明必须从4位之外借位，这意味着减法的结果是错误的。

这些4位算术示例可以推广到任意大小的计算机算术。将两个数相加后，如果没有最终进位，进位标志会被设置为0；如果有最终进位，则被设置为1。如果不需要从“外部”借位，减法将把进位标志设置为0；如果需要借位，则设置为1。每次执行加法或减法运算时，CPU总是将rflags寄存器中的CF标志相应地设置为0或1。当没有进位时，CPU会主动将CF设置为0，不管其中先前保存的是什么值。

只要结果符合用于计算的数据类型的位数，就是正确的。如果结果有误，无论是因为加法需要进位还是减法需要借位，都会通过将进位标志设置为1来记录此错误。 cFG2nf2QWsdH8YHynaL9AGlIjUNY8ABOpz7Jk/PYGlSNnjowuZncpItRKyEcW6MT