反码加法循环进位与补码加法的理解

反码与补码的加法，从大一的时候学大学计算机基础，就很迷，逻辑上总是不能说服自己。最近自学计算机组成原理，又碰到这个问题。看到书中的一句话，突然豁然开朗，摘录如下：

"我常说：当你能衡量你正在谈论的东西并能用数字加又表达时，你才真的对它有了充分子解；而当你还不能衡量，也不能用数字表达时，你的了解就是肤浅的和不能令人满意的。尽管了解也许是认知的开始，但在思想上很难说你已经进入了科学的阶段。" -- Lord Kelvin

理解这个问题，首先引入位置表示法的定义：

位置表示法的定义

  • 一个 n 位的整数 N 会按下面的形式书写：

    a_{n-1}a_{n-2}\cdots a_ia_0

    • 其中 a_i(i=0, 1, \cdots, n-1)是与基数 b 的幂相乘的系数，即有下式成立

      N = a_{n-1}b^{n-1} + a_{n-2}b^{n-2} + \cdots + a_{0}b^{0}=\sum_{i=0}^{n-1}{a_i b^{i}}

    • 对于负数，则会在其前面加上负号 -，即 -a_{n-1}a_{n-2}\cdots,a_ia_0

    • 对于二进制，则 b=2

      • 例：十进制数 7，-7 表示为 4 位二制数分别为： 0111， -0111

  • 人们一般习惯在位置码上进行运算，但计算机不习惯，而且计算机底层不可能用负号来表示负数，更不可能让负号参与运算，因此引入了原码，反码和补码的概念

原码的定义

  • 原码的定义主要是为了引入符号位

  • 此时设一个n位的二进制数， 其按位置表示法为X，则其原码定义如下：

    [X]_{\text {原码}}=\left\{\begin{array}{cc} X & X \geqslant 0 \\ & \\ 2^{n-1}-X & X<0 \end{array}\right.

    • 对于用4位二进制表示的 -0111 来说，其原码计算为

      [-0111]_{原码} = 2^{4-1} - (-0111) = 1000 + 0111 = 1111

    • 需要注意的是，位置表示法中的负号也会参与运算

反码的定义

  • 反码的定义如下：

    [X]_{\text {反码}}=\left\{\begin{array}{cc} X & X \geqslant 0 \\ & \\ (2^{n}-1)+X & X<0 \end{array}\right.

    • 对于用4位二进制表示的 -0111 来说，其反码计算为

      [-0111]_{反码} = (2^{4}-1) + (-0111) = 1111 - 0111 = 1000

补码的定义

  • 补码的定义如下：

    [X]_{\text {补码}}=\left\{\begin{array}{cc} X & X \geqslant 0 \\ & \\ 2^{n}+X & X<0 \end{array}\right.

    • 对于用4位二进制表示的 -0111 来说，其补码计算为

      [-0111]_{补码} = 2^{4} + (-0111) = 10000 - 0111 = 1000

反码加法的循环进位推导

  • 设有两个n位的二进制数， 其按位置表示法分别为X， Y
    则其反码运算为 [X]_{\text {反码}} + [Y]_{\text {反码}}，为了取得与位置表示法运算等效的结果，需要满足下式

    [X]_{\text {反码}} + [Y]_{\text {反码}} = [X+Y]_{反码} \quad\quad (1)

    • 依据此式，即可进行分类讨论
  1. X \ge 0, Y\ge 0, 此时 (1) 式中左右两边显然成立
  2. X, Y 异号，此时：

[X]_{\text {反码}} + [Y]_{\text {反码}} = X + Y + 2^n - 1 \quad\quad (2)

  • 若 X+Y>=0， 则 [X+Y]_{反码} = X + Y
    • 此时 (2) 式会溢出，舍去其最高位（相当于减去2^n）， 再加上1，即可得到对应的结果，跟循环进位的操作匹配
  • 若 X+Y<0, 则 [X+Y]_{反码} = X + Y + 2^n -1，与 (2) 式对应
    • 由于 X+Y<0，此时(2) 式不会产生进位
  1. X<0, Y<0， 此时有

[X+Y]_{反码} = X + Y + 2^n - 1 \quad\quad (3)

而

[X]_{\text {反码}} + [Y]_{\text {反码}} = X + 2^n - 1 + Y + 2^n -1 =(X+Y+2^n-1) + 2^n - 1 \quad\quad (4)

  • 此时(4)式会溢出，将(4)式加 1 再舍掉进位 2^n，即可得到(3)式中的结果

综合 1， 2， 3 即可得到反码加法的循环进位规则

  • 补码加法与原码加法的推导基本相同，可得出补码加法与位置表示法的加法相同
  • 虽然推导时是按加法，但是由于 X, Y 没有预设符号，所以易证对减法也等效
  • 按照相同的推导方法，也可以得出用原码加减法时，负数符号位会参与运算，从而很难与原位置表示法的加减法对应起来
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容