澳门新葡亰信誉平台游戏CSAPP复习(1月23日)

by admin on 2020年1月20日

几乎所有的机器上,多字节对象都被存储为连续的字节序列,对象的地址为所使用字节中最小的地址,例如:int
型变量x的地址为0X100,即地址表达式&X的值为0X100,那么x的4个字节将被存储在存储器的0X100,0X101,0X102和0X103的位置。

对二值信号进行存储和执行计算的电子电路非常简单和可靠。

第二章   信息的表示和处理

 

重要的三中数字表示:

1   信息存储

·大多数计算机使用8位的块,或者字节(byte),作为最小的可寻址的内存单位,而不是访问内存中单独的位。

·机器级程序将内存视为一个非常大的字节数组,称为虚拟内存。内存的每个字节都由一个唯一的数字来标识,称为它的地址,所有可能地址的集合称为虚拟地址空间。(只是一个展现给机器级程序的概念性映像)

考虑一个十位整数,位表示为[Xw-1,Xw-2,…,X1,X0],其中Xw-1是最高有效位。X0为最低有效位,若w是8的倍数,这些位可被分组为字节,期中最高有效字节包括位[Xw-1,Xw-2,…,Xw-8],最低有效位包括[X7,X6,…,X1,X0],其他字节包括中间的位。最低有效字节在最前面的方式为小端法,最高有效位在最前面的方式为大端法。大多数Intel兼容的机采用小端法,IBM和Sun
Microsystems的机器大部分采用大端法,但是排列表示一个对象的自己诶的规则不是按照企业界限严格划分的,许多比较新的微处理器使用双端法,即可以把他们配制成作为大端或者小端的机器运行。

  1. 无符号 — 基于传统的二进制表示法,表示大于或者等于零的数字。
  2. 补码 —
    表示有符号整数的最常见方式,有符号整数就是可以为正或者为负得数字。
  3. 浮点数 — 表示实数的科学记数法的以二为基数的版本。

2   简单概念

1)十六进制(0x,0X)

2)字数据大小

每台计算机都有一个字长,指明指针数据的标称大小。因为虚拟地址是以这样的一个字来编码的,所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。如某机器字长为w位,虚拟地址的范围为0~(2^w)-1(32位程序和64位程序区别:在于该程序时如何编译的,而不是其运行的机器类型)

3)寻址和字节顺序

·对象的地址以及如何排列

·例如:假设一个类型的int型的变量
x的地址为0x100,则x的(4)个字节将被存储在内存中的位置。

·小端法:最低有效字节在最前面的方式

·大端法:最高有效字节在最前面的方式

(二进制代码不兼容)

4)c语言中的运算

位级运算

逻辑运算

移位运算:机器支持两种形式的右移,即逻辑右移和算术右移。

逻辑右移:在左端补k个零。

算术右移:在左端补k个最高有效位的值。

(注:几乎所有的编译器/机器组合都对有符号数使用算术右移。对于无符号数,必须采用逻辑右移。)

 

计算机的表示法是用有限数量的位来对一个数字编码。由于表示的精度有限,浮点运算是不可结合的。

3   整数表示

用位来编码整数的两种方式:一种只能表示非负数,而另一种能够表示负数,零和正数。负数的范围比正数的范围大一。

1)无符号数的编码

11—>[1011]; 双射;双向编码唯一性;

2)补码编码

最常见的有符号数的计算机表示方式就是补码,将字的最高有效位解释为负权。

B2T4([1011])=(-1)*2^3+0*2^2+1*2^1+1*2^0;

范围:-2^(w-1)~2^(w-1)-1;

双射,补码编码唯一性。

注:-1与Umax有同样的位表示—-一个全1的串。数值0在两种表示方法中都是全0的串。

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

强制类型转换的结果保持位值不变,只是改变了解释这些位的方式。即在c语言中,处理同样字长的有符号数和无符号数之间相互转换的一般规则是:数值可能会改变,但是位模式不改变。

1  原理:补码转换为无符号数:

对满足TMin<=x<=TMax的x有:T2Uw(x)={x+2^w,x<0},{x,x>=0};

(负数就被转换为了大的正数,而非负数会保持不变。)

 2  原理:无符号数转换为补码:

对满足0<=u<=UMax的u有:

U2Tw(u)={u,u<=TMax},{u-2^w,u>TMax};

(对于小的数,从无符号数到有符号数的转换将保留数字的原值。对于大的数,数字将被转换为一个负值。)

4)c语言中的有符号数与无符号数

几乎所有的机器都使用补码,转换时大多数系统遵循的原则是底层的位保持不变。

c语言对同时包含有符号和无符号数表达式的处理方式:

当执行一个运算时,如果它的一个运算数是有符号的而另一个是无符号的,那么c语言会隐式地将有符号参数强制类型转换为无符号数,并假设这两个数都是非负的,来执行这个运算。

5)扩展一个数字的位表示

1 无符号数的零扩展

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

2 补码数的符号扩展

要将一个补码数转换成一个更大的数据类型,可以执行符号扩展,在表示中添加最高有效位的值。

注:c语言标准要求的规则:

从一个数据大小到另一个数据大小的转换,以及无符号和有符号数字之间的转换的相对顺序能够影响一个程序的行为。

例:当把short转换成unsigned时,我们先要改变大小,之后再完成从有符号到无符号的转换。也就是说

(unsigned)sx 等价于(unsigned)(int)sx,再求值。

6)截断数字

截断一个数字可能会影响它的值—–溢出的一种形式。

1 截断无符号数

x :[Xw-1,Xw-2,……X0]   ,x1表示x截断为k位的结果,则x1 
:[Xk-1,Xk-2,……,X0]。则它们所表示的无符号值大小关系为:x1=x
mod2^k

2 截断补码数值

也具有相同的属性,只不过要将最高位转换为符号位。

x :[Xw-1,Xw-2,……X0]   ,x1表示x截断为k位的结果,则x1 
:[Xk-1,Xk-2,……,X0]。x=B2Uw(x),x1=B2Tk(x1),则x1=U2Tk(x mod
2^k);

:将数值 x=53191从 int 转换为 short,由于2^16=65536>=x,所以有
x mod2^16  =x。第二步,把这个数转换为16位补码,

得到x2=53191-65536=(-)12345。

7)整数运算

1  无符号数加法

简单丢弃2^(w-1)位就可以计算出模2^w。

算术运算溢出:指完整的整数结果不能放到数据类型的字长限制中去。

x+y=【x+y或者x+y-2^w;(取决于有无溢出,溢出丢弃)】

检测有无溢出:结果小于其中一个加数

无符号数取反:-x=[x或者2^w-x];取决于x是否为0

2  补码加法

x+y=【x+y-2^w;x+y;x+y+2^w】(正溢出,正常,负溢出)

正溢出:x+y超过TMax。负溢出:x+y小于TMin。

检测有无溢出:x>0,y>0,s<0。或x<0,y<0,s>=0。

补码的非:对w位的补码加法;来说,TMin是自己的加法的逆,而对于其他任何数值,x都有-x作为其加法的逆。

3  无符号乘法

c语言中的无符号乘法被定义为产生w位的值,就是2w位的整数乘积的低w位来表示的值。

将一个无符号数截断为w位等价于计算该值模2^w。

x*y=(x*y)mod  2^w。

4  补码乘法

将一个补码说截断为w位相当于先计算该值,模2^w,再把无符号数转换为补码。

x*y=U2Tw【(x*y)mod  2^w】。

5  乘以常数

整数乘法指令相当慢,需要10个或者更多个时钟周期,然而其他整数运算(加法,减法,位级运算和移位)只需要一个时钟周期。因此,编译器使用了一项重要的优化,即试着用移位和加法运算组成的组合来代替乘以常数因子的乘法

左移一个数值等价于执行一个与2的幂相乘的无符号乘法。补码乘法类似。

例:x*14   因为14=2^3+2^2+2^1,所以编译器会把乘法写为
(x<<3+x<<2+x<<1),将一个乘法替换为三个移位和两个加法。

或者14=2^4-2^1,所以  x<<4-x<<1.两个移位和一个减法。

6  除以2的幂

整数除法要比整数乘法更慢—–需要30个或者更多的时钟周期。

除以2的幂,用右移。

1 无符号除法   x>>k(逻辑移位),产生的数值左趋近。

2
补码除法x>>k(算术移位),向下舍入。或者(x+(1<<k)-1)>>k
产生数值向上舍入。第二种方法相当于在执行算术右移之前加上一个适当的偏置量会导致结果正确舍入。

8)浮点数运算

1  二进制小数表示

2  浮点数表示

用V=(-1)^s   *  M * 2^E的形式表示一个数。

符号位:s决定是负数(s=1)还是正数(s=0)。

尾数:M是一个二进制小数,它的范围是1~2或者0~1。

阶码:E的作用是对浮点数加权,这个权重是2的E次幂。

即将浮点数的位表示划分为三个字段,分别对这些值进行编码:

·一个单独的符号位s直接编码符号s。

·k位的阶码字段exp=……编码E。

·n位小数字段frac=……编码尾数M,但是编码出来的值也依赖于阶码字段的值是否为0.

注:单精度float中,s、exp、frac字段分别为1位,k为8位,和n为23位,得到了32位的表示。

注:双精度double中,s、exp、frac字段分别为1位,k为11位,和n为52位,得到了64位的表示。

三种情况:

1、 规格化的值

最普遍情况。当exp的位模式既不全为0,也不全为1,。在这种情况中,阶码字段被解释为以偏置形式表示的有符号整数,也就是说,阶码的值是

E=e-Bias,其中e是无符号数,其位表示为ek-1ek-2……e0,而Bias是一个等于2^(k-1)-1的偏置值,(127or1023)。

小数字段frac被解释为f,尾数定义为M=1+f。即隐含的以1开头的表示。这种表示方法,是一种轻松的获得一个额外精度的技巧。既然第一位总是1,那么我们就不需要显式的表示它。

2、 非规格化的值

当阶码域为全0时,所表示的数是非规格化形式。阶码值是E=1-Bias,而尾数的值是M=f,也就是小数字段的值,不包含隐式地开头的1。

两个功能:表示0和那些非常接近0的数。

3、特殊值

最后一类数值是阶码全为1的时候出现的。当小数域全为0时,得到的值表示无穷。当小数域为非零时,结果值被称为“NaN”,即“不是一个数”。

3   舍入

因为表示方法限制了浮点数范围与精度,所以浮点运算只能近似地表示实数运算。

关键问题是在两个可能值的中间确定舍入方向。

向偶数舍入,即向最近的值舍入,是默认的方式。向偶数舍入的方式采用的方法是:它将数字向上或者向下舍入,使得结果的最低有效数字是偶数。这种方法将1.5和2.5都舍入为2,避免了一定的统计误差。向0舍入方式是把正数向下舍入,把负数向上舍入。向下舍入,向上舍入。

4  浮点数运算

运算不可结合。

浮点加法不具有结合性。满足单调性。满足交换律

浮点乘法可交换,不具有可结合性。浮点乘法在加法上不具备分配性。

例:使用单精度浮点,表达式(3.14+le10)-le10求值得到0.0。(因为舍入,值3.14会丢失)另一方面,表达式3.14+(le10-le10)得出值3.14。

例:单精度浮点情况:表达式 
le20*(le20-le20)求值为0.0,而le20*le20-le20*le20会得到NaN。

                                                                                            
[第二章完]

如果对第一个参数求值就能确定表达式的结果,那么逻辑运算的就不会对第二个参数求值。

整数运算和浮点运算会有不同的数学属性是因为他们处理数字表示有限性的方式不同–整数的表示虽然只能编码一个相对较小的数值范围,但是这种表示是精确的;而浮点数虽然可以编码一个较大的数值范围,但是这种表示只是近似的。
整数运算–精确的。
浮点运算–非精确的。

 

2.1 信息存储

大多数计算机使用8位的块,或者字节,作为最小的可寻址的存储器单位,而不是在存储器中访问单独的位。

C语言中一个指针的值(无论是指向一个整数、一个结构或某个其他程序对象)都是以某个存储块的第一个字节的虚拟地址。

在C语言中,以0x或者0X开头得数字常量被认为是十六进制的值。字符A~F既可以是大写,也可以是小写,甚至是大小写混合。

十六进制转换为二进制:首先将每4位分为一组,再把它转换为十六进制。不过需要注意,如果位得总数不是4的倍数,最左边得一组可以少于4位,前面用0补足,然后将每个4位组转换为相应的十六进制数字。

当值x是2的非负整数n次幂时,也就是x=2^n,我们可以很容易地将x携程十六进制形式,只要记住:
x的二级制表示就是1后面跟n个0.
十六进制数字0代表4个二级制0。
所以,当n表示成i+4j的形式,其中0≤i≤3时,我们可以把写成开头得十六进制数字为
1(i=0)、2(i=1)、4(i=2)、8(i=3),后面跟随着j个十六进制的0.
比如: x=2048=2^11
于是有: n = 11 = 3+4*2 从而得到十六进制表示 0x800


C语言中的移位运算:对于一个位表示为[Xn-1,Xn-2,…,X0]的操作数X,C表达式x<<k;会生成一个值,其位表示为[Xn-k-1,Xn-k-2,…,X0,0,…,0],即x向左移动k位,丢弃最高位的k位,并在右端补k个0,移位量应是一个0~n-1之间的数,移位的运算是从左到右可结合的。

2.1.2 字

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

右移位运算x>>k;的行为有些微妙,一般而言机器支持两种形式的右移位:逻辑右移和算术右移。逻辑右移在左端补k个0,得到[0,0,…,0,Xn-1,Xn-2,…,Xk],算术右移在最左端补k个最高位有效值,得到[Xn-1,Xn-1,…,Xn-1,Xn-2,…,Xk].C语言标准没有确定应该用哪种类型的右移,对于无符号数据(用unsigned声明的正兴对象)右移必须是逻辑的。对于有符号数据,算术的和逻辑的都可以。实际上几乎所有的编译器/机器组合都对有符号数据使用算术右移。

2.1.3 数据大小

C的数据类型大小:
char — 1个字节。
short int — 2个字节
int — 4个字节
long int– 使用机器的全字长,如果是32位则4字节,如果64为则8字节
long long int–
允许64位整数,使用8个字节。对于32位机器而言,编译器必须把这种数据类型的操作编译成一系列32位操作的代码。
float — 4个字节
double– 8个字节
char* — 机器的全字长,32位是4个字节,64位是8个字节。

需要注意:许多程序员假设一个声明为int类型得程序对象能被用来存储一个指针。这在大多数32位得机器上能正常工作,但是在一台64位得机器上却会导致问题。(因为64位下int是4字节,而指针是8字节。)

 

2.1.4 寻址和字节顺序

在几乎所有的机器上,多字节对象都被存储为连续的字节序列,对象的地址为嗦使用字节中最小的地址。
例如:一个类型为int得变量x的地址为0x100,也就是说,地址表达式&x的值为0x100。那么,x的4个字节被存储在存储器的0x100,0x101,ox102,ox103位置。

在存储器存储中,有大端法和小端法的区分:
大端法 — 最高有效字节在最前面。IBM和SUN采用此种规则。
小端法 — 最低有效字节在最前面。Intel兼容机采用此种规则。
许多比较新的微处理器使用双端法,也就是说可以把他们配置为大端或者小端的机器运行。

对于int类型的x,位于地址0x100处,它得十六进制值为0x1234567
,地址范围为0x100~0x103字节,其排列顺序依赖于机器类型。
大端法 — 01(ox100) 23(0x101) 45(0x102) 67(0x103)
小端法 — 67(ox100) 45(0x101) 23(0x102) 01(0x103)

一般情况下,机器所使用的字节顺序对我们来说是透明的,不可见的。无论使用哪种类型的机器编译程序都会得到同样的结果。
除非在编写网络程序的时候,才需要注意这个问题。
为了避免这类问题,网络应用程序的代码编写必须遵守已建立的关于字节顺序的规则,以确保发送机器将它得内部表示转换成网络标准,而接收方机器则将网络标准转换为它得内部表示。

对于任一位向量a,有a^a =0 。

对大多数C语言的实现而言,处理同样字长的有符号数和无符号数之间的转换的一般规则是:数值可能会改变,但是位模式不变。

2.1.9 C语言中的位运算和逻辑运算

C语言中的位运算:
| 或
& 与
~ 取反
^ 异或 当p=1且q=0,或者p=0且q=1时, p^q = 1

C语言中的逻辑运算:
|| 或 or
&& 与 and
! 非 not

逻辑运算认为所有非零的参数都表示true,而参数0表示false。

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

 

2.1.0 C语言中的移位运算

左移、右移
右移支持两种:逻辑右移和算术右移。
逻辑右移在左端补0。
算术右移是在左端补最高有效位的值。
x = 01100001 10010101
x》4 (逻辑右移) 00000110 00001001
x》4 (算术右移) 00000110 11111001

C语言中并没有明确定义应该使用哪种类型的右移。对于无符号数据(也即是以
unsigned声明开通的整型对象),逻辑右移是必须得。
几乎所有的编译器、机器组合都对有符号数据使用算术右移,且许多程序员也都假设机器会使用算术右移。

另外,Java对于如何进行右移有明确的定义。
x》k 会将x算术右移k个位置。
x>>>k 会对x做逻辑右移。

在许多机器上,当移位位数k超过了机器的字长w时,移位移的是w mod k 位。
比如在32位机器上移位40位,则只是移8位。

int lval = oxFEDCBA98 <<32 = oxFEDCBA98
int aval = oxFEDCBA98 >>36 = 0xFFEDCBA9
unsigned uval = oxFEDCBA98u >>40 = ox00FEDCBA

不过C语言没有对这种行为进行保障,所以移位数量应该保持小于字长。
另一方面,Java特别要求位移数量应该按照之前讲的求模的方法来计算。

加法减法的优先级比移位运算要高。
所以: 1<<2+3<<4 = 1<<(2+3)<<4 =
(1<<(2+3))<<4 = 512
在拿不准时,请用括号表明运算顺序。

当执行一个运算时,如果它的一个运算数是有符号的,而另一个是无符号的,那么C语言会隐式的将有符号参数强制转换成无符号数,并假设这两个数都是非负的,来执行这个运算。

 

将一个无符号数转换成一个更大的数据类型,只需要简单的在表示开头添加0,这种运算称为零扩展(zero
expression);将一个补码数字转换为一个更大的数据类型,可以执行符号扩展(sign
expression),规则是在表示中添加最高位有效位的值的副本,如原始值的位表示为[Xw-1,Xw-2,…,X0],扩展后的表示就为[Xw-1,…,Xw-1,Xw-1,Xw-2,…,X0].

 

一个算术运算的溢出是指完整的整数结果不能放到数据类型的字长限制中去。

 

进程是操作系统对一个正在运行的程序的一种抽象。

 

hello.c                                    
hello.i                          
hello.s                       hello.o  

————–>预处理器(cpp)————->编译器(ccl)——–>汇编器(as)———–>连接器

源程序(文本)                        被修改的源程序                  汇编程序                  可重定位的目标程序

                                              (文本)                         (文本)              (二进制 )               

         hello

(ld)———————->

        可执行的目标程序(二进制)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图