02 2.2 整数表示.txt

2.2 整数表示
在本节中，我们描述用位来编码整数的两种不同的方式∶一种只能表示非负数，而另一种能够表示负数、零和正数。后面我们将会看到它们在数学属性和机器级实现方面密切相关。我们还会研究扩展或者收缩一个已编码整数以适应不同长度表示的效果。图2-8列出了我们引人的数学术语，用于精确定义和描述计算机如何编码和操作整数。这些术语将在描述的过程中介绍，图在此处列出作为参考。


2.2.1整型数据类型
C语言支持多种整型数据类型——表示有限范围的整数。这些类型如图2-9和图2-10所示，其中还给出了“典型”32位和64位机器的取值范围。每种类型都能用关键字来指定大小，这些关键字包括char、short、long，同时还可以指示被表示的数字是非负数(声明为unsigned)，或者可能是负数(默认)。如图2-3所示，为这些不同的大小分配的字节数根据程序编译为32位还是64位而有所不同。根据字节分配，不同的大小所能表示的值的范围是不同的。这里给出来的唯一一个与机器相关的取值范围是大小指示符long的。大多数64位机器使用8个字节的表示，比32位机器上使用的4个字节的表示的取值范围大很多。
图2-9和图2-10中一个很值得注意的特点是取值范围不是对称的——负数的范围比整数的范围大1。当我们考虑如何表示负数的时候，会看到为什么会这样。C语言标准定义了每种数据类型必须能够表示的最小的取值范围。如图2-11所示，它们的取值范围与图2-9和图2-10所示的典型实现一样或者小一些。特别地，除了固定大小的数据类型是例外，我们看到它们只要求正数和负数的取值范围是对称的。此外，数据类型int可以用2个字节的数字来实现，而这几乎回退到了16位机器的时代。还可以看到，long 的大小可以用4个字节的数字来实现，对32位程序来说这是很典型的。固定大小的数据类型保证数值的范围与图2-9给出的典型数值一致，包括负数与正数的不对称性。

给C语言初学者 C、C++和Java中的有符号和无符号数
C和C++都支持有符号(默认)和无符号数。Java只支持有符号数。

2.2.2 无符号数的编码
假设有一个整数数据类型有w位。我们可以将位向量写成子，表示整个向量，或者写成[w-1，Tw-2，…，ro]，表示向量中的每一位。把至看做一个二进制表示的数，就获得


44 第一部分 程序结构和执行
了的无符号表示。在这个编码中，每个位x都取值为0或1，后一种取值意味着数值2应为数字值的一部分。我们用一个函数B2U。（Binary to Unsigned的缩写，长度为w）来表示∶
原理∶无符号数编码的定义对向量云=【z一，r一t，…，xn】∶
BU。.(i)=Sn2
在这个等式中，符号"="表示左边被定义为等于右边。函数 B2U将一个长度为w的0、1串映射到非负整数。举一个示例，图2-11展示的是下面几种情况下B2U给出的从位向量到整数的映射∶
B2U.([000])=0·2＋0·2＋0·2'＋1.2°=0+0＋0＋1=1 BU.([0101])=0·2＋1·2＋0·2＋1·2°=0＋4＋0＋1=5 B2U.([1011])=1.2＋0.2＋1.2'＋1.2°=8+0＋2＋1=112 B2U([111])=1·28＋1·2＋1·2'＋1·20=8＋4＋2＋1=15
在图中，我们用长度为2的指向右侧箭头的条表示每个位的位置i。每个位向量对应的数值就等于所有值为1的位对应的条的长度之和。
让我们来考虑一下 w 位所能表示
2=27
的值的范围。最小值是用位向量【00·.
?2-1B
0】表示，也就是整数值0，而最大值是土3}4子424p9u早p4p9 用位向量【11…】表示，也就是整数值
00o
UMazr。=22=2"-1.以4位情况【c四- tou)
为例，UMar.=B2U.（【【11】）=2- IC nEEEBEU'
1=15。因此，函数B2U。能够被定义 【I1
10，1}"→{0，…，图212 w=4的无符号数示例。
中位i为1，数值就会相应加上2
2"-1}
无符号数的二进制表示有一个很重要的属性，也就是每个介于0～2"-1之间的数都有唯—一个w位的值编码。例如，十进制值11作为无符号数，只有一个4位的表示，即【1011】。我们用数学原理来重点讲述它，先表述原理再解释。
原理∶无符号数编码的唯一性
数学术语双射是指一个函数f有两面∶它将数值x映射为数值y，即 y=（x），但它也可以反向操作，因为对每一个y而言，都有唯一一个数值x使得f（x）=y。这可以用反画数厂'来表示，在本例中，即x='（y）。函数B2U。将每一个长度为w的位向量都映射为0～2"-1之间的一个唯一值;反过来，我们称其为U2B。（即"无符号数到二进制"），在0～2"-1之间的每一个整数都可以映射为一个唯一的长度为w的位模式。2.2.3 补码编码
对于许多应用，我们还希望表示负数值。最常见的有符号数的计算机表示方式就是补码（two's-complement）形式。在这个定义中，将字的最高有效位解释为负权（negative weight）。我们用函数 B2T。（Binary to Two'scomplement的缩写，长度为w）来表示∶
第2章信息的表示和处理45
原理∶补码编码的定义对向量=【x-），一∶，…20】∶B2T。()=-x-12-l＋》x2
(2.3)
最高有效位r一也称为符号位，它的"权重"为-2"一l，是无符号表示中权重的负数。符号位被设置为1时，表示值为负，而当设置为0时，值为非负。这里来看一个示例，图2-13展示的是下面几种情况下B2T给出的从位向量到整数的映射。

我们可以看到，图 2-12和图 2-13 -7-6-5-4-3-2-1012345
中的位模式都是一样的，对等式（2.2）和等式（2.4）来说也是一样，但是当最 000r 高有效位是1时，数值是不同的，这是 【0101
因为在一种情况中，最高有效位的权重 （101】是+8，而在另一种情况中，它的权重
权重（
是-8.
让我们来考虑一下w位补码所能图213 w=4的补码示例。把位3作为符号位，因此当它表示的值的范围。它能表示的最小值是为1时，对数每
位为场负在图中用带向左箭头的条表示
位向量【10】（也就是设置这个位为负
权，但是清除其他所有的位），其整数值为TMin。=-2一。而最大值是位向量【01…1】（清除具有负权的位，而设置其他所有的位），其整数值为 TMar。二2?=2-1.以长度为4为例，我们有TMn=B2T，（【1000】）=-2'=-8，而 TMax，=B2T。（【0111】）=2'+2＋20=4＋2+1=7。
我们可以看出B2T。是一个从长度为w的位模式到TMin。和TMar。之间数字的映射，写作 B2T。∶（0，1}→{TMin。，…，TMar。）。同无符号表示一样，在可表示的取值范围内的每个数字都有一个唯一的w位的补码编码。这就导出了与无符号数相似的补码数原理
原理∶补鸡编马的唯一性函数 B2T。是一个双射。
我们定义函数T2B（即"补码到二进制""）作为B2T。的反函数。也就是说，对于每个数x，满足 TMin≤x≤TMar。，则T2B。（x）是x的（唯一的）位模式。
练习题2.17 假设w=4，我们能给每个可能的十六进制数字赋予一个数值，假设用一个无符号或者补码表示。请根据这些表示，通过写出等式（2.1）和等式（2.3）所示的
求和公式中的2的非零次幂，填写下表∶

图2-14展示了针对不同字长，几个重要数字的位模式和数值。前三个给出的是可表示的整数的范围，用UMa. 、TMin和TMac w来表示。在后面的讨论中，我们还会经常引用到这三个特殊的值。如果可以从上下文中推断出w，或者w不是讨论的主要内容时，我们会省略下标w，直接引用UMax 、TMin和TMax。

关于这些数字，有几点值得注意。第一，从图2-9和图2-10可以看到，补码的范围是不对称的:|TMin|= |TMax|+1，也就是说，TMin没有与之对应的正数。正如我们将会看到的，这导致了补码运算的某些特殊的属性，并且容易造成程序中细微的错误。之所以会有这样的不对称性，是因为一半的位模式(符号位设置为1的数)表示负数，而另一半(符号位设置为0的数)表示非负数。因为0是非负数，也就意味着能表示的整数比负数少一个。第二，最大的无符号数值刚好比补码的最大值的两倍大一点:UMa工-2TMax.+1。补码表示中所有表示负数的位模式在无符号表示中都变成了正数。图2-14也给出了常数-1和0的表示。注意一1和UMax有同样的位表示—-一个全1的串。数值О在两种表示方式中都是全О的串。C语言标准并没有要求要用补码形式来表示有符号整数，但是几乎所有的机器都是这么做的。程序员如果希望代码具有最大可移植性，能够在所有可能的机器上运行，那么除了图2-11所示的那些范围之外，我们不应该假设任何可表示的数值范围，也不应该假设有符号数会使用何种特殊的表示方式。另一方面，许多程序的书写都假设用补码来表示有符号数，并且具有图2-9和图2-10所示的“典型的”取值范围，这些程序也能够在大量的机器和编译器上移植。C库中的文件<limits.h>定义了一组常量，来限定编译器运行的这台机器的不同整型数据类型的取值范围。比如，它定义了常量INT_MAX、INT_MIN和UINT_MAx，它们描述了有符号和无符号整数的范围。对于一个补码的机器，数据类型int有w位，这些常量就对应于TMaxw、TMin和UMax 。.的值。

第2章信息的表示和处理47
料 关于确定大小的整数类型的更多内睿
对于某些程序来说，用某个确定大小的表示来编码数据类型非常重要。例如，当编写程序，使得机器能够按照一个标准协议在因特网上通信时，让数据类型与协议指定的数据类型兼容是非常重要的。我们前面看到了，某些C数据类型，特别是long型，在不同的机器上有不同的取值范围，而实际上C语言标准只指定了每种数据类型的最小范围，而不是确定的范图。虽然我们可以选择与大多数机器上的标准表示兼容的数据类型，但是这也不能保证可移植性。
我们已经见过了32位和64位版本的确定大小的整数类型（图2-3），它们是一个更大数据类型类的一部分。ISOC99标准在文件stdint.h中引入了这个整数类型类。这个文件定义了一组数据类型，它们的声明形如intNt和uintNt，对不同的N值指定N位有符号和无符号整数。N的具体值与实现相关，但是大多数编译器允许的值为8、16、32和64。因此，通过将它的类型声明为uint16t，我们可以无歧义地声明一个16 位无符号变量，而如果声明为int32t，就是一个32位有符号变量。
这些数据类型对应着一组宏，定叉了每个N的值对应的最小和最大值。这些宏名字形如 INTyMITN、INTM MAx 和UINTNMAx。
确定宽度类型的带格式打印需要使用宏，以与系统相关的方式扩展为格式串。因此，举个例子来说，变量×和y的类型是int32t和uint64t，可以通过调用printf 来打印它们的值，如下所示∶
printr("x -W" PRId32",y =X" PRTu64"a",x,y);
编译为64位程序时，宏 PRId32展开成字符串""，宏 PRIu64则展开成两个字符串"1""心"。当C预处理器遇到仅用空格（或其他空白字符）分隔的一个字符串常量序列时，就把它们串联起来。因此，上面的 printf调用就变成了∶printr("x =d,y =1u\a",x,y);
使用宏能保证∶不论代码是如何被编译的，都能生威正确的格式字符串。
'关于整数数据类型的取值范围和表示，Java标准是非常明确的。它要求采用补码表示，取值范围与图210中64位的情况一样。在Java中，单字节数据类型称为byte，而不是char。这些非常具体的要求都是为了保证无论在什么机器上运行，Java程序都能表现地完全一样。院用 有符号数的其他表示方法
有符号数还有两种标准的表示方法∶
反码（Ones'Complement）;除了最高有效位的权是-（2-1-1）而不是-2'，它和补码是一样的∶
B2O.）=-r一（2一-1）＋Sx2
原码（Sgr-Magniude）;最高有效位是符号位，用来确定剩下的位应该取负权还是正权∶B2S。()=(-1)'-. (Sx2)
这两种表示方法都有一个奇怪的属性，那就是对于数字0有两种不同的编码方式。这两种表示方法，把【00…】都解释为+0。而值-0在原玛中表示为【10…0】，在反码中表示为【11…1】。虽然过去生产过基于反码表示的机器，但是几乎所有的现代机器都使用科码。我们将看到在浮点数中有使用原码编码。

48 第一部分 程序结构和执行
请注意补码（Two's complement）和反码（Ones'complement）中搬号的位置是不同的。术语补码来源于这样一个情况，对于非负数x，我们用2~-xr（这里只有一个2）来计算-x的w位表示。术语反码来源于这样一个属性，我们用【11…】-r（这里有很多个1）来计算一r的反码表示。为了更好地理解补码表示，考虑下面的代码∶
thort x-12345;ahort ax --x;
tov.bytes((bytepointer)kx,sizeof (short);
当在大端法机器上运行时，这段代码的输出为30 39和cfc7，指明x的十六进制表示为0x3039，而m×的十六进制表示为0xcFC7。将它们展开为二进制，我们得到x的位模式为【000001101】，而mx的位模式为【1100111001】。如图2-15所示，等式（2.3）对这两个位模式生成的值为12345和-12345。

练习题2.18 在第3章中，我们将看到由反汇编器生成的列表，反汇编器是一种将可
执行程序文件转换回可读性更好的ASCI码形式的程序。这些文件包含许多十六进制数字，都是用典型的补码形式来表示这些值。能够认识这些数字并理解它们的意义
（例如它们是正数还是负数），是一项重要的技巧。
在下面的列表中，对于标号为A～（标记在右边）的那些行，将指令名（sub、mov 和add）右边显示的（32位补码形式表示的）十六进制值转换为等价的十进制值。


2.2.4 有符号数和无符号数之间的转换
C语言允许在各种不同的数字数据类型之间做强制类型转换。例如，假设变量x声明为int，u声明为unsigned。表达式（unsigned）x会将x的值转换成一个无符号数值，而（int）u将u的值转换成一个有符号整数。将有符号数强制类型转换成无符号数，或者反过来，会得到什么结果呢?从数学的角度来说，可以想象到几种不同的规则。很明显，对于在两种形式中都能表示的值，我们是想要保持不变的。另一方面，将负数转换成无符号数可能会得到0。如果转换的无符号数太大以至于超出了补码能够表示的范围，可能会得到TMar。不过，对于大多数C语言的实现来说，对这个问题的回答都是从位级角度来看的，而不是数的角度。
比如说，考虑下面的代码∶


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


从图2-14我们可以看到，对于32位字长来说，无符号形式的4294967295（UMaxm）和补码形式的-1的位模式是完全一样的。将unsigned强制类型转换成int，底层的位表示保持不变。
对于大多数C语言的实现，处理同样字长的有符号数和无符号数之间相互转换的一般规则是∶数值可能会改变，但是位模式不变。让我们用更数学化的形式来描述这个规则。我们定义函数U2B。和T2B.，它们将数值映射为无符号数和补码形式的位表示。也就是说，给定0≤r≤UMar。范围内的一个整数x，函数U2B。（xr）会给出r的唯一的w位无符号表示。相似地，当x满足 TMin≤r≤TMar。，函数T2B_（x）会给出x的唯一的w位补码表示。现在，将函数T2U。定义为T2U（x）=B2U。（T2B。（x））。这个函数的输入是一个

50 第一部分程序结构和执行
TMin。～TMar。的数，结果得到一个0～UMar。的值，这里两个数有相同的位模式，除了参数是无符号的，而结果是以补码表示的。类似地，对于0～UMar。之间的值x，定义函数U2T。为U2T。（x）=B2T。（U2B（x））。生成一个数的无符号表示和x的补码表示相同。继续我们前面的例子，从图2-15中，我们看到T2U。（-12345）=53191，并且U2T。（53191）=-12345。也就是说，十六进制表示写作oxcrc7的16 位位模式既是-12345的补码表示，又是53191的无符号表示。同时请注意12345+＋53191=6536=2"。这个属性可以推广到给定位模式的两个数值（补码和无符号数）之间的关系。类似地，从图2-14我们看到T2U（-1）=4294967295，并且U2Ta（4294967295）=-1。也就是说，无符号表示中的UMax有着和补码表示的-1相同的位模式。我们在这两个数之间也能看到这种关系∶1十UMar。=2"。
接下来，我们看到函数U2T描述了从无符号数到补码的转换，而T2U描述的是补码到无符号的转换。这两个函数描述了在大多数C语言实现中这两种数据类型之间的强制类型转换效果。
练习题2.19 利用你解答练习题2.17时填写的表格，填写下列描述函数TUl的表格。
Tu)
通过上述这些例子，我们可以看到给定位模式的补码与无符号数之间的关系可以表示为函数 T2U的一个属性∶
原理∶补码转换为无符号数对满足 TMin≤r≤TMar。的x 有∶
_x+2",x<0
(2.5)
比如，我们看到T2U。（-12345）=-12345＋20=53191，同时T2U。（-1）=-1+2-=UMar。
该属性可以通过比较公式（2.1）和公式（2.3）推导出来，推导∶补码转换为无符号数
比较等式（2.1）和等式（2.3），我们可以发现对于位模式云，如果我们计算 B2U。（云）-B2T。G）之差，从0到w—2的位的加权和将互相抵消掉，剩下一个值∶BZU儿（）-BT。（）=r一（2一1-（-2-1））=工-2。这就得到一个关系∶B2U。（）=工。2"+BT。（）。我们因此就有
B2UL(T2B。(x))= T2U。(x)=x+r2*
根据公式（2.5））的两种情况，在x的补码表示中，位r。一决定了x是否为负。I 比如说，图2-16比较了当w=4时函数B2U和B2T是如何将数值变成位模式的。对补码来说，最高有效位是符号位，我们用带向左箭头的条来表示。对于无符号数来说，最高有效位是正权重，我们用带向右的箭头的条来表示。从补码变为无符号数，最高有效位
第2章 信息的表示和处理 51
的权重从-8变为＋8。因此，补码表示的负数如果看成无符号数，值会增加2'=16。因而，-5变成了＋11，而-1变成了＋15。

图2-16 比较当 w=4时无符号表示和补码表示（对补码和无符号数来说，
最高有效位的权重分别是-8和+8，因而产生一个差为16）
图2-17说明了函数T2U的一般行为。如图所示，当将一个有符号数映射为它相应的无符号数时，负数就被转换成了大的正数，而非负数会保持不变。
三 练习题2.20 请说明等式（2.5）是如何应用到解答练习题2.19时生成的表格中的各项的。
反过来看，我们希望推导出一个无符号数u和与之对应的有符号数U2T。（w）之间的关系∶原理∶无符号数转换为补码对满足0≤u≤UMar。的u有∶

· 该原理证明如下∶推导;无符号数转换为补码
设i=U2B。（u），这个位向量也是U2T。（2）的补码表示。公式（2.1）和公式（2.3）结合起来有
U2T_(u)=-u-2"+u
在u的无符号表示中，对公式（2.7）的两种情况来说，位M决定了u是否大于TMar。=2-l-1。
图2-18说明了函数U2T的行为。对于小的数（≤TMar.），从无符号到有符号的转换将保留数字的原值。对于大的数（>TMaz.），数字将被转换为一个负数值。
2*-
[2
无符号数 21
图218 从无符号数到补码的转换。函数U2T 智217 从补码到无符号数的转换。函数
T2U将负数转换为大的正数
把大于21-1的数字转换为负值

总结一下，我们考虑无符号与补码表示之间互相转换的结果。对于在范围0≤x≤TMar。之内的值x而言，我们得到T2U。（x）=x和U2T。（x）=x。也就是说，在这个范围内的数字有相同的无符号和补码表示。对于这个范围以外的数值，转换需要加上或者减去2。例如，我们有T2U（-1）=-1+2"=UMar。——最靠近0的负数映射为最大的无符号数。在另一个极端，我们可以看到T2U。（TMin）=-2l＋2"=2l=TMar。十1———最小的负数映射为一个刚好在补码的正数范围之外的无符号数。使用图2-15的示例，我们能看到 T2U。（-12345）=65563＋-12345=53191. 2.2.5 C 语言中的有符号数与无符号数
如图29和图2-10所示，C语言支持所有整型数据类型的有符号和无符号运算。尽管C语言标准没有指定有符号数要采用某种表示，但是几乎所有的机器都使用补码。通常，大多数数字都默认为是有符号的。例如，当声明一个像12345或者0x122B这样的常量时，这个值就被认为是有符号的。要创建一个无符号常量，必须加上后缀字符'U'或者''，例如，12345U或者0x1A2Bu。
C语言允许无符号数和有符号数之间的转换。虽然C标准没有精确规定应如何进行这种转换，但大多数系统遵循的原则是底层的位表示保持不变。因此，在一台采用补码的机器上，当从无符号数转换为有符号数时，效果就是应用函数U2T.，而从有符号数转换为
无符号数时，就是应用函数 T2U。，其中w表示数据类型的位数。
显式的强制类型转换就会导致转换发生，就像下面的代码∶13i
int tx,ty;unsigned ux,uy;
uy -(unsigned)ty;
另外，当一种类型的表达式被赋值给另外一种类型的变量时，转换是隐式发生的，就像下面的代码∶
unsigned ux,uy;
tx =ux;/* Caat to aigned*/uy = ty;/* Cast to unslgned */
当用printf输出数值时，分别用指示符d、u和ex以有符号十进制、无符号十进制和十六进制格式输出一个数字。注意 printf没有使用任何类型信息，所以它可以用指示符u来输出类型为int的数值，也可以用指示符d输出类型为unsigned的数值。例如，考虑下面的代码∶
nt x=-1;
umsigned u= 2147483648;/* 2 to the 31st */printf（"x=知- A\n"，x，x）;printf("u= Xu- XN",u,u);当在一个32 位机器上运行时，它的输出如下∶
x=4294967295--1 u-2147483648=-2147483648

第2 章 信息的表示和处理53
在这两种情况下，printf首先将这个字当作一个无符号数输出，然后把它当作一个有符号数输出。以下是实际运行中的转换函数∶TU（-1）=UMaxa=2-1和U2T。（2四）=2-2=-2=TMin:。
由于C语言对同时包含有符号和无符号数表达式的这种处理方式，出现了一些奇特的行为。当执行一个运算时，如果它的一个运算数是有符号的而另一个是无符号的，那么C 语言会隐式地将有符号参数强制类型转换为无符号数，并假设这两个数都是非负的，来执行这个运算。就像我们将要看到的，这种方法对于标准的算术运算来说并无多大差异，但是对于像<和>这样的关系运算符来说，它会导致非直观的结果。图2-19展示了一些关系表达式的示例以及它们得到的求值结果，这里假设数据类型int表示为32位补码。考虑比较式-1<00。因为第二个运算数是无符号的，第一个运算数就会被隐式地转换为无符号数，因此表达式就等价于42949672950<0u〔回想T2U。（-1）=UMar。），这个答案显然是错的。其他那些示例也可以通过相似的分析来理解。
类重

注∶非直观的情况标注了··'。当一个速算裁是无特号的时候，另一个运算数也被隐式强制特操为无井号。
练习题2.21 假设在采用补码运算的32位机器上对这些表达式求值，按照图2-19的
格式填写下表，描述强制类型转换和关系运算的结果。
——表语一天一求童m
-2147403647-1 -2147483648 -2147483647-12147483647 -2147483647-10<214740647 │-2147483647-1<-2147483647 -2147483647-1U <-247403647
区监费注DAIAIC 语言中 7MZ的写法
在图2-19和练习题2.21中，我们很小心地将TMinm写成-2147483647-1。为什么不简单地写成-2147483648或者0x80000?看一下C头文件limits.h，注意到它们使用了跟我们写 TMinu和 TMax∶类似的方法∶
/* Minimum and maximum values a'signed int' can hold.*/#def ine INMT_MAX 2147483647 #define IT_MTN(-INT_MAx-1)
不幸的是，补码表示的不对称性和C语言的转换规则之间奇怪的交互，迫使我们用

54 第一部分 程序姑构和执行
这种不寻常的方式来写TMin加。虽然理解这个问题需要我们钻研C语言标准的一些比较隐晦的角落，但是它能够帮助我们充分领会整数数据类型和表示的一些细微之处。2.2.6 扩展一个数字的位表示
一个常见的运算是在不同字长的整数之间转换，同时又保持数值不变。当然，当目标数据类型太小以至于不能表示想要的值时，这根本就是不可能的。然而，从一个较小的数据类型转换到一个较大的类型，应该总是可能的。
要将一个无符号数转换为一个更大的数据类型，我们只要简单地在表示的开头添加0。这种运算被称为零扩展（zero extension），表示原理如下∶
原理∶无符号数的零扩展
定义宽度为w的位向量i=【u-1，u一，…，u】和宽度为w'的位向量'=【0，…0，u一1，u一，…·0】，其中w'>w。则BU。（i）=B2U。（ü'）。
按照公式（2.1），该原理可以看作是直接遵循了无符号数编码的定义。
要将一个补码数字转换为一个更大的数据类型，可以执行一个符号扩展（sign exten-sion），在表示中添加最高有效位的值，表示为如下原理。我们用蓝色标出符号位xi来突出它在符号扩展中的角色。
原理∶补码数的符号扩晨
定义宽度为w的位向量=【x，工2，…，z6】和宽度为w的位向量'=【r一，…，一，x，x·…·x6】，其中w'>w。则B2T。（云）=B2T。）。
例如，考虑下面的代码∶

在采用补码表示的32位大端法机器上运行这段代码时，打印出如下输出∶
ex= -12345:cf ci uax= 53191:cf c7 x-12345:ft ff ct c7 ux = 53191:00 00 ef c7
我们看到，尽管-12345的补码表示和53191的无符号表示在16 位字长时是相同的，但是在3位字长时却是不同的。特别地，-12345的十六进制表示为0xFFCFC7，而53191的十六进制表示为0x00CFC7。前者使用的是符号扩展———最开头加了16位，都是最高有效位1，表示为十六进制就是0xFF。后者开头使用16个0来扩展，表示为十六进制就是0x000。
图2-20给出了从字长w=3到w=4的符号扩展的结果。位向量【101】表示值-4+1=

-3.对它应用符号扩展，得到位向量【1101】，表示的值-8+4+1=-3。我们可以看到，对于w=4，最高两位的组合值是-8+4=-4，与w=3时符号位的值相同。类似地，位向量11】和【11】都表示值一1 -2'--。
《2-
2-s 2l=2 2°-1
-8-7-6-5-4-3-2-10!234567 [1ol
稳转超
ml—y
字-20 从u=3到w=4的符号扩展示例.对于 w=4，最高两位组合权重为-8+4=-4，与 w=3时的符号位的权重一样
有了这个直觉，我们现在可以展示保持补码值的符号扩展。推导∶补码数值的符号扩展令 w'=w+k，我们想要证明的是
B2T(-,,,-,-…,x6])= B2T。([r-1-…·26])
下面的证明是对k进行归纳。也就是说，如果我们能够证明符号扩展一位保持了数值不变，那么符号扩展任意位都能保持这种属性。因此，证明的任务就变为了∶B2T([r-,-,z,…,26])=B2T([r-,x-,….x])用等式（（2.3）展开左边的表达式，得到∶

我们使用的关键属性是2~-2一'=2一'。因此，加上一个权值为-2的位，和将一个权值为-2一'的位转换为一个权值为21'的位，这两项运算的综合效果就会保持原始的数值。 ■练习题2.22 通过应用等式（2.3），表明下面每个位向量都是-5的补码表示。

可以看到第二个和第三个位向量可以通过对第一个位向量做符号扩展得到。
值得一提的是，从一个数据大小到另一个数据大小的转换，以及无符号和有符号数字之间的转换的相对顺序能够影响一个程序的行为。考虑下面的代码∶
short ax= -12345;/*-12345 */unsgnoed uy- ex;/* Mystery printf("uy u:\t",uy);
s shov_bytes((byte_pointer)zuy,sizeof(unsigned));在一台大端法机器上，这部分代码产生如下输出∶
uy = 4294954951:ft t cf c7
这表明当把 short.转换成unsigned时，我们先要改变大小，之后再完成从有符号到无符号的转换。也就是说（（unsigned）sx等价于（unsigned）（int）sx，求值得到4294954951，而不等价于（unsigned）（unsigned short）sx，后者求值得到53191。事实上，这个规则是C 语言标准要求的。练习题2.23考虑下面的C函数∶
1nt runl(uasigned word)(return(int)((word<24)>>24);
int fun2(unsigned word)(
return((int)word<< 24)>>24;
假设在一个采用补码运算的机器上以32位程序来执行这些函数。还假设有符号数值的右移是算术右移，而无符号数值的右移是逻辑右移。
A.填写下表，说明这些函数对几个示例参数的结果。你会发现用十六进制表示来做会更方便，只要记住十六进制数字8到F的最高有效位等于1。
funl(w)0x000076 0x87654321 0x0000c5 OxEDCBA987
B.用语言来描述这些函数执行的有用的计算。2.2.7 截断数字
假设我们不用额外的位来扩展一个数值，而是减少表示一个数字的位数。例如下面代码中这种情况∶
1 4nt x=53191;
2 short Bx-(ehort)x; /*-12345*/3 nt y-Bx;
当我们把x强制类型转换为 short时，我们就将32位的int截断为了16位的 short int。

就像前面所看到的，这个16位的位模式就是-12345的补码表示。当我们把它强制类型转换回int时，符号扩展把高16位设置为1，从而生成-12345的32位补码表示。当将一个w位的数三=【r、一1，工一2，…，x6】截断为一个k位数字时，我们会丢弃高w—k位，得到一个位向量'=【x-1，工-2，…，x。】。截断一个数字可能会改变它的值——溢出的一种形式。对于一个无符号数，我们可以很容易得出其数值结果。
原理∶截断无符号数
令云等于位向量【r-，Z-，，…，26】，而'是将其截断为k位的结果∶=【x-1，-，…26】。令x=B2U（），x'=B2U.（'）。则r'=xmod2'。
该原理背后的直觉就是所有被截去的位其权重形式都为2，其中≥k，因此，每一个权在取模操作下结果都为零。可用如下推导表示∶
推导∶截断无符号数
通过对等式（2.1）应用取模运算就可以看到∶
B2U儿（【r-，r-…，x】） mod2=Sn2】mod2
0.■
在这段推导中，我们利用了属性∶对于任何≥，2'mod2*=0。
补码截断也具有相似的属性，只不过要将最高位转换为符号位∶原理∶截断补码数值
令等于位向量【x0，工-，…x6】，而'是将其截断为k位的结果∶'=【工-1，>，…，x0】。令r=BU。（），r'=B2T，G）。则r'=U2T.（xmod2*）。在这个公式中，xmod 2'将是0到2'-1之间的一个数。对其应用函数U2T.产生的效果是把最高有效位x-的权重从2'转变为-2r1。举例来看，将数值 x=53191从int转换为short。由于2"=65536≥r，我们有xmod 2"=x。但是，当我们把这个数转换为16位的补码时，我们得到r'=53191-6536=-12345.
推导∶截断补码数值
使用与无符号数截断相同的参数，则有
BU。([1,…,x6])mod2*= BU,[-1,·…,x2]
也就是，xmod2'能够被一个位级表示为【x-，r-，…，x】的无符号数表示。将其转
■换为补码数则有x'=U2T.（x mod 2*）。
总而言之，无符号数的截断结果是∶
B2U[x-1,-…,28]=B2U。([x1,-…,x2])mod2(2.9)而补码数字的截断结果是∶
B2T[r-,x-·…,x8]=U2T(B2U([x-1,z…,x2]) mod 24) (2.10)国练习题2.24 假设将一个4位数值（用十六进制数字0～F表示）截断到一个3位数值（用十六进制数字0～7表示）。填写下表，根据那些位模式的无符号和补码解释，说明这种截断对某些情况的结果。
&确9二K备重
新值双M有
截新盈二原6值
解释如何将等式（2.9）和等式（2.10）应用到这些示例上。2.2.8 关于有符号数与无符号数的建议
就像我们看到的那样，有符号数到无符号数的隐式强制类型转换导致了某些非直观的行为。而这些非直观的特性经常导致程序错误，并且这种包含隐式强制类型转换的细微差别的错误很难被发现。因为这种强制类型转换是在代码中没有明确指示的情况下发生的，程序员经常忽视了它的影响。
下面两个练习题说明了某些由于隐式强制类型转换和无符号数据类型造成的细微的错误。练习题2.25 考虑下列代码，这段代码试图计算数组a中所有元素的和，其中元素的
/* WARTNG: This is buggy code*/
float sum_elements(float a],unsigned length){
float result-0;
for(1=0;1<= length-1;4t)result +- a[i];return result;)
当参数length等于0时，运行这段代码应该返回0.0。但实际上，运行时会遇到一个内存错误。请解释为什么会发生这样的情况，并且说明如何修改代码。练习题2.26 现在给你一个任务，写一个函数用来判定一个字符串是否比另一个更
长。前提是你要用字符串库函数 strlen，它的声明如下∶/* Prototype for library ftunction strlen*/size_t strlen(const char *a);最开始你写的函数是这样的∶
/* Determine whether string s is longer than string t*//* WARNING:This function is buggy */int strlonger(char *s,char *t)(
return strlen(s)- strlen(t)>0;
当你在一些示例数据上测试这个函数时，一切似乎都是正确的。进一步研究发现在头文件stdio.h中数据类型size_t是定义成 unsignedint的。A.在什么情况下，这个函数会产生不正确的结果?B.解释为什么会出现这样不正确的结果。C.说明如何修改这段代码好让它能可靠地工作。
第2章 信息的表示和处理 59
废注厂函数 getpername的安全漏洞
2002年，从事FreBSD开源操作系统项目的程序员意识到，他们对getpeername 画数的实现存在安全漏洞。代码的简化版本如下∶
1 /*
* FreeBSD's implementation of getpeernase()·/4
/* Declaration of library function mescpy */void *memcpy(void *dest,void *src,size_t n);/* Kernel memory region holding user-accessible data */wdefine KSIZE 1024 :
/* Copy at most maxlen bytes from kernel region to user buffer */int copy_from_kernel(void *user_dest,int max1len)(1s
/* Byte count len is minimum of buffer size and maxlen */int len =KSIZE<maxlen?KSIZE:maxlen;meacpy(user_dest,kbuf,len);18
return len;19
在这段代码里，第7行给出的是库函数memcpy的原型，这个函数是要将一段指定长度为n的字节从内存的一个区城复制到另一个区域。
从第14行开始的函数 copyfrom_kernel是要将一些操作系统内核维护的数据复制到指定的用户可以访问的内存区域。对用户来说，大多数内核维护的数据结构应该是不可读的，因为这些数据结构可能包含其他用户和系统上运行的其他作业的敏感信息，但是显示为kbuf的区域是用户可以读的。参数maxlen给出的是分配给用户的缓冲区的长度，这个缓冲区是用参数user_dest指示的。然后，第16行的计算确保复制的字
节数据不会超出源或者目标缓冲区可用的范图。
不过，假设有些怀有恶意的程序员在调用copy_from_kernel的代码中对maxlen 使用了负数值，那么，第16行的最小值计算会把这个值贼给len，然后len会作为参数n被传递给memcpy。不过，请注意参数n是被声明为数据类型sizet的。这个数据类型是在库文件stdio.h中（通过typedef）被声明的。典型地，对32位程序它被定义为unsignedint，对64位程序定义为unsignedlong。既然参数n是无符号的，那么
memcpy会把它当作一个非常大的正整数，并且试图将这样多字节的数据从内核区域复制到用户的缓冲区。虽然复制这么多字节（至少2个）实际上不会完成，因为程序会遇到进程中非法地址的错误，但是程序还是能读到它没有被授权的内核内存区城。
我们可以看到，这个问题是由于数据类型的不匹配造成的∶在一个地方，长度参数是有符号数;而另一个地方，它又是无符号数。正如这个例子表明的那样，这样的不匹配会成为缺陷的原因，甚至会导致安全漏洞。幸运的是，还没有案例报告有程序员在FreeBSD上利用了这个漏洞。他们发布了一个安全建议，"FreBSD-SA-02∶38.signed-error"，建议系统管理员如何应用补丁消除这个漏洞。要修正这个缺陷，只要将copy from_kernel的参数maxlen声明为类型sizet，也就是与memcpy的参数n一致。同时，我们也应该将本地变量len和返回值声明为size_t。

我们已经看到了许多无符号运算的细微特性，尤其是有符号数到无符号数的隐式转换，会导致错误或者漏洞的方式。避免这类错误的一种方法就是绝不使用无符号数。实际上，除了C以外很少有语言支持无符号整数。很明显，这些语言的设计者认为它们带来的麻烦要比益处多得多。比如，Java只支持有符号整数，并且要求以补码运算来实现。正常的右移运算符>被定义为执行算术右移。特殊的运算符>>被指定为执行逻辑右移。
当我们想要把字仅仅看做是位的集合而没有任何数字意义时，无符号数值是非常有用的。例如，往一个字中放入描述各种布尔条件的标记（flag）时，就是这样。地址自然地就
是无符号的，所以系统程序员发现无符号类型是很有帮助的。当实现模运算和多精度运算的数学包时，数字是由字的数组来表示的，无符号值也会非常有用。2.3整数运算
许多刚入门的程序员非常惊奇地发现，两个正数相加会得出一个负数，而比较表达式x<y和比较表达式x-y<0会产生不同的结果。这些属性是由于计算机运算的有限性造成的。理解计算机运算的细微之处能够帮助程序员编写更可靠的代码。2.3.1无符号加法
考虑两个非负整数z和y，满足0≤r，y<2"。每个数都能表示为w位无符号数字。然而，如果计算它们的和，我们就有一个可能的范围0≤x+y≤2+-2。表示这个和可能需要w+1 位。例如，图221展示了当x和y有4位表示时，函数x+y的坐标图。参数（显示在水平轴上）取值范围为0～15，但是和的取值范围为0~30。函数的形状是一个有坡度的平面（在两个维度上，函数都是线性的）。如果保持和为一个w+1位的数字，并且把它加上另外一个数值，我们可能需要w+2个位，以此类推。这种持续的"字长膨胀"意味着，要想完整地表示算术运算的结果，我们不能对字长做任何限制。一些编程语言，例如Lsp，实际上就支持无限精度的运算，允许任意的（当然，要在机器的内存限制之内）整数运算。更常见的是，编程语言支持固定精度的运算，因此像"加法"和"乘法"这样的运算不同于它们在整数上的相应运算。
图221 整数加法。对于一个4位的字长，其和可能需要5位