二.2 整数表示（2.1-2.4）

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

        图2-8列出了我们引入的数学术语，用于精确定义和描述计算机如何编码和操作整数。这些术语将在描述的过程中介绍，图在此处列出作为参考。

 二.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位机器的时代。固定大小的数据类型保证数值的范围与2-9给出的典型数值一致，包括负数与正数的不对称性。

 给C语言初学者        C、C++和Java中的有符号和无符号数

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

 二.2.2  无符号数的编码

        假设有一个整数数据类型有w位。我们可以将位向量写成x⃗，表示整个向量，或者写成[x（w-1），x（w-1），…，x0]，表示向量中的每一位。把x⃗看做一个二进制表示的数，就获得了x⃗的无符号表示。在这个编码中，每个位xi都取值为0或1，后一种取值意味着数值2^i应为数字值的一部分。我们用一个函数B2Uw（binary to unsigned的缩写，长度为w）来表示：

        原理：无符号数编码的定义

        对向量x⃗ = [x（w-1），x（w-2），…，x0]：                                              

在这个等式中，符号“≒”表示左边被定义为等于右边。函数B2Uw将一个长度为 w的0、1串映射到非负整数。举一个例子，图2-11展示的是下面几种情况下B2U给出的从位向量到整数的映射：

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

        让我们来考虑一下w位所能表示的值的范围。最小值是用位向量[00...0]表示，也就是整数值0，而最大值是用位向量[11...1]表示，也就是整数值UMAXw=2^w-1。以4位情况为例，UMAX4=B2U4([1111])=2^4-1=15。因此，函数B2Uw能够被定义为一个映射B2Uw：{0,1}w→{0，...，2^w-1}。

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

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

        函数B2Uw是一个双射。

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

二.2.3  补码编码

        对于许多应用，我们还希望表示负数值。最常见的有符号数的计算机表示方式就是补码（two`s - complement）形式。在这个定义中，将字的最高有效位解释为负权（negativeweight）。我们用函数B2Tw（binary to two·s-complement的缩写，长度为w）来表示：

        原理：补码编码的定义：

        最高有效位x（w-1）也称为符号位，它的“权重”为-2^（w-1），是无符号表示中权重的负数。符号位被设置为1时，表示值为负，而当设置为0时，值为非负。这里来看一个示例，图2-13展示的是下面集中情况下B2T给出的从位向量到整数的映射。 

        在这个图中，我们用向左指的条表示符号位具有负权重。于是， 与一个位向量相关联的数值是由可能得向左指的条和向右指的条加起来决定的。

        我们可以看到，图2-12和图2-13中的位模式都是一样的，对等式（2.2）和等式（2.4）来说也是一样的，但是当最高有效位是1时，数值是不同的，这是因为在一种情况中，最高有效位的权重是+8，而在另一种情况中，它的权重是-8。

        让我们考虑一下w位补码所能表示的值的范围。它能表示的最小值是位向量[10···0]（也就是设置这个位为负权，但是清除其他所有的位），其整数值为TMinw=-2^(w-1)。而最大值是位向量[01···1]（清除具有负权的位，而设置其他所有的位），其整数值为。以长度为4为例，我们有TMin4=B2T4([1000])=-2³=-8，而TMax4=B2T4=B2T4([0111])=2²+2¹+2º=4+2+1=7。

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

        原理：补码编码的唯一性

        函数B2Tw是一个双射。

        我们定义函数T2Bw（即“补码到二进制”）作为B2Tw的反函数。也就是说，对于每个数x，满足TMinw≤x≤TMaxw，则T2Bw（x）是x的（唯一的）w位模式。

练习题2.17        假设w=4，我们能给每个可能的十六进制数字赋予一个数值，假设用一个无符号或者补码表示。请根据这些表示，通过写出等式（2.1）和等式（2.3）所示的求和公式中的2的非零次幂，填写下表：

x向量		B2U4（x）	B2T4（x）
十六进制	二进制
0XE	[1110]	2³+2²+2¹=14	-2³+2²+2¹=-2
0x0	[0000]	0	0
0x5	[0101]	2²+2º=5	2²+2º=5
0x8	[1000]	2³=8	-2³=-8
0xD	[1101]	2³+2²+2º=13	-2³+2²+2º=-3
0xF	[1111]	2³+2²+2¹+2º=15	-2³+2²+2¹+2º=-1

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

        关于这些数字，有几点值得注意。第一，从图2-9和图2-10可以看到，补码的范围是不对称的：|TMin|=|TMax|+1，也就是说，TMin没有与之对应的正数。正如我们将会看到的，这导致了补码运算的某些特殊的属性，并且容易造成程序中细微的错误。之所以会有这样的不对称性，是因为一半的位模式（符号位设置为1的数）表示负数，而另一半（符号位设置为0的数）表示非负数。因为0是非负数，也就意味着能表示的整数比负数少一个。第二，最大的无符号数值刚好比补码的最大值的两倍大一点：UMaxw=2TMaxw+1。补码表示中所有表示负数的位模式在无符号表示中都变成了正数。图2-14也给出了常数-1和0的表示。注意-1和UMax有同样的位表示——一个全1的串。数值0在两种表示方式中都是全0的串。

        C语言标准并没有要求要用补码形式来表示有符号整数，但是几乎所有的机器都是这么做的。程序员如果希望代码具有最大的可移植性，能够在所有可能得机器上运行，那么除了图2-11所示的那些范围之外，我们不应该假设任何可表示的数值范围，也不应该假设有符号数会使用特殊的表示方式。另一方面，许多程序的书写都假设用补码来表示有符号数，并且具有图2-9和图2-10所示的“典型的”取值范围，这些程序也能够在大量的机器和编译器上移植。C库中的文件<limits.h>定义了一组常量，来限定编译器运行的这台机器的不同整型数据类型的取值范围。比如，它定义了常量INT_MAX、INT_MIN和UINT_MAX，它们描述了有符号和无符号整数的范围。对于一个补码的机器，数据类型int有w位，这些常量就对应了TMaxw、TMinw和UMaxw的值。

旁注        关于确定大小的整数类型的更多内容

        对于某些程序来说，用某个确定大小的表示来编码数据类型非常重要。例如，当编写程序，使得机器能够按照一个标准协议在因特网上通信时，让数据类型与协议指定的的数据类型兼容是非常重要的。我们前面看到了，某些C数据类型，特别是long型，在不同的机器上有不同的取值范围，而实际上C语言标准只指定了每种数据类型的最小范围，而不是确定的范围。虽然我们可以选择与大多数机器上的标准表示兼容的数据类型，但是这也不能保证可移植性。

        我们已经见过了32位和64位版本的确定大小的整数类型（图2-3），它们是一个更大数据类型类的一部分。ISO C99标准在文件stdint.h中引入了这个整数类型类。这个文件定义了一组数据类型，它们的声明形如intN_t和uintN_t，对不同的N值指定N位有符号和无符号整数。N的具体值与实现相关，但是大多数编译器允许的值为8/16/32和64。因此，通过将它的类型声明为uint16_t，我们可以无歧义地声明一个16位无符号变量，而如果声明为int32_t，就是一个32位有符号变量。

        这些数据类型对应着一组宏，定义了每个N的值对应的最小和最大值。这些宏名字形如INTN_MIN、INTN_MAX和UINTN_MAX。

        确定宽度类型的带格式打印需要使用宏，以与系统相关的方式扩展位格式串。因此，举个例子来说，变量x和y的类型是int32_t和uint64_t，可以通过调用printf来打印它们的值，如下所示：

        

printf("x = %" PRId32",y = %"PRIu64"\n",x,y);

编译为64位程序时，宏PRId32展开成字符串"d"，宏PRIu64则展开成两个字符串“l”“u”。当C预处理器遇到仅用空格（或其他空白字符）分隔的一个字符串常量序列时，就把它们串联起来。因此，上面的printf调用就变成了：

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

使用宏能保证：不论代码是如何被编译的，都能生成正确的字符串。

        关于整数数据类型的取值范围和表示，Java标准是非常明确的。它要求采用补码表示，取值范围与图2-10中64位的情况一样。在Java中，单字节数据类型称为byte，而不是char。这些非常具体的要求都是为了保证无论在什么机器上运行，Java程序都能表现地完全一样。

旁注        有符号数的其他表示方法

        有符号数还有两种标准的表示方法：

        反码（Ones' Complement）：除了最高有效位的权是-（2^（w-1）-1）而不是-2^（w-1），它和补码是一样的： 

        原码（Sign-Magnitude）：最高有效位是符号位，用来确定剩下的位应该取负权还是正权：

        这两种表示方法都有一个奇怪的属性，那就是对于数字0有两种不同的编码方式。这两种表示方法，把[00···0]都解释为+0。而值-0在原码中表示为[10···0]，在反码中表示为[11···1]。虽然过去产生过基于反码表示的机器，但是几乎所有的现代机器都使用补码。我们将看到在浮点数中有使用原码编码。

        请注意补码（Two's complement）和反码（Ones' complement）中撇号的位置是不同的。术语补码来源于这样一个情况，对于非负数x，我们用2^w-x（这里只有一个2）来计算-x的w位表示。术语反码来源于这样一个属性，我们用[111···1]-x（这里有很多个1）来计算-x的反码表示。

        为了更好地理解补码表示，考虑下面的代码：

short x = 12345;
short mx = -x;show_bytes((byte_pointer)&x,sizeof(short));
show_bytes((byte_pointer)&mx,sizeof(short));

         当在大端法机器上运行时，这段代码的输出为30 39和cf c7，指明x的十六进制表示为0x3039，而mx的十六进制表示为0xCFC7。将它们展开为二进制，我们得到x的位模式为[0011000000111001]，而mx的位模式为[1100111111000111]。如图2-15所示，等式（2.3）对这两个位模式生成的值为12345和-12345。

练习题2.18        在第3章中，我们将看到由反汇编器生成的列表，反汇编器是一种将可执行程序文件转换回可读性更好地ASCII码形式的程序。这些文件包含许多十六进制数字，都是用典型的补码形式来表示这些值。能够认识这些数字并理解它们的意义（例如它们是正数还是负数），是一项重要技巧。

        在下面的列表中，对于标号为A~I（标记在右边）的那些行，将指令名（sub、mov和add）右边显示的（32位补码形式表示的）十六进制值转换为等价的十进制值。 

4004d0: 48 81 ec e0 02 00 00    sub    $0x2e0,%rsp                A.
4004d7: 48 8b 44 24 a8          mov    -0x58(%rsp),%rax           B.
4004dc: 48 03 47 28             add    0x28(%rdi),%rax            C.
4004e0: 48 89 44 24 d0          mov    %rax,-0x30(%rsp)           D.
4004e5: 48 8b 44 24 78          mov    0x78(%rsp),%rax            E.
4004ea: 48 89 87 88 00 00 00    mov    %rax,0x88(%rdi)            F.
4004f1: 48 8b 84 24 f8 01 00    mov    0x1f8(%rsp),%rax           G.
4004f8: 00
4004f9: 48 03 44 24 08          add    0x8(%rsp),%rax
4004fe: 48 89 84 24 c0 00 00    mov    %rax,0xc0(%rsp)            H.
400505: 00
400506: 48 8b 44 d4 b8          mov    -0x48(%rsp,%rdx,8),%rax    I.

 二.2.4  有符号数和无符号数之间的转换

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

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

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

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

v = -12345,uv = 53191

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

        类似地，考虑下面的代码：

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

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

 u = 4294967295，tu = -1

        从图2-14我们可以看到，对于32位字长来说，无符号形式的4294967295（UMax32）和补码形式的-1的位模式是完全一样的。将unsigned强制类型转换成int，底层的位表示保持不变。

        对于大多数C语言的实现，处理同样字长的有符号数和无符号数之间相互转换的一般规则是：数值可能会改变，但是位模式不变。让我们用更数学化的形式来描述这个规则。我们定义函数U2Bw和T2Bw，它们将数值映射为无符号数和补码形式的位表示。也就是说，给定0≤x≤UMax范围内的一个整数x，函数U2Bw（x）会给出x的唯一的w位无符号表示。相似地，当x满足TMinw≤x≤TMaxw，函数T2Bw（x）会给出x的唯一的w位补码表示。

        现在，将函数T2Uw定义为T2Uw（x）= B2Uw（T2Bw（x））。这个函数的输入是一个TMinw~TMaxw的数，结果得到一个0~UMaxw的值，这里两个数有相同的位模式，除了参数是无符号的，而结果是以补码表示的。类似地，对于0~UMaxw之间的值x，定义函数

U2Tw为U2Tw（x）= B2Tw（U2Bw（x））。生成一个数的无符号表示和x的补码表示相同。

        继续我们前面的例子，从图2-15中，我们看到T2U16（-12345）= 53191，并且U2T16（53191）= -12345。也就是说，十六进制表示写作0XCFC7的16位位模式既是-12345的补码表示，又是53191的无符号表示。同时请注意12345+53191=65536=2^16。这个属性可以推广到给定位模式的两个数值（补码和无符号数）之间的关系。类似地，从图2-14我们看到T2U32（-1）= 4294967295，并且U2T32（4294967295）= -1.也就是说，无符号表示中的UMax有着和补码表示的-1相同的位模式。我们在这两个数之间也能看到这种关系：1+UMaxw = 2^w。

        接下来，我们看到函数U2T描述了从无符号数到补码的转换，而T2U描述的是补码到无符号的转换。这两个函数描述了在大多数C语言实现中这两种数据类型之间的强制类型转换效果。

练习题2.19        利用你解答练习题2.17时填写的表格，填写下列描述函数T2U4的表格。

x	T2U4（x）
-8	8
-3	13
-2	14
-1	15
0	0
5	5

        通过上述这些例子，我们可以看到给定位模式的补码与无符号数之间的关系可以表示为函数T2U的一个属性：

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

        对满足TMinw≤x≤TMaxw的x有：

        比如，我们看到T2U16（-12345）= -12345+2^16=53191，同时

T2Uw（-1）=-1+2^w=UMaxw 。

        该属性可以通过比较公式（2.1）和公式（2.3）推导出来。

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

        比较等式（2.1）和等式（2.3），我们可以发现对于位模式x，如果我们计算B2Uw（x）-B2Tw（x）只差，从0到w-2的位的加权和将互相抵消掉，剩下一个值：B2Uw（x）-B2Tw（x）=x[w-1]·（2^(w-1)-（-2^（w-1）））= x[w-1]·2^w。这就得到一个关系：B2Uw（x）= x[w-1]·2^w+B2Tw（x）。我们因此就有：

        根据公式（2.5）的两种情况，在x的补码表示中，位x[w-1]决定了x是否为负。

        比如说，图2-16比较了当w=4时函数B2U和B2T是如何将数值变成位模式的。对补码来说，最高有效位是符号位，我们用带向左箭头的条来表示。对于无符号数来说，最高有效位是正权重，我们用带向右的箭头的条来表示。从补码变为无符号数，最高有效位的权重从-8变为+8。因此，补码表示的负数如果看成无符号数，值会增加2^4=16.因而，-5变成了+11，而-1变成了+15。 

        图2-17说明了函数T2U的一般行为。如图所示，当将一个有符号数映射为它相应的无符号数时，负数就被转换成了大的正数，而非负数会保持不变。 

练习题2.20        请说明等式（2.5）是如何应用到解答题2.19时生成的表格中的各项的。反过来看，我们希望推导出一个无符号数u和与之对应的有符号数U2Tw（u）之间的关系：

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

        对满足0≤u≤UMaxw的u有： 

         该原理证明如下：

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

        设u=U2Bw（u），这个位向量也是U2Tw（u）的补码表示。公式2.1和公式2.3结合起来有

        在u的无符号表示中，对公式（2.7）的两种情况来说，位u[w-1]决定了u是否大于TMaxw=2^(w-1)-1。

        图2-18 说明了函数U2T的行为。对于小的数（≤TMaxw），从无符号到有符号的转换将保留数字的原值。对于大的数（＞TMaxw），数字将被转换为一个负数值。

        总结一下，我们考虑无符号数与补码表示之间互相转换的结果。对于在范围0≤x≤TMaxw之内的值x而言，我们得到T2Uw（x）=x和U2Tw（x）=x。也就是说，在这个范围内的数字有相同的无符号和补码表示。对于这个范围以外的数值，转换需要加上或者减去2^w。例如，我们有T2Uw（-1）=-1+2^w=UMaxw——最靠近0的负数映射为最大的无符号数。在另一个极端，我们可以看到T2Uw（TMinw）=-2^（w-1）+2^w=2^(w-1)=TMaxw+1——最小的负数映射为一个刚好在补码的正数范围之外的无符号数。使用图2-15的示例，我们能看到T2U16(-12345)=65536+-12345=53191。