Now Reading: 二进制算法中的进位(CARRY)标志和溢出(OVERFLOW)标志

Loading

二进制算法中的进位(CARRY)标志和溢出(OVERFLOW)标志

原文来自 Ian! D. Allen – [[email protected]]
(mailto:[email protected]) – www.idallen.com

在整数算术中,不要把“进位”标志和“溢出”标志混淆。每个标志都可以单独出现,也可以同时出现。CPU的ALU不关心或不知道你是在做有符号还是无符号的数学运算;ALU总是在做任何整数运算时适当地设置两个标志。ALU不知道有符号/无符号;ALU只是做二进制运算并适当地设置标志。你,作为程序员,必须知道在运算完成后检查哪个标志。

如果你的程序把一个字中的位当作无符号数,你必须注意看你的算术是否把进位标志置为1,表示结果是错误的。在做无符号数学运算时,你不关心溢出标志。(溢出标志只与有符号数有关,与无符号数无关。)

如果你的程序把一个字中的位当作二进制补码有符号值,你必须注意看你的算术是否把溢出标志置为1,表示结果是错误的。在做有符号的二进制补码数学运算时,你不关心进位标志。(进位标志只与无符号数有关,与有符号数无关。)

在无符号算术中,观察进位标志来检测错误。
在无符号算术中,溢出标志对你没有什么意义。
在有符号算术中,观察溢出标志来检测错误。
在有符号算术中,进位标志对你没有什么意义。

英语

不要把英语动词“to overflow” (溢出)和ALU中的“overflow flag” (溢出标志)混淆。动词“to overflow” (溢出)通常用来表示一些数学结果不适合可用的位数;它可以是整数运算、浮点运算或其他任何运算。 “Overflow flag” (溢出标志)是由ALU按照下面描述的方式特别设置的,并且它与通俗英语中的动词“to overflow” (溢出)不同。

在英语中,我们可能会说“二进制/整数运算溢出了结果可用的位数,导致进位标志被打开”。注意这种英语中动词“to overflow” (溢出)的用法等同于说“溢出标志被打开”。一个数学结果可以溢出(动词)可用的位数而不打开ALU的“overflow” (溢出)标志。

进位标志

在二进制/整数运算中打开进位标志的规则有两条:

  1. 如果两个数字相加导致最高有效位(最左边)相加产生了进位,则设置进位标志。
    1111 + 0001 = 0000 (进位标志被打开)
  2. 如果两个数字相减需要从最高有效位(最左边)借位,则也设置进位(借位)标志。
    0000 – 0001 = 1111 (进位标志被打开)

否则,进位标志被清零。

  • 0111 + 0001 = 1000 (进位标志被清零)
  • 1000 – 0001 = 0111 (进位标志被清零)

在无符号算术中,观察进位标志来检测错误。

在有符号算术中,进位标志不会告诉您任何有趣的信息。

溢出标志

二进制/整数运算中,打开溢出标志的规则有两条:

  1. 如果两个没有符号位的数相加,得到一个有符号位的数,那么“溢出”标志就会打开。
    0100 + 0100 = 1000 (溢出标志打开)
  2. 如果两个有符号位的数相加,得到一个没有符号位的数,那么“溢出”标志就会打开。
    1000 + 1000 = 0000 (溢出标志打开)

其他情况下,溢出标志就会关闭。

  • 0100 + 0001 = 0101 (溢出标志关闭)
  • 0110 + 1001 = 1111 (溢出标志关闭)
  • 1000 + 0001 = 1001 (溢出标志关闭)
  • 1100 + 1100 = 1000 (溢出标志关闭)

注意,你只需要看三个数的符号位(最左边的)来判断溢出标志是打开还是关闭。

如果你是做二进制补码(有符号)运算,溢出标志打开意味着答案是错误的——你把两个正数相加得到了一个负数,或者你把两个负数相加得到了一个正数。

如果你是做无符号运算,溢出标志没有意义,应该被忽略。

二进制补码检测错误的规则是通过检查结果的符号来确定。一个负数和一个正数相加不可能是错的,因为它们的和在两个加数之间。由于两个加数都在允许的范围内,而它们的和在它们之间,所以它也必须在范围内。混合符号的加法永远不会打开溢出标志。

在有符号运算中,观察溢出标志来检测错误。

在无符号运算中,溢出标志对你没有什么意义。

ALU如何计算溢出标志

这部分内容是可选阅读的。

有几种自动检测二进制补码运算中的溢出错误的方法(对于那些不喜欢手动检查方法的人)。这里有两种:

计算溢出标志:方法一

只有当两个同号的数相加得到一个异号的数时,才会发生溢出。所以,要检测溢出我们不关心除了符号位以外的任何位。忽略其他位。

有两个操作数和一个结果,我们有三个符号位(每个是1或0)要考虑,所以我们有8种可能的三位组合。只有其中两种情况被认为是溢出。

下面只是两个加数和结果的符号位:

加法标志位
    num1sign num2sign sumsign
   ---------------------------
        0 0 0
 *OVER* 0 0 1 (两个正数结果相加应该是正的)
        0 1 0
        0 1 1
        1 0 0
        1 0 1
 *OVER* 1 1 0 (两个正数结果相加应该是正的)
        1 1 1

我们可以重复同样的表格来表示减法。注意,减去一个正数和加上一个负数是一样的,所以触发溢出标志的条件是:

减法标志位
    num1sign num2sign sumsign
   ---------------------------
        0 0 0
        0 0 1
        0 1 0
 *OVER* 0 1 1 (减去一个负数等于加上一个正数)
 *OVER* 1 0 0 (减去一个负数等于加上一个正数)
        1 0 1
        1 1 0
        1 1 1

一台计算机可能包含一个小的逻辑门阵列,当满足上述四种溢出条件中的任何一种时,将溢出标志设置为“1” 。

人类只需要记住,当做有符号运算时,两个同号的数相加必须得到同号的结果,否则就发生了溢出。

计算溢出标志:方法二

当两个二进制值相加时,考虑进入最左边一位(进入符号位)的二进制进位和从最左边一位(符号位)出去的二进制进位。(从最左边的[符号]位出去的进位成为ALU中的进位标志。)

在二进制补码中,溢出可能发生在不是从最左列进位,而是当有一个进入它而没有匹配的出去时。也就是说,当有一个进入符号位但没有从符号位出去时,就会发生溢出。

溢出标志是进入符号位(如果有)的进位与从符号位(如果有)出去的进位的异或。如果进入不等于出去,就会发生溢出。

例子(2位有符号二进制补码数字):

  11
+ 01
 ===
  00
  • 进入是1
  • 出去是1
  • 1 XOR 1 = 没有溢出
  01
+ 01
 ===
  10
  • 进入是1
  • 出去是0
  • 1 XOR 0 = 溢出!
  11
+ 10
 ===
  01
  • 进入是0
  • 出去是1
  • 0 XOR 1 = 溢出!
  10
+ 10
 ===
  11
  • 进入是0
  • 出去是0
  • 0 XOR 0 = 没有溢出

注意,这种异或方法只适用于二进制进入符号的进位。如果你使用十六进制数字、十进制数字或八进制数字,你也会有进位;但是,这种非二进制的进位不会影响符号,你不能用这种非二进制的进位和出去的进位进行异或。

十六进制加法例子(显示异或对十六进制进位不起作用):

  8Ah
+ 8Ah
 ====
  14h

由于A+A产生的十六进制进位为1,它不会影响符号位。如果你用二进制做运算,你会看到没有任何进入符号位的进位;但是,有从符号位出去的进位。因此,上面的例子会使溢出标志打开。(这个例子把两个负数相加得到了一个正数。)

svg

What do you think?

Show comments / Leave a comment

Leave a reply

Loading
svg
Quick Navigation
  • 01

    二进制算法中的进位(CARRY)标志和溢出(OVERFLOW)标志