深入理解计算机系统 - 信息的表示和处理

在这一章，我们会了解表示基本数据类型的方法，机器级指令如何操作这样的数据，编译器如何将C程序翻译成这样的指令。接着会研究几种实现处理器的方法，帮助我们更好地了解硬件资源如何被用来执行命令。在深入了解了如何表示和执行应用程序之后，我们将学会一些技巧，用来写出安全、可靠且充分利用计算机资源的程序

信息的表示和处理

现代计算机存储和处理的信息以二值信号表示。这些二进制数字，或者称为位(bit)，形成了数字革命的基础。以前，大家熟悉并使用了1000多年的十进制数字起源于印度，在12世纪被阿拉伯数学家改进，并在13世纪被意大利数学家Leonardo Pisano(更为大家熟知的名字是Fibonacci)带到西方。

对于有10个手指的人类，使用十进制表示法是很自然的事情，但是当构造存储和处理信息的机器时，二进制值工作得更好。其可以更容易地被表示、存储和传输，例如可以表示为卡片上有没有孔洞、导线上的高电压或低电压，或者顺时针或逆时针的磁场。对二值信号进行存储和执行计算的电子电路非常简单可靠，制造商能够在一个单独的硅片上集成数百万甚至数十亿个这样的电路。

单个的位不是很有用，然而当把位组合在一起，再加上某种解释(interpretation)，就可以赋予它们含义，并用来表示任何有限集合的元素。比如，使用一个二进制数字系统，我们能够用位组来编码非负数。通过标准的字符码，我们能够对文档中的字母和符号进行编码。

我们研究三种最重要的数字表示：

1. 无符号(unsigned)编码：表示大于或等于0的数字
2. 补码(two’s-complement)编码：表示有符号整数
3. 浮点数(floating-point)编码：表示实数的科学计数法的以2为基数的版本

计算机的表示法是用有限数量的位来对一个数字编码，所以如果结果太大以至不能表示时，某些运算就会溢出(overflow)。例如，32位的int类型不能容纳200*300*400*500的结果

浮点运算有不同的数学属性，当其溢出时，会产生特殊的值+∞，由于表示的精度有限，浮点运算是不可结合的，例如，在很多机器上，C表达式\((3.14+1e20)-1e20\)求得的值会是0.0，而\(3.14+(1e20-1e20)\)求得的值会是3.14

这种情况在整数运算中不会出现，因为整数表示的范围虽然小，但是是精确的；而浮点数虽然可以编码较大的数值范围，但是这种表示只是近似的

为了使编写的程序能在全部数值范围内正确工作，而且具有可以跨越不同机器、操作系统和编译器组合的可移植性，了解可以表示的数字值的范围、位级表示、算术运算的属性是非常重要的

信息存储

大多数计算机使用8位的块，或者字节(byte)，作为最小的可寻址的内存单位，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称为虚拟内存(virtual address space)。这个虚拟地址空间只是一个展现给机器级程序的概念性映像，实际的实现结合了动态随机访问存储器(DRAM)、闪存、磁盘存储器、特殊硬件以及操作系统，为程序提供一个看上去统一的字节数组。

十六进制表示法

一个字节由8位组成。在二进制标识法中，它的值域是00000000 ~ 11111111，看成十进制整数，就是0 ~ 255。两种符号标识发对于描述位模式都不是很方便。二进制标识发太冗长，十进制表示法与位模式的互相转换很麻烦。替代的方法是使用十六进制(hexadecimal)数来表示位模式。十六进制(简写为”hex”)使用数字0 ~ 9以及字符A ~ F来表示16个可能的值。用十六进制来书写，一个字节的值域为00 ~ FF

在C语言中，以Ox或OX开头的数字常量常被认为是十六进制的值。字符A ~ F既可以是大写，也可以是小写。例如，我们可以将数字FA1D37B(16进制)写作OxFA1D37B，或者Oxfa1d37b，甚至是大小写混合，在这本书里，是用C表示法来表示十六进制的

编写机器级程序的一个常见任务就是在位模式的十进制、二进制和十六进制表示之间人工转换。二进制和十六进制之间的转换比较简单直接，因为可以一次执行一个十六进制数字的转换。

比如，一个数字0x173A4C，可以通过展开每个十六进制数字，将其转换成二进制：

1:0001 7:0111 3:0011 A:1010 4:0100 C:1100

这样就得到了二进制表示：000101110011101001001100

反过来，如果给定了一个二进制数字1111001010110110110011，可以通过首先把它分为每4位一组来转换为十六进制。不过要注意，如果总位数不是4的倍数，最左边的一组可以少于4位，前面用0补足

11:3 1100:C 1010:A 1101:D 1011:B 0011:3

字数据大小

每台计算机都有一个字长(word size)，指明指针数据的标称大小(nominal size)。因为虚拟地址是以这样的一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。也就是说，对于以字长为w位的机器而言，虚拟地址的范围为\(0\)到\(2^w-1\)，程序最多访问\(2^w\)个字节

最近这些年，出现了大规模从32位字长机器到64位字长机器的迁移。32位字长限制虚拟地址空间位4千兆字节(写作4GB)，而扩展到64位字长使得虚拟地址空间为16EB，大约是\(1.84*10^{19}\)字节

大多数64位机器也可以运行为32位机器编译的程序，这是一种向后兼容，将程序称为”32位程序”或”64位程序”时，区别在于该程序是如何编译的，而不是其运行的机器类型。

为了避免由于依赖”典型”大小和不同编译器设置带来的奇怪行为，ISO C99引入了一类数据类型，其数据大小是固定的，不随编译器和机器设置而变化。其中就有int32_t和int64_t，分别位4个字节和8个字节，使用确定大小的整数类型是程序员准确控制数据表示的最佳途径

大部分数据类型都编码为有符号数值，除非有前缀关键字unsigned或对确定大小的数据类型使用了特定的无符号声明。对关键字的顺序以及包括还是省略可选关键字来说，C语言允许存在多种形式，比如，这里所有的声明都是一个意思：

• unsigned long
• unsigned long int
• long unsigned
• long unsigned int

上面的图中还展示了指针(图中使用了一个被声明为类型”char * “的变量)，使用程序的全字长

在C中，任何数据类型T，声明T *p;，表明p是一个指针变量，指向一个类型为T的对象。例如char *p就将一个指针声明为指向一个char类型的变量

程序员应该力图使他们的程序在不同的机器和编译器上可移植，可移植的一个方面就是使程序对不同数据类型的确切大小不敏感。许多程序编写都假设为上面图中32位程序的字节分配。随着64位机器的日益普及，在将这些程序移植到新机器上时，比如有许多程序员假设一个声明为int类型的程序对象能被用来存储一个指针。这在大多数32位的机器上能正常功能，但是在一台64位的机器上却会导致问题。

寻址和字节顺序

对于跨越多字节的程序对象，我们必须建立两个规则：这个对象的地址是什么，以及在内存中如何排列这些字节。在几乎所有机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。例如，假设一个类型为int的变量x的地址为0x100，也就是说，地址表达式&x的值为0x100。那么，如果x为32位表示，x的4个字节将被存储在内存的0x100、0x101、0x102和0x103位置

排列表示一个对象的字节有两个通用的规则，小端法(little endian)和大端法(big endian)，分别表示在内存中按照最低有效字节到最高有效字节顺寻存储和从最高有效字节到最低有效字节的顺序存储。

假设变量x的类型位int，位于地址0x100处，它的十六进制值为0x01234567。地址范围0x100 ~ 0x103的字节顺序依赖于机器的类型：

在字0x01234567中，高位字节的十六进制位0x01，而低位字节值为0x67

大多数Intel兼容机都只用小端模式，另一方面，IBM和Oracle的大多数机器则是按照大端模式操作。许多比较新的微处理器使用的是双端法(bi-endian)，也就是说可以把它们配置成作为打断或者小段的机器运行。实际情况中，一旦选择了特定操作系统，字节顺序就固定了。选择何种字节顺序没有技术上的理由，只要选择了一种规则并且一直遵循，对于哪种字节排序的选择都是任意的。

对于大多数应用程序员来说，其机器所使用的字节顺序是完全不可见的。不过有时候，字节顺序会成为问题。在不同类型的机器之间通过网络传送二进制数据时，一个常见的问题是当小端法机器产生的数据被发送到大端法机器或者反过来时，接受程序发现里面的字节成了反序的。为了避免这类问题，网络应用程序的代码编写必须遵守已建立的关于字节顺序的规则，以确保发送方机器将它的内部表示转换成网络标准，而接收方机器则将网络标准转换为它的内部表示

当阅读小端法机器生成的机器级程序表示时，经常会将字节按照相反的顺序显示。因为按照小端法，最低有效位在右边，所以会从右边开始排，这值得注意

还有一种情况是当编写规避正常的类型系统的程序时。在C语言中，可以通过强制类型转换(cast)或联合(union)来允许一种数据引用一个对象，而这种数据类型与创建这个对象时定义的数据类型不同。虽然很多应用编程都强烈不推荐这种编码技巧，但是它们对系统及编程来说是非常有用的

看这段代码：

# include <stdio.h>
typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len){
    size_t i;
    for (i = 0; i < len; i++)
        printf(" %.2x", start[i]);
    printf("\n");
}

void show_int(int x){
    show_bytes((byte_pointer) &x, sizeof(int));
}

void show_float(float x){
    show_bytes((byte_pointer) &x, sizeof(float));
}

void show_pointer(void *x){
    show_bytes((byte_pointer) &x, sizeof(void *))
}

这段代码使用强制类型转换来访问和打印不同程序对象的字节表示。我们用typedef将数据类型byte_pointer定义为一个指向类型为unsigned char的对象的指针。这样一个字节指针引用一个字节序列，每个字节都被认为是一个非负整数。上面的代码中show_bytes函数传入了一个字节序列的地址(传入了字节指针和字节数)，字节数的数据类型是size_t，表示数据结构大小的首选数据类型。show_bytes打印出每个以十六进制表示的字节。C格式化指令%.2x表明整数必须用至少两个数字的十六进制格式输出

show_bytes之后的三个函数分别用show_bytes来输出了类型为int、float和void *的C程序对象的字节表示。在调用show_bytes时，传入的是被强制转换为unsigned char *类型的指向它们参数x的指针&x，这种强制类型转换告诉编译器，程序应该把这个指针看成指向一个字节序列，而不是指向一个原始数据类型的对象。然后，这个指针会被看成是对象使用的最低字节地址。注意这里使用了sizeof运算符来确定对象使用的字节数。一般来说，sizeof(T)返回存储一个类型为T的对象锁需要的字节数。使用sizeof而不是固定值，也有利于之后程序的移植。

上图是在不同的机器/操作系统调用前面代码的输出结果，可以看到，除了数值类型因为小端法与大端法造成的字节输出顺序的不同之外，指针值也是完全不同的，不同的机器/操作系统使用不同的存储分配规则。另一个值得注意的特性是上面除了Linux 64使用8字节地址之外，其他操作系统都是使用4字节地址。

C语言小技巧：typeof声明提供了一种给数据类型命名的方式。这能极大改善代码的可读性，因为深度嵌套的类型声明很难读懂；·printf(以及fprintf和sprintf)提供了一种打印信息的方式，在第一个参数格式串(format string)里，每个以%开始的字符序列都表示如何格式化下一个参数，比较典型的有%d是输出一个十进制整数，而%c是输出一个字符，其编码由参数给出，指定确定大小数据类型的格式，如int32_t，要更复杂一些，之后会提到

在函数show_bytes中，我们看到指针和数组之间紧密的关系，之后会详细介绍这一点。在代码中，我们还可以看到取地址运算符&，这分别创建了指向三种不同类型的x的指针，在这里三个指针的类型分别为int*、float*和void **(数据类型void *是一种特殊类型的指针，没有相关联的类型信息)

强制类型转换运算符可以将一种数据类型转换为另一种，比如(byte_pointer)&x表明无论指针&x以前是什么类型，它现在就是一个指向数据类型为unsigned char的指针。这里给出的强制类型转换不会改变真实的指针，它们只是告诉编译器以新的数据类型来看代被指向的数据。

表示字符串

C语言中字符串被编码为一个以null(其值为0)字符结尾的字符数组。每个字符都由某个标准编码来表示，最常见的是ASCII字符码。如果我们以参数"12345"(包括终止符)来运行上面的代码，我们得到的结果是31 32 33 34 35 00，注意，十进制数字x的ASCII码正好是0x3x，而终止字节的十六进制表示为0x00。在使用ASCII码作为字符码的任何系统上都得到相同的效果，与字节顺序喝字大小规则无关。所以，文本数据比二进制数据具有更强的平台独立性。

布尔代数简介

二进制是计算机编码、存储和操作信息的核心。源于1850年前后乔治布尔(George Boole，1815-1864)的工作，产生了丰富的数学知识体系，所以也被称为布尔代数(Boolean algebra)。布尔注意到通过将逻辑值TRUE(真)和FALSE(假)编码为二进制值1和0，能够设计出一种代数，以研究逻辑推理的基本原则。

布尔代数在数字系统的设计和分析中扮演着重要的角色，四个布尔运算符(&，|，^，~)可以扩展到位向量的运算，位向量就是固定长度为w、由0和1组成的串。位向量的运算可以定义成参数的每个对应元素之间的运算。假如a和b分别代表两个长度均为w的位向量，我们将a&b也定义为一个长度为w的位向量，其中第i个元素等于ai&bi，0<=i<w。可以用类似的方式将运算

、^和~扩展到位向量上。

比如w=4，参数a=[0110]，b=[1100]，那么4种运算a&b、a

b、a^b和~b分别得到以下结果

这里有一道练习题：

答案：10010110、10101010、01000001、01111101、00111100

布尔代数和整数运算有很多相似之处，比如，乘法对加法的分配律，写为a*(b+c)=(a*b)+(a*c)，而布尔运算&对|的分配律，写为a&(b|c)=(a&b)|(a&c)。此外，布尔运算|对&也有分配律，写为a|(b&c)=(a|b)&(a|c)

当考虑长度为w的位向量上的^，&和~运算时，会得到一种不同的数学形式，我们称之为布尔环(Boolean ring)，布尔环与整数运算有很多相同的属性。比如，整数运算的一个属性是每个值x都有一个加法逆元(additive inverse)-x使得x+(-x)=0。布尔环也有类似的属性，这里的”加法”运算是^，不过这时每个元素的加法逆元是它自己本身。也就是说，对于任何值a来说，a^a=0，这里我们用0来表示全0的位向量。可以看到对单个位来说这是成立的，即0^0=1^1=0，将这个扩展到位向量也是成立的。当我们重新排列组合顺序，这个属性也仍然成立，因此有(a^b)^a=b¹。这个属性会引起一些很有趣的结果和聪明的技巧，在后面的练习题中会探讨。

位向量一个很有用的应用就是表示有限集合。比如我们用位向量a:[01101001]表示集合A={0,3,5,6}，而b:[01010101]表示集合B={0,2,4,6}(注意我们是从位向量的右边往左边看)。使用这种编码集合的方法，布尔运算|和&分别对应于集合的并和交，而~对应集合的补集。比如在前面的例子里，运算a&b得到位向量[01000001]，而A∩B={0，6}，在大量实际应用中，我们都能看到用位向量来对集合编码，在之后也会接触到。

这里有一道练习题

答案：

A.~黑色 = 白色，~红色 = 蓝绿色，~蓝色 = 黄色，~红紫色 = 绿色，反过来也是一样

B.蓝色|绿色 = 001|010 = 011 = 蓝绿色，黄色&蓝绿色 = 110&011 = 010 = 绿色，红色^红紫色 = 100^101 = 001 = 蓝色

C语言中的位级运算

C语言的一个很有用的特性就是它支持按位布尔运算。事实上，我们在布尔运算中使用的那些符号就是C语言所使用的：

|就是OR(或)，&就是AND(与)，~就是NOT(取反)，^就是EXCLUSIVE-OR(异或)。这些运算能运用到任何”整型”的数据类型上，这里有一张图，是一些对char数据类型表达式求值的例子：

正如图上表示的那样，确定一个位级表达式的结果最好的方法，就是将十六进制的参数扩展成二进制表示并执行二进制运算，然后转换回十六进制

这里还有几道练习题：

答案：

第一步：a a^b

第二步：b a^b

第三步：b a

答案：

Ａ.从first是0，last是2k的时候开始循环，一直到first<=last的时候结束，假设到最后first的值为n，则最后n=2k-n的时候结束，所以到最后first和last的值都是k

B.因为此时两个数相同，异或运算的结果均为0

C.把first<=last改为first<last

位级运算的几个常见算法就是实现掩码运算，这里的掩码指的是一个位模式，表示从一个字中选出的位的集合。比如用掩码0xFF表示一个字的低位字节。位级运算x&0xFF生成一个由x的最低有效字节组成的值，其他的字节就被置为0，比如，对于x=0x89ABCDEF，其表达式得到0x000000EF，即我们得到了其最低的八位的值。

答案：

bis(x,y) bis(bic(x,y),bic(y,x))

bis和OR等价，如果x或y对应的位为1，则最后的结果相应的位会是1，所以得到第一个答案，另外，bic(x,m)等价于x&~m，只有当x对应的位为1且m对应的位为0的时候，最后的结果的对应位才等于1，因为x^y等价于(x&~y)|(~x&y)，所以得到第二个答案

关于这个答案，首先一定要仔细审题，理解bis和bic指令的作用，然后要理解这些操作的等价关系，特别是对于这里的bic操作，在m为1的每个位置，将z对应的位设置为0，也就是说和上面解释的一样，m对应的位为0且x对应的位不为0，最后的结果的对应位才为1

C语言中的逻辑运算

C语言还提供了一组逻辑运算符||、&&和!，分别对应命题逻辑中的OR、AND和NOT运算。逻辑运算很容易和位级运算相混淆，但是它们的功能是完全不同的。逻辑运算认为所有非零的参数都表示TRUE，而参数0表示FALSE。它们返回1或者0，分别表示结果为TRUE或者为FALSE。这里是一些示例：

可以观察到，按位运算只有在特殊条件下，即参数被限制为0或者1时，才与其对应的逻辑运算有相同的行为。

逻辑运算符&&和||与 它们对应的位级运算&和|之间第二个重要的区别是，如果对第一个参数求值就能确定表达式的结果，那么逻辑运算符就不会对第二个参数求值。

这里直接做第二题：!(x^y)

C语言中的移位运算

C语言还提供了一组移位运算，向左或者向右移动位模式。对于一个位表示为\([x_{w-1},x_{w-2},…,x_0]\)的操作数\(x\)，C表达式x<<k会生成一个值，其位表示为\([x_{w-k-1},x_{w-k-2},…,x_0,0,…,0]\)。也就是说，x向左移动k位，丢弃最高的k位，并在右端补k个0。移位量应该是一个0~w-1之间的值。移位运算是从左至右可结合的，所以x<<j<<k等价于(x<<j)<<k

有一个相应的右移运算x>>k，但是它的行为有点微妙。一般来说，机器支持两种形式的右移：逻辑右移和算数右移。逻辑右移在左端补k个0，得到的结果是\([0,…,0,x_{w-1},x_{w-2},…,x_k]\)。算数右移是在左端补k个最高有效位的值，得到的结果是\([x_{w-1},…,x_{w-1},x_{w-1},x_{w-2},…,x_k]\)。这种做法看上去可能有点奇特，但是我们会发现它对有符号整数数据的运算非常有用

让我们看一个例子，这个例子对一个8位参数x的两个不同的值做了不同的移位操作：

图中斜体数字表示的是因为移位运算而填充的值，可以看到除了算数右移[10010101]时，其他情况填充的值都是0，因为其最高位是1，所以算数右移之后填充的也是1

C语言标准没有明确定义有符号数应该使用哪种类型的右移，即算数右移或逻辑右移都可以，所以也意味着可能会出现可以执行问题。在实际情况中，几乎所有的编译器/机器都对有符号数使用算数右移，且虚度哦程序员也都假设机器会使用这种右移。而对于无符号数来说，右移必须是逻辑的。而Java中对右移的具体方式有明确的定义，比如x>>k会将x算数右移k个位置，而x>>>k会对x做逻辑右移

C语言标准小心地规避了当位移量大于等于待移位值的位数的情况，实际上位移量会通过计算k mod w得到，不过这种行为对于C程序来说是没有保证的，所以应该保持位移量小于待移动位值的位数

因为加法(和减法)的优先级比移位运算要高。所以表达式1<<2+3<<4等价于1<<(2+3)<<4，答案是512

思考移位运算的最好方式是使用二进制表示，将最初的值转换为二进制，执行移位运算，然后再转换回十六进制

整数表示

接着，我们来学习用位来编码整数的两种不同方式：一种只能表示非负数，而另一种能够表示负数、零和正数。后面我们会看到它们在数学属性和机器级实现方面密切相关，并且还会研究扩展或者收缩一个已编码整数以适应不同长度表示的效果。

这里会涉及到一些数学术语，用于精确定义和描述计算机如何编码和操作整数，这里先把相关的图放在以便之后参考

整数数据类型

C语言支持多种整型数据类型——表示有限范围的整数。每种类型都能用关键字来指定大小，这些关键字包括char、short、long，同时还可以指示被表示的数字是非负数(声明为unsigned)，或者可能是负数(默认)。为这些类型分配的字节数根据程序编译为32位还是64位也会有所不同，根据字节分配，不同的大小所能表示的值的范围是不同的。这里唯一一个与机器相关的取值范围是long类型的，大多数64位机器使用8个字节的表示，比32位机器上使用的4个字节的表示的取值范围大很多

这里有一个很值得注意的特点是取值范围是不对称的——负数的范围比正数的范围大1，当我们考虑如何考虑负数的时候，会看到为什么会这样

C语言标准定义了每种数据类型必须能够表示的最小的取值范围。它们的取值范围和之前图上的典型实现一样或者小一些。除了固定大小的数据类型是例外，我们看到它们只要求正数和负数的取值范围是对称的。另外int可以用2个字节的数字来实现，long可以用4个字节的数字来实现

C和C++都支持有符号(默认)和无符号数。Java只支持有符号数

无符号数的编码

假设有一个整数数据类型有w位。我们可以将位向量写成\(\vec{x}\)，表示整个向量，或者写成\([x_{w-1},x_{w-2},…,x_0]\)，表示向量中的每一位。把\(\vec{x}\)看作一个二进制表示的数，就获得了\(\vec{x}\)的无符号表示。在这个编码中，每个位\(x_i\)都取值为0或1，后一种取值意味着数值\(2^i\)应为数字值的一部分。我们用一个函数\(B2U_w\)(Binary to Unsigned的缩写，长度为w)来表示

在这个等式中，符号”≐”表示左边被定义为等于右边。函数\(B2U_w\)将一个长度为w的0、1串映射到非负整数，比如下面几种情况：

在图中，我们用\(2^i\)的指向右侧箭头的条表示每个位的位置i，每个位向量对应的数值都等于所有值为1的位对应的长度之和

所以，当这个串的长度为w时的取值范围是在它的内容为全0到全1之间的，也就是整数值\(UMax_w≐\sum^{w-1}_{i=0}2^i=2^w-1\)

以4位情况为例，\(UMax_4=B2U_4([1111])=2^4-1=15\)。因此，函数\(B2Uw\)能够被定义为一个映射\(B2U_w:\{0,1\}^w→\{0,…,2^w-1\}\)

无符号的二进制表示有一个很重要的属性，也就是每个介于\(0\)到\(2^w\)-1之间的数都有唯一一个w位的值编码。例如，十进制值11作为无符号数，只有一个四位的表示，即\([1011]\)。我们用数学原理来重点讲述它，先表述原理再解释。

原理：无符号数编码的唯一性

函数\(B2U_w\)是一个双射，所谓双射是一个数学术语，意思是一个函数\(f\)有两面：它将数值\(x\)映射为数值\(y\)，即\(y=f(x)\)，但它也可以反向操作，因为对每一个\(y\)而言，都有唯一一个数值\(x\)使得\(f(x)=y\)。这可以用反函数\(f^{-1}\)来表示，即\(x=f^{-1}(y)\)，在本例中也是如此，函数\(B2U_w\)将每一个长度为\(w\)的位向量都映射为\(0\)到\(2^w-1\)之间的一个唯一值；反过来，我们称其为\(U2B_w\)(即”无符号数到二进制”)，在\(0\)到\(2^w-1\)之间的每一个整数都可以映射为一个唯一的长度为\(w\)的位模式

补码编码

对于许多应用，我们还希望表示负数值。最常见的有符号数的计算机表示方法就是补码(two’s-complement)形式。在这个定义中，将字的最高有效位解释为负权(negative weight)。我们用函数\(B2T_w\)(Binary to Two’s-complement的缩写，长度为\(w\))来表示：

原理：补码编码的定义

对向量\(\vec{x}=[x_{w-1},x_{w-2},…,x_0]\)：

\[B2T_w(\vec{x})≐-x_{w-1}2^{w-1}+\sum^{w-2}_{i=0}x_i2^i\]

最高有效位\(x_{w-1}\)也称为符号位，它的”权重”为$-2^{w-1}$，是无符号表示中权重的负数。符号位被设置为1时，表示值为负，而当设置为0时，值为非负。这里来看几个示例：

\[B2T4([0001])=-0*2^3+0*2^2+0*2^1+1*2^0=0+0+0+1=1\] \[B2T4([0101])=-0*2^3+1*2^2+0*2^1+1*2^0=0+4+0+1=5\] \[B2T4([1011])=-1*2^3+0*2^2+1*2^1+1*2^0=-8+0+2+1=-5\] \[B2T4([1111])=-1*2^3+1*2^2+1*2^1+1*2^0=-8+4+2+1=-1\]

从图上可以看出，与一个位向量相关联的数值是由可能的向左指的条和向右直的条加起来决定的

可以看到，这张图的位模式和之前展示的无符号整数的位模式是一样的，但是当最高有效位是1时，数值是不同的，这是因为在第一种情况中，最高有效位的权重是+8，而在这里，它的权重是-8

所以我们可以想到\(w\)位补码所能表示的值的范围。它能表示的最小值是位向量\([10…0]\)(也就是设置这个位为负权，但是清楚其他所有的位)，其整数值为\(TMin_w≐-2^{w-1}\)。而最大值是位向量\([01…1]\)(清除具有负权的位，而设置其他所有的位)，其整数值为\(TMin_w≐-2^{w-1}\)，其整数值为\(TMax_w≐\sum^{w-2}_{i=0}2^i=2^{w-1}-1\)。以长度为4为例，我们有\(TMin_4=B2T_4([1000])=-2^3=-8\)，而\(TMax_4=B2T_4([0111])=2^2+2^1+2^0=4+2+1=7\)

我们可以看出\(B2T_w\)是一个从长度\(w\)的位模式到\(TMin_w\)和\(TMax_w\)之间的数字的映射，写作\(B2T_w:{0,1}^w→{TMin_w,…,TMax_w}\)。同无符号表示一样，在可表示的取值范围内的每个数字都有一个唯一的\(w\)位的编码编码。这就导出了与无符号数相似的补码数原理：

原理：补码编码的唯一性

函数\(B2T_w\)是一个双射

我们定义函数\(T2B_w\)(即”补码到二进制”)作为\(B2T_w\)的反函数。也就是说，对于每个数\(x\)，满足\(TMin_w\leq{x}\leq{TMax_w}\)，即\(T2B_w(x)\)是\(x\)的(唯一的)\(w\)位模式

观察上图可以发现：

• 补码的范围是不对称的：$$

  TMin

  =

  TMax

  +1\(，也就是说，\)TMin$$没有与之对应的正数，这导致了补码运算中某些特殊的属性，并且容易造成程序中细微的错误。之所以有这样的不对称性，是因为一半的位模式(符号位设置为1的数)表示负数，而另一半(符号位设置为0的数)表示非负数。因为0是非负数，也就意味着能表示的整数比负数少一个

• 最大的无符号数值正好比补码的最大值的两倍大一点：\(UMax_w=2TMax_w+1\)。补码表示中所有表示负数的位模式在无符号表示中都编程了正数
• \(-1\)和\(UMax\)有同样的位表示，即一个全1的串，数值0在两种表示方法中都是全0的串

C语言标准并没有要求要用补码形式来表示有符号整数，但是几乎所有的机器都是这么做的。程序员如果希望代码具有最大可移植性，能够在所有可能的机器上运行，那么除了上图中的那些范围，我们不应该假设任何可表示的数值范围，也不应该假设有符号数回使用何种特殊的表示方式。另一方面，许多程序的书写都假设用补码来表示有符号数，并且具有上面描述的那些”典型的”取值范围，这些程序也能够在大量的机器和编译器上移植。

C库中的文件<limits.h>定义了一组常量来限定编译器运行的这台机器的不同整型数据类型的取值范围。比如，其定义了常量INT_MAX、INT_MIN和UNIT_MAX，它们描述了有符号和无符号整数的范围。对于一个补码的机器，数据类型int有\(w\)位，这些常量就对应于\(TMax_w\)、\(TMin_w\)和\(UMax_w\)的值

有符号数和无符号数之间的转换

C语言允许在各种不同的数字数据类型之间做强制类型转换。例如，假设变量x声明为int，u声明为unsigned。表达式(unsigned)x会将x的值转换成一个无符号数值，而(int)u将u的值转换成一个有符号整数。将有符号整数强制类型转换成无符号数，或者反过来，会得到什么结果呢。很明显，我们是希望这些值保持不变的，可以想象将负数转换成无符号数可能回得到0，如果转换的无符号数太大以至于超出了补码能够表示的范围，可能会得到\(TMax\)。不过，对于大多数C语言的实现来说，对这个问题的回答都是从位级角度来看的，而不是数的角度

比如说，考虑下面的代码：

short int v = -12345;
unsigned short uv = (unsigned short)v;
printf("v = %d, uv = %u\n", v, uv);

在一台使用补码的机器上，上述代码会产生如下输入：

v = -12345, uv = 53191

我们看到，强制类型转换的结果保持位值不变，只是改变了解释这些位的方式。-12345的16位补码表示与53191的16位无符号表示是完全一样的。将short强制类型转换为unsigned short改变数值，但是不改变位表示。

类似地，考虑这段代码：

unsigned u = 4294967295u; /* UMax */
int tu = (int)u;
printf("u = %u, tu = %d\n", u, tu);

在一台采用补码的机器上，会产生如下输出：

u = 4294967295, tu = -1

因为对于32位字长来说，无符号形式的4294967295(\(UMax_{32}\))和补码形式的-1的位模式是完全一样的。将unsigned强制类型转换成int，底层的位表示保持不变。

对于打输出C语言的实现，处理同样字长的有符号数和无符号数之间相互转换的一般规则是：数值可能会改变，但是位模式不变。

可以用更数学化的方法表示：\(T2U_w(x)≐B2U_w(T2B_w(x))\)和\(U2T_w(x)≐B2T_w(U2B_w(x))\)都是成立的

通过前面的所有例子，我们还可以看到，位模式相同的补码与无符号数之间的关系可以表示为函数\(T2U\)的一个属性：

原理：补码转换为无符号数

对满足\(TMin_w\leq{x}\leq{TMax_w}\)的\(x\)有：

\[T2U_w(x)=\begin{cases} x+2^w,x<0\\ x,x\geq0 \end{cases}\]

比如，我们看到\(T2U_{16}(-12345)=-12345+2^{16}=53191\)，\(T2U_w(-1)=-1+2^w=UMax_w\)

推导过程：补码转换为无符号数

因为对于位模式\(\vec{x}\)，如果我们计算\(B2U_w(\vec{x})-B2T_w\vec{(x)}\)的差，从0到w-2的位的加权和互相抵消掉，剩下一个值：

\[B2U_w(\vec{x})-B2T_w(\vec{x})=x_{w-1}(2^{w-1}-(-2^{w-1}))=x_{w-1}2^w\]

这就得到一个关系：\(B2U_w(\vec{x})=x_{w-1}2^w+B2T_w(\vec{x})\)，因此就有：

\[B2U_w(T2B_w(x))=T2U_w(x)=x+x_{w-1}2^w\]

如何理解上面两个式子的关系呢，首先\(T2B_w(x)\)把当前补码数转换成二进制表示，再通过\(B2U_w(\vec{x})\)转换成无符号整数，所以这里的\(B2U_w(T2B_w(x))\)和\(B2U_w(\vec{x})\)是等效的，即从补码数到无符号数的转换操作\(T2U_w(x)\)。再根据上面的关系\(B2U_w(\vec{x})=x_{w-1}2^w+B2T_w(\vec{x})\)，现在\(B2T_w(\vec{x})\)的值就是\(x\)，所以推导出了最后的公式

这张图说明了函数\(T2U\)的一般行为，当将一个有符号数映射为相应的无符号数时，负数会被转换成大的正数，非负数会保持不变

接着，我们来考虑将一个无符号数转换为补码

原理：无符号数转换为补码

对满足\(0\leq{u}\leq{UMax_w}\)的\(u\)有： \(U2T_w(u)=\begin{cases} u,u\leq{TMax_w}\\ u-2^w,u>TMax_w \end{cases}\) 该原理证明如下：

推导：无符号数转换为补码

设\(\vec{u}=U2B_w(u)\)，并且这个位向量也是\(U2T_w{u}\)的补码表示，根据无符号数编码和补码编码的定义，即

\(B2U_w(\vec{x})≐\sum^{w-1}_{i=0}x_i2^i\)和\(B2T_w(\vec{x})≐-x_{w-1}2^{w-1}+\sum^{w-2}_{i=0}x_i2^i\)

我们将其结合起来，所以得到了\(U2T_w(u)=-u_{w-1}2^w+u\)

可以看到，位\(u_{w-1}\)决定了\(u\)是否大于\(TMax_w=2^{w-1}-1\)

总结：当\(0\leq{x}\leq{TMax_w}\)之内的值\(x\)而言，我们得到\(T2U_w{x}=x\)和\(U2T_w{x}=x\)，即在这个范围内的数字的无符号和补码表示的值是相同的。在这个范围以外的数值，转换需要加上或者减去\(2^w\)

C语言中的有符号数与无符号数

尽管C语言标准没有指定有符号数要采用某种表示，但是几乎所有的机器都使用补码。通常，大多数数字都默认为是有符号的。例如，声明一个像12345或者0x1A2B这样的常量时，这个值就被认为是有符号的。加上后缀字符U或者u，例如12345U或0x1A2Bu

C语言允许无符号数有符号数的转换，虽然C标准没有精确规定要如何进行这种转换，但大多数系统遵循的原则是底层的位表示不变。即之前提到过的那些函数的规则(\(U2T_w\)，\(T2U_w\)等)

显式的强制类型转换会导致转换发生，比如：

int tx, ty;
unsigned ux, uy;

tx = (int) ux;
uy = (unsigned) ty;

另外，当一种类型的表达式被赋值给另一种类型的变量时，转换是隐式的，比如：

int tx, ty;
unsigned ux, uy;

tx = ux; /* Cast to signed */
uy = ty; /* Cast to unsigned */

当用printf输出数值时，用指示符%d、%u和%x以有符号十进制、无符号十进制和十六进制格式输出一个数字。注意其可以用指示符%u来输出类型为int的数值，也可以用指示符%d输出类型为unsigned的数值，比如：

int x = -1;
unsigned u = 2147483648; /* 2 to the 31st */

printf("x = %u = %d\n", x, x);
printf("u = %u = %d\n", u, u);

在一个32位机器上运行时，其输出：

x = 4294967295 = -1

u = 2147483648 = -2147483648

提示：结合前面的函数\(T2U_w(x)=x+x_{w-1}2^w\)，所以\(T2U_{32}(-1)=-1+2^{32}=UMax_{32}\)

\(U2T_w(u)=-u_{w-1}2^w+u\)，所以\(U2T_{32}(2^{31})=-2^{32}+2^{31}=-2^{31}=TMin_{32}\)

由于C语言同时包含有符号和无符号数表达式的处理方式，所以会出现一些奇特的行为。当执行一个运算时，如果它的一个运算数是有符号的而另一个是无符号的，那么C语言会隐式地将有符号参数强制类型转换为无符号数，并假设这两个数都是非负的，来执行这个运算。这里的运算主要是说的对于像<和>这样的关系运算符，可以看这张图，由于发生了隐式转换，所以会产生没那么直观的结果：

注意：这里为什么没有直接用\(-2147483648\)或者\(0x80000000\)来表示\(TMin_{32}\)呢，这是由于补码的不对称性和C语言的转换规则之间奇怪的交互。虽然理解这个问题需要我们去关注C语言标准的一些比较隐晦的角落，但是它能帮助我们充分领会整数数据类型及其表示的一些细微之处

扩展一个数字的位表示

一个常见的操作是要在不同字长的整数之间做转换，同时又保持数值不变。当目标数据类型太小，以至于根本表示不了想要的值时，这根本就是不可能的，而从一个较小的数据类型转换到一个较大的类型时，应该总是可能的。

要将一个无符号数转换成一个更大的数据类型，只需要简单地在表示的开头添加0，这种运算被称为零扩展(zero extension)

原理：无符号数的零扩展

定义宽度为\(w\)的位向量\(\vec{u}=[u_{w-1},u_{w-2},…,u_0]\)以及宽度为\(w^′\)的位向量\(\vec{u′}=[0,…,0,u_{w-1},u_{w-2},…,u_0]\)，其中\(w′>w\)。则\(B2U_w(\vec{u})=B2U_{w′}(\vec{u′})\)

这个原理相当于是直接遵循了无符号数编码定义的结果

要将一个补码数字转换成一个更大的数据类型，可以执行一个符号扩展(sign extension)，在表示中添加最高有效位的值，表示为如下原理：

原理：补码数的符号扩展

定义宽度为\(w\)的位向量\(\vec{x}=[x_{w-1},x_{w-2},…,x_0]\)和宽度为\(w\)的位向量\(\vec{x′}=[x_{w-1},…,x_{w-1},x_{w-1},x_{w-2},…,x_0]\)，其中\(w′>w\)。则\(B2T_w(\vec{x})=B2T_{w′}(\vec{x′})\)

例如这段代码：

short sx = -12345; /* -12345 */
unsigned short usx = sx; /* 53191 */
int x = sx; /* -12345 */
unsigned ux = usx; /* 53191 */

printf("sx = %d:\t", sx);
show_bytes((byte_pointer) &sx, sizeof(short));
printf("usx = %u:\t", usx);
show_bytes((byte_pointer) &usx, sizeof(unsigned short));
printf("x = %d:\t", x);
show_bytes((byte_pointer) &x, sizeof(int));
printf("ux = %u:\t", ux);
show_bytes((byte_pointer) &ux, sizeof(unsigned));

在采用补码表示的32位大端法机器上运行这段代码，输出：

sx = -12345: cf c7
usx = 53191: cf c7
x = -12345: ff ff cf c7
ux = 53191: 00 00 cf c7

可以看到，尽管\(-12345\)的补码表示和\(53191\)的无符号表示在16位字长是相同的，但是在32位字长时却是不同的。比如这里\(-12345\)的十六进制表示为\(0xFFFFCFC7\)，而\(53191\)的十进制表示为\(0x0000CFC7\)。前者使用的是符号扩展，即最开头加了16位，都是最高有效位1，表示为十六进制就是\(0xFFFF\)。后者开头使用16个0来扩展，表示为十六进制就是\(0x0000\)

比如一个位向量\([101]\)表示值\(-4+1=-3\)。对其应用符号扩展，得到位向量\([1101]\)，表示的值\(-8+4+1=-3\)。我们可以看到，对于\(w=4\)，最高两位的组合值是\(-8+4=-4\)，与\(w=3\)时符号位的值相同。类似地，位向量\([111]\)和\([1111]\)都表示值\(-1\)

有了这个直觉，我们现在可以展示保持补码值的符号扩展

推导：补码数值的符号扩展

令\(w′=w+k\)，我们想要证明的是

\[B2T_{w+k}([x_{w-1},x_{w-1},x_{w-2},…,x_0])=B2T_w([x_{w-1},x_{w-2},…,x_0])\]

如果我们能证明符号扩展一位保持了数值不变，那么符号扩展任意位都能保持这种属性。因此，证明的任务就变为了：

\[B2T_{w+1}([x_{w-1},x_{w-1},x_{w-2},…,x_0])=B2T_w([x_{w-1},x_{w-2},…,x_0])\]

根据补码编码的定义展开左边的表达式，得到：

\[\begin{aligned} B2T_{w+1}([x_{w-1},x_{w-1},x_{w-2},…,x_0])&=-x_{w-1}2^w+\sum^{w-1}_{i=0}x_i2^i\\ &=-x_{w-1}2^w+x_{w-1}2^{w-1}+\sum^{w-2}_{i=0}x_i2^i\\ &=-x_{w-1}(2^w-2^{w-1})+\sum^{w-2}_{i=0}x_i2^i\\ &=-x_{w-1}2^{w-1}+\sum^{w-2}_{i=0}x_i2^i\\ &=B2T_w([x_{w-1,x_{w-2},…,x_0}]) \end{aligned}\]

从上面的推算过程可以看出，有没有新加的位，得到的结果都是相同的，运算的结果会得到相同的数值

截断数字

假设我们不用额外的位来扩展一个数值，而是减少表示一个数字的位数。例如下面代码中这种情况：

int x = 53191;
short sx = (short) x; /* -12345 */
int y = sx;

当我们把x强制类型转换为short时，我们就将32位的int截断为了16位的short int。就像前面看到的，这个16位的位模式就是-12346的补码表示。当我们把其强制转换为int时，符号扩展把高16位设置为1，从而生成-12345的32位补码表示

当将一个\(w\)位的数\(\vec{x}=[x_{w-1},x_{w-2},…,x_0]\)截断为一个k位数字时，我们会丢弃掉高w-k位，得到一个位向量\(\vec{x′}=[x_{k-1}，x_{k-2},…,x_0]\)。截断一个数字可能会改变它的值，这是溢出的一种形式，对于一个无符号数，我们可以很容易得出其数值结果

原理：截断无符号数

令\(\vec{x}\)等于位向量\([x_{w-1,x_{w-2},…,x_0}]\)，而\(\vec{x′}\)是将其截断为k位的结果：\(\vec{x′}=[x_{k-1},x_{k-2},…,x_0]\)。令\(x=B2U_w(\vec{x})\)，\(x′=B2U_k(\vec{x′})\)，则\(x′=xmod 2^k\)

该原理背后的直觉是所有被截取的位其权重形式都是\(2^i\)，其中$i\geq{k}$，因此，每一个权在取模操作下结果都为零

推导：截断无符号数

\[\begin{aligned} B2U_w([x_{w-1},x_{x-2},…,x_0]) mod 2^k&=[\sum^{w-1}_{i=0}x_i2^i]mod2^k\\ &=[\sum^{k-1}_{i=0}x_i2^i]mod2^k\\ &=\sum^{k-1}_{i=0}x_i2^i\\ &=B2U_k([x_{k-1},x_{k-2},…,x_0]) \end{aligned}\]

这段推导主要利用了属性：对于任何\(i\geq{k}\)，\(2^imod2^k=0\)

补码截断也具有相似的属性，只不过要将最高位转换为符号位：

原理：截断补码数值

因为之前得到了无符号数截断的公式，所以现在将其转换为补码即可，则补码数字的截断结果是：

\[B2T_k[x_{k-1},x_{k-2},…,x_o]=U2T_k(B2U_w([x_{w-1},x_{w-2},…,x_o])mod2^k)\]

关于有符号数与无符号数的建议

可以看到，有符号数到无符号数的强制类型转换导致了某些非直观的行为。这些非直观的特性经常导致程序错误，并且这种包含隐式强制类型转换的细微差别的错误很难被发现。因为这种强制转换是在代码中没有明确指示的时候发生的，程序员经常忽视了它的影响

这边来看两道题：

首先我们在之前了解到执行一个运算时，如果它的一个运算数是有符号的而另一个是无符号的，那么C语言会隐式地将有符号参数强制类型转换为无符号数，并假设这两个数都是非负的，来执行这个运算。

所以这里当length为0时，把length-1看成无符号的0加上有符号的-1，又因为我们知道补码转换成有符号数的转换公式是\(T2U_w(x)=x+x_{w-1}2^w\)，所以这里的结果相当于\(-1+1×2^{32}=4,294,967,295\)，所以会遇到错误，这里有很多种改法，只要避免了这种情况就行了，比如在这里先判断length的值，如果等于0，直接return result

A. 在strlen(t)大于strlen(s)时会出现步正确的结果

B. 因为两个无符号数相减，最后的结果也是无符号数，而此时本来应该输出一个负数，所以这里会用得到相应补码数对应的无符号数，答案会不直观

C. 改成直接比较，把return strlen(s) - strlen(t) > 0;改成return strlen(s) > strlen(t)

整数运算

许多刚入门的程序员会惊奇地发现，两个正数相加会得出一个负数，而比较表达式\(x<y\)和比较表达式\(x-y<0\)会产生不同的结果。这是由于计算机运算的有限性造成的。理解计算机运算的细微之处可以帮助程序员编写更可靠的代码

无符号加法

考虑两个非负整数\(x\)和\(y\)，满足\(0\leq{x},y<2^w\)。每个数都能表示为\(w\)位无符号数字。如果计算它们的和，我们就有一个可能的范围\(0\leq{x+y}\leq2^{w+1}-2\)。表示这个和可能需要\(w+1\)位。例如，这张图展示了当\(x\)和\(y\)有4位表示时，函数\(x+y\)的坐标图。可以看出参数(显示在水平轴上)取值范围为0到15，但是和的取值范围0到30。函数的形状是一个有坡度的平面(在两个维度上，函数都是线性的)，如果保持和为一个\(w+1\)位的数字，并且把它加上另外一个数值，我们可能需要\(w+2\)个位，以此类推。这种持续的”字长膨胀”意味着，想要完整表示算数运算的结果，我们不能对字长做任何限制。一些编程语言，例如Lisp，就支持无限精度的运算，允许任意的(当然，要在机器的内存限制之内)整数运算。更常见的是，编程语言支持固定精度的运算，因此像”加法”和”乘法”这样的运算不同于它们在整数上的相应运算。

让我们为参数\(x\)和参数\(y\)定义运算\(+^u_w\)，其中\(0\leq{x},y<2^w\)，该操作是把整数和\(x+y\)截断为\(w\)位得到的结果，再把这个结果看作是一个无符号数。这可以被视为一种形式的模运算，对\(x+y\)的位级表示，简单丢弃任何权重大于\(2^{w-1}\)的位就可以计算出和模\(2^w\)。比如，考虑一个4位数字表示，\(x=9\)和\(y=12\)的位表示分别为\([1001]\)和\([1100]\)，它们的和是21，5位的表示为\([10101]\)。但是如果舍弃最高位，我们就得到\([0101]\)，也就是说，十进制值的5。这就和值\(21mod16=5\)一致

我们可以将操作\(+^u_w\)描述为：

原理：无符号数加法

对满足\(0\leq{x},y<2^w\)的\(x\)和\(y\)有： \(x+^u_wy=\begin{cases} x+y,x+y<2^w 正常\\ x+y-2^w,2^w\leq{x+y}<2^{w+1}溢出 \end{cases}\) 推导：无符号数加法

一般而言，我们可以看到，如果\(x+y<2^w\)，和的\(w+1\)位标识中的最高位会等于0，因此丢弃它不会改变这个数值。另一方面，如果\(2^w\leq{x+y}<2^{w+1}\)，和的\(w+1\)位表示中的最高位会等于1，因此丢弃它就相当于从和中减去了\(2^w\)

说一个算数运算溢出，是指完整的整数结果不能放到数据类型的字长限制中去。如图展示了字长\(w=4\)的无符号加法函数的坐标图。这个和是按模\(2^4=16\)计算的。当\(x+y<16\)时，没有溢出，并且\(x+^u_4y\)就是\(x+y\)。这对应图中标记为”正常”的斜面。当\(x+y\geq{16}\)时，加法溢出，结果相当于从和中减去16。这对应图中标记为”溢出”的斜面

当执行C程序时，不会将溢出作为错误而发信号。不过有的时候，我们可能希望判定是否发生了溢出。

原理：检测无符号数加法中的溢出

对在范围\(0\leq{x},y\leq{UMax_w}\)中的\(x\)和\(y\)，令\(s\doteq{x}+^u_wy\)。则对计算\(s\)，当且仅当\(s<x\)或者\(s<y\)时，发生了溢出

作为说明，我们可以看到\(9+^u_412=5\)。由于\(5<9\)，我们可以看出发生了溢出。

推导：检测无符号数加法中的溢出

通过观察发现\(x+y\geq{x}\)，所以如果\(s\)没有溢出，我们能够肯定\(s\geq{x}\)。另一方面，如果\(s\)确实溢出了，我们就有\(s=x+y-2^w\)。假设\(y<2^w\)，我们就有\(y-2^w<0\)，因此\(s=x+(y-2^w)<x\)

模数加法形成了一种数学结构，称为阿贝尔群(Abelian group)，这是以丹麦数学家Niels Henrik Abel(1802~1829)的名字命名。它是可交换的(这就是叫”abelian”的原因)和可结合的。它有一个单位元0，并且每个元素有一个加法逆元。让我们考虑\(w\)位的无符号数的集合，执行加法运算\(+^u_w\)，对于每个值\(x\)，必然有某个值\(-^u_wx\)满足\(-^u_wx+^u_wx=0\)，该加法的逆操作可以表述如下：

原理：无符号数求反

对满足\(0\leq{x}<2^w\)的任意\(x\)，其\(w\)位的无符号逆元\(-^u_wx\)由这个式子给出： \(-^u_wx=\begin{cases} x,x=0\\ 2^w-x,x>0 \end{cases}\) 该结果可以很容易地通过案例分析推导出来：

推导：无符号数求反

当\(x=0\)时，加法逆元显然是0。对于\(x>0\)，考虑值\(2^w-x\)。我们观察到这个数字在\(0<2^w-x<2^w\)范围之内，并且\((x+2^w-x)mod2^w=2^wmod2^w=0\)。因此，它就是\(x\)在\(+^u_w\)下的逆元

补码加法

对于补码加法，我们必须确定当结果太大(为正)或者太小(为负)时，应该做些什么。给定在范围\(-2^{w-1}\leq{x},y\leq{2}^{w-1}-1\)之内的整数值\(x\)和\(y\)，它们的和就在范围\(-2^w\leq{x}+y\leq{2}^w-2\)之内，想要准确表示，可能需要\(w+1\)位。就像以前一样，我们通过将表示截断到\(w\)位，来避免数据大小的不断扩张。然而，却不像模数加法那样在数学上感觉很熟悉。定义\(x+^t_wy\)为整数和\(x+y\)被截断为\(w\)位的结果，并将这个结果看做是补码数。

原理：补码加法

对满足\(-2^{w-1}\leq{x},y\leq{2}^{w-1}-1\)的整数\(x\)和\(y\)，有： \(x+^t_wy=\begin{cases} x+y-2^w,2^{w-1}\leq{x+y}正溢出\\ x+y,-2^{w-1}\leq{x+y}<2^{w-1}正常\\ x+y+2^w,x+y<-2^{w-1}负溢出 \end{cases}\)

推导：补码加法

因为补码加法与无符号数加法有相同的位级表示，所以可以按照如下步骤表示运算\(+^t_w\)，将其参数转换为无符号数，执行无符号数加法，再将结果转换为补码：

\[x+^t_wy\doteq{U}2T_w(T2U_w(x)+^u_wT2U_w(y))\]

因为根据之前的推断，我们可以把\(T2U_w(x)\)写成\(x_{w-1}2^w+x\)，把\(T2U_w(y)\)写成\(y_{w-1}2^w+y\)，使用属性\(+^u_w\)是模\(2^w\)的加法，以及模数加法的属性，我们就能得到： \(\begin{aligned} x+^t_wy&=U2T_w(T2U_w(x)+^u_wT2U(y))\\ &=U2T_w[(x_{w-1}2^w+x+y_{w-1}2^w+y)\ mod\ 2^w]\\ &=U2T_w[(x+y)\ mod\ 2^w] \end{aligned}\) 消除了\(x_{w-1}2^w\)和\(y_{w-1}2^w\)这两项，因为它们模\(2^w\)等于\(0\)

为了更好地理解这个数量，定义整数\(z\)为整数和\(z\doteq{x+y}\)，\(z'\)为\(z'\doteq{z\ mod\ 2^w}\)，而\(z''\)为\(z''\doteq{U2T_w(z')}\)。数值\(z''\)等于\(x+^t_wy\)。我们分成4种情况分析

首先，我们记得无符号数转换为补码的公式，对满足\(0\leq{u}\leq{UMax_w}\)的\(u\)有： \(U2T_w(u)=\begin{cases} u,\ u\leq{TMax_w}\\ u-2^w,\ u>TMax_w \end{cases}\)

1. \(-2^w\leq{z}<-2^{w-1}\)。然后，我们会有\(z'=z+2^w\)。这就得出\(0\leq{z'}<-2^{w-1}+2^w=2^{w-1}\)，因为这个数字满足上面所示无符号数转换为补码的第一个区间，所以\(z''=z'\)，这种情况称为负溢出(negative overflow)。我们将两个负数相加(这是我们能得到\(z<-2^{w-1}\)的唯一方式)，得到一个非负的结果\(z''=x+y+2^w\)
2. \(-2^{w-1}\leq{z}<0\)。那么，我们又将有\(z'=z+2^w\)，得到\(-2^{w-1}+2^w=2^{w-1}\leq{z'}<2^w\)。我们看到\(z'\)在满足\(z''=z'-2^w\)的范围之内，因此\(z''=z'-2^w=z+2^w-2^w=z\)。也就是说，我们的补码和\(z''\)等于整数和\(x+y\)

1. 关于这里的异或运算，一开始可能不太理解，首先要明白，异或，就是找出两个位向量里面不同的元素，这里因为每个元素的加法逆元这个属性即使交换之后也成立，所以这里其实相当于(a^a)^b，即b与0相异或，值还是b ↩