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

原文发布于我的github 主页

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

"我常说：当你能衡量你正在谈论的东西并能用数字加又表达时，你才真的对它有了充分子解；而当你还不能衡量，也不能用数字表达时，你的了解就是肤浅的和不能令人满意的。尽管了解也许是认知的开始，但在思想上很难说你已经进入了科学的阶段。" -- 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)$
- 依据此式，即可进行分类讨论

$X \ge 0, Y\ge 0$ , 此时 (1) 式中左右两边显然成立
$X, Y$ 异号，此时：

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

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

$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$ 没有预设符号，所以易证对减法也等效
按照相同的推导方法，也可以得出用原码加减法时，负数符号位会参与运算，从而很难与原位置表示法的加减法对应起来

最后编辑于：2021.04.04 09:40:37

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,258评论 6赞 498
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,335评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,225评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,126评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,140评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,098评论 1赞 295
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,018评论 3赞 417
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,857评论 0赞 273
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,298评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,518评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,678评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,400评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,993评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,638评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,801评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,661评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,558评论 2赞 352