韩国网站源码下载深圳网站建设案例

当前位置： 首页 > news >正文

韩国网站源码下载,深圳网站建设案例,百度后台登录,软件设计培训在本节中#xff0c;我们描述用位来编码整数的两种不同的方式#xff1a;一种只能表示非负数#xff0c;而另一种能够表示负数、零和正数。后面我们将会看到它们在数学属性和机器级实现方面密切相关。我们还会研究扩展或者收缩一个已编码整数以适应不同长度表示的效果。 图2…        在本节中我们描述用位来编码整数的两种不同的方式一种只能表示非负数而另一种能够表示负数、零和正数。后面我们将会看到它们在数学属性和机器级实现方面密切相关。我们还会研究扩展或者收缩一个已编码整数以适应不同长度表示的效果。 图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⃗表示整个向量或者写成[xw-1xw-1…x0]表示向量中的每一位。把x⃗看做一个二进制表示的数就获得了x⃗的无符号表示。在这个编码中每个位xi都取值为0或1后一种取值意味着数值2^i应为数字值的一部分。我们用一个函数B2Uwbinary to unsigned的缩写长度为w来表示 原理无符号数编码的定义 对向量x⃗ [xw-1xw-2…x0]                                               在这个等式中符号“≒”表示左边被定义为等于右边。函数B2Uw将一个长度为 w的0、1串映射到非负整数。举一个例子图2-11展示的是下面几种情况下B2U给出的从位向量到整数的映射 在图中我们用长度为2 ^i的指向右侧箭头的条表示每个位的位置i。每个位向量对应的数值就等于所有值为1的位对应的条的长度之和。 让我们来考虑一下w位所能表示的值的范围。最小值是用位向量[00…0]表示也就是整数值0而最大值是用位向量[11…1]表示也就是整数值UMAXw2^w-1。以4位情况为例UMAX4B2U4([1111])2^4-115。因此函数B2Uw能够被定义为一个映射B2Uw{0,1}w→{0…2^w-1}。 无符号数的二进制表示有一个很重要的属性也就是每个介于0~2^w-1之间的数都有唯一一个w位的值编码。例如十进制值11作为无符号数只有一个4位的表示即[1011]。我们用数学原理来重点讲述它先表述原理再解释。 原理无符号数编码的唯一性 函数B2Uw是一个双射。 数学术语双射是指一个函数f有两面它将数值x映射为数值y即xf(x)但它也可以反向操作因为对每一个y而言都有唯一一个数值x使得fxy。这可以用反函数f⁻¹来表示在本例中即xf⁻¹(y)。函数B2Uw将每一个长度为w的位向量都映射为0~2^w-1之间的一个唯一值反过来我们称其为U2Bw即“无符号数到二进制”在0~2^w-1之间的每一个整数都可以映射为一个唯一的长度为w的位模式。 二.2.3  补码编码 对于许多应用我们还希望表示负数值。最常见的有符号数的计算机表示方式就是补码twos - complement形式。在这个定义中将字的最高有效位解释为负权negativeweight。我们用函数B2Twbinary to two·s-complement的缩写长度为w来表示 原理补码编码的定义 最高有效位xw-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为例我们有TMin4B2T4([1000])-2³-8而TMax4B2T4B2T4([0111])2²2¹2º4217。 我们可以看出B2Tw是一个从长度为w的位模式到TMinw和TMaxw之间数字的映射写作B2Tw{0,1}w→{TMinw···TMaxw}。同无符号表示一样在可表示的取值范围内的每个数字都有一个唯一的w位的补码编码。这就导出了无符号数相似的补码数原理 原理补码编码的唯一性 函数B2Tw是一个双射。 我们定义函数T2Bw即“补码到二进制”作为B2Tw的反函数。也就是说对于每个数x满足TMinw≤x≤TMaxw则T2Bwx是x的唯一的w位模式。 练习题2.17        假设w4我们能给每个可能的十六进制数字赋予一个数值假设用一个无符号或者补码表示。请根据这些表示通过写出等式2.1和等式2.3所示的求和公式中的2的非零次幂填写下表 x向量B2U4xB2T4x十六进制二进制0XE[1110]2³2²2¹14-2³2²2¹-20x0[0000]000x5[0101]2²2º52²2º50x8[1000]2³8-2³-80xD[1101]2³2²2º13-2³2²2º-30xF[1111]2³2²2¹2º15-2³2²2¹2º-1 图2-14展示了针对不同字长几个重要数字的位模式和数值。前三个给出的是可表示的整数范围用UMaxw、TMinw和TMaxw来表示。在后面的讨论中我们还会经常引用到这三个特殊的值。如果可以从上下文中推断出w或者w不是讨论的主要内容时我们会省略下标w直接引用UMaxTMin和TMax。 关于这些数字有几点值得注意。第一从图2-9和图2-10可以看到补码的范围是不对称的|TMin||TMax|1也就是说TMin没有与之对应的正数。正如我们将会看到的这导致了补码运算的某些特殊的属性并且容易造成程序中细微的错误。之所以会有这样的不对称性是因为一半的位模式符号位设置为1的数表示负数而另一半符号位设置为0的数表示非负数。因为0是非负数也就意味着能表示的整数比负数少一个。第二最大的无符号数值刚好比补码的最大值的两倍大一点UMaxw2TMaxw1。补码表示中所有表示负数的位模式在无符号表示中都变成了正数。图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]。虽然过去产生过基于反码表示的机器但是几乎所有的现代机器都使用补码。我们将看到在浮点数中有使用原码编码。         请注意补码Twos 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声明为intu声明为unsigned。表达式unsignedx会将x的值转换成一个无符号数值而intu将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 4294967295tu -1 从图2-14我们可以看到对于32位字长来说无符号形式的4294967295UMax32和补码形式的-1的位模式是完全一样的。将unsigned强制类型转换成int底层的位表示保持不变。 对于大多数C语言的实现处理同样字长的有符号数和无符号数之间相互转换的一般规则是数值可能会改变但是位模式不变。让我们用更数学化的形式来描述这个规则。我们定义函数U2Bw和T2Bw它们将数值映射为无符号数和补码形式的位表示。也就是说给定0≤x≤UMax范围内的一个整数x函数U2Bwx会给出x的唯一的w位无符号表示。相似地当x满足TMinw≤x≤TMaxw函数T2Bwx会给出x的唯一的w位补码表示。 现在将函数T2Uw定义为T2Uwx B2UwT2Bwx。这个函数的输入是一个TMinw~TMaxw的数结果得到一个0~UMaxw的值这里两个数有相同的位模式除了参数是无符号的而结果是以补码表示的。类似地对于0~UMaxw之间的值x定义函数 U2Tw为U2Twx B2TwU2Bwx。生成一个数的无符号表示和x的补码表示相同。 继续我们前面的例子从图2-15中我们看到T2U16-12345 53191并且U2T1653191 -12345。也就是说十六进制表示写作0XCFC7的16位位模式既是-12345的补码表示又是53191的无符号表示。同时请注意1234553191655362^16。这个属性可以推广到给定位模式的两个数值补码和无符号数之间的关系。类似地从图2-14我们看到T2U32-1 4294967295并且U2T324294967295 -1.也就是说无符号表示中的UMax有着和补码表示的-1相同的位模式。我们在这两个数之间也能看到这种关系1UMaxw 2^w。 接下来我们看到函数U2T描述了从无符号数到补码的转换而T2U描述的是补码到无符号的转换。这两个函数描述了在大多数C语言实现中这两种数据类型之间的强制类型转换效果。 练习题2.19        利用你解答练习题2.17时填写的表格填写下列描述函数T2U4的表格。 xT2U4x-88-313-214-1150055 通过上述这些例子我们可以看到给定位模式的补码与无符号数之间的关系可以表示为函数T2U的一个属性 原理补码转换为无符号数 对满足TMinw≤x≤TMaxw的x有 比如我们看到T2U16-12345 -123452^1653191同时 T2Uw-1-12^wUMaxw 。 该属性可以通过比较公式2.1和公式2.3推导出来。 推导补码转换为无符号数 比较等式2.1和等式2.3我们可以发现对于位模式x如果我们计算B2Uwx-B2Twx只差从0到w-2的位的加权和将互相抵消掉剩下一个值B2Uwx-B2Twxx[w-1]·2^(w-1)–2^w-1 x[w-1]·2^w。这就得到一个关系B2Uwx x[w-1]·2^wB2Twx。我们因此就有 根据公式2.5的两种情况在x的补码表示中位x[w-1]决定了x是否为负。 比如说图2-16比较了当w4时函数B2U和B2T是如何将数值变成位模式的。对补码来说最高有效位是符号位我们用带向左箭头的条来表示。对于无符号数来说最高有效位是正权重我们用带向右的箭头的条来表示。从补码变为无符号数最高有效位的权重从-8变为8。因此补码表示的负数如果看成无符号数值会增加2^416.因而-5变成了11而-1变成了15。  图2-17说明了函数T2U的一般行为。如图所示当将一个有符号数映射为它相应的无符号数时负数就被转换成了大的正数而非负数会保持不变。  练习题2.20        请说明等式2.5是如何应用到解答题2.19时生成的表格中的各项的。反过来看我们希望推导出一个无符号数u和与之对应的有符号数U2Twu之间的关系 原理无符号数转换为补码 对满足0≤u≤UMaxw的u有  该原理证明如下 推导无符号数转换为补码 设uU2Bwu这个位向量也是U2Twu的补码表示。公式2.1和公式2.3结合起来有 在u的无符号表示中对公式2.7的两种情况来说位u[w-1]决定了u是否大于TMaxw2^(w-1)-1。 图2-18 说明了函数U2T的行为。对于小的数≤TMaxw从无符号到有符号的转换将保留数字的原值。对于大的数TMaxw数字将被转换为一个负数值。 总结一下我们考虑无符号数与补码表示之间互相转换的结果。对于在范围0≤x≤TMaxw之内的值x而言我们得到T2Uwxx和U2Twxx。也就是说在这个范围内的数字有相同的无符号和补码表示。对于这个范围以外的数值转换需要加上或者减去2^w。例如我们有T2Uw-1-12^wUMaxw——最靠近0的负数映射为最大的无符号数。在另一个极端我们可以看到T2UwTMinw-2^w-12^w2^(w-1)TMaxw1——最小的负数映射为一个刚好在补码的正数范围之外的无符号数。使用图2-15的示例我们能看到T2U16(-12345)65536-1234553191。