Jialong's Blog
沉潜 自由 追寻幸福
csapp: 2.信息的表示和处理(部分完成)
书籍《深入理解计算机系统》阅读学习笔记

第一部分内容:程序结构和执行

我们需要用方法表示基本数据类型,然后考虑机器级指令如何操作这样的数据,以及编译器如何将C程序翻译成这样的指令。接下来研究集中处理器的方法,使得我们能够更好地了解硬件资源如何被用来执行指令。

信息存储

十六进制表示法及转换

二进制和十进制对描述位模式来说都不方便,因此采用16进制数(hex)来表示位模式。

C语言中16进制数以0X或0x开头,字符‘A’~‘F’既可以是大写也可以是小写。

二进制和十六进制之间的转换较为简单,不再赘述。

十进制和十六进制数之间的转换要反复利用乘法和除法进行处理:

  • 从十进制到十六进制:反复用16除十进制数
  • 从十六进制到十进制:用相应的16的幂乘以每个十六进制数。

字数据大小

字长指明指针数据的标称大小。虚拟地址是以这样一个字来编码的,所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小

对一个字长为w的机器而言,虚拟地址的范围是$0$ ~$2^w-1$,程序最多访问$2^w-1$个字节。

近年,很多机器都从32位字长迁移到了64位字长。大多64位字长机器可以运行32位字长机器编译的程序。32位程序和64位程序的区别在于程序是如何编译成的,而不是运行的机器类型。

寻址和字节顺序

小端法、大端法

对于跨越多个字节的程序对象,我们必须明确:

  1. 这个对象的地址是什么
  2. 如何在内存中排列这些字节

一般来说,多字节对象被存储为连续的字节序列,对象的地址为所使用字节中最小的地址

  • 小端法:将最低有效字节放在最前面(最小地址)存储。(例如一个二进制数最右边的8位是最低有效字节)

  • 大端法:将最高有效字节放在最前面(最小地址)存储。

大多Intel兼容机使用小端模式。

以下代码使用强制类型转换来访问和打印不同程序对象的字节表示。

#include <stdio.h>

typedef unsigned char *byte_pointer;	//将byte_pointer定义为一个指向类型为unsigned char对象的指针
//指针被强制类型转换为unsigned char *, 这告诉编译器程序应该把这个指针看成指向一个字节序列,而不是指向一个原始数据类型的对象。

void show_bytes(byte_pointer start, size_t len)
{//按顺序显示出指针指向对象的每个字节内容,可以判断出系统使用的小端法还是大端法
	size_t i;
	for (i = 0; i < len; i++)
		printf("%.2x", start[i]);
	printf("\n");
}

//使用sizeof确定对象使用的字节数
void show_int(int x)
{//显示int对象的字节内容
	show_bytes((byte_pointer) &x, sizeof(int));
}
void show_float(float x)
{//显示float对象的字节内容
	show_bytes((byte_pointer) &x, sizeof(float));
}
void show_pointer(void *x)
{//显示void *对象的字节内容
	show_bytes((byte_pointer) &x, sizeof(void *));
}

表示字符串

对文本进行编码。

ASCII编码、Unicode编码

之前写过一篇相关博客:字符编码:Unicode, UTF-8

布尔代数

四种布尔运算:

与、或、非、异或

异或:当P或Q为真但不同时为真时,异或成立;即当p=1且q=0或p=1且q=1时,p^q=1

位向量的布尔运算

按位进行布尔运算。

C语言中的位级运算

按照对应位进行布尔运算。

C语言中的逻辑运算

||&&!

逻辑运算和位级运算完全不同,逻辑运算认为所有非零的参数都表示TRUE,参数0表示FALSE。以下是一些表达式求值举例:

表达式 结果
!0x41 0x00
!0x00 0x01
!!0x41 0x01

C语言中的移位运算

左移k位:将操作数向左移动k位,丢弃掉最高的k位并在右端补k个0

逻辑右移:在左端补k个0

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

几乎所有编译器都对有符号数使用算术右移,对无符号数使用逻辑右移。

整数表示

来编码整数的两种不同方式:

  • 一种只能表示非负数
  • 另一种能表示负数、零和正数

整型数据类型

C语言通过关键字来表示多种整型数据类型,这些关键字包括char、short、long,同时还能指示被表示的数字是非负数(声明为unsigned)。

为不同大小分配的字节数根据程序编译为32位还是64位有所不同;根据字节分配,不同大小所能表示的值的范围是不同的。

取值范围是不对称的,负数的范围比正数大1.

无符号数的编码

直接按照二进制进行编码即可。B2U:将二进制编码映射到一个非负整数

无符号数的编码具有唯一性

补码编码

(two’s-complement)。用来表示有符号数,将字的最高有效位解释为负权,用$B2T_w$表示: $$ B2T_w(\vec x)=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2_i $$ 最高有效位$x_{w-1}$称为符号位,它的权重为$-2^{w-1}$,是无符号表示中权重的负数。

从维向量到整数映射的举例: $$ B2T_4([0001])=1 \
B2T_4([0101])=5 \
B2T_4([1011])=5 \
B2T_4([1111])=-1 $$ w位补码所能表示的值的范围是:$[-2^{w-1},2^{w-1}-1]$,例如长度为4的补码可以表示的范围是$[-8,7]$。与无符号数一样,在可表示的取值范围内,每个数字都唯一的w位补码。

用补码来编码负数(有符号数)。几乎所有现代机器目前都采用补码编码。

反码:最高有效位的权是$-(2^{w-1}-1)$,其他和补码一样。

原码:最高有效位是符号位,用来确定剩下的位应该取负权还是正权。

这两种表示方式对于数字0都有两种不同的编码方式。

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

对于多数C语言的实现来说,这个问题都是从位级角度来看的,而不是的角度。

处理同样字长的有符号和无符号数之间相互转换的规则为:数值可能会改变,但位模式不变。

补码转换为无符号数$T2U_w(x)$,当x<0时值改变,计算结果为$x+2^w$,当x>0时值不变。

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

C语言支持所有整型数据类型的有符号和无符号计算,几乎所有机器都采用补码表示有符号数。通常大多数数字都默认是有符号的。

扩展一个数字的位表示

将无符号数扩展为一个更大的数据类型:只需在表示的开头添加0即可。

将一个补码扩展为一个更大的数据类型:执行一个符号扩展,即在开头添加最高有效位数字。

符号扩展不改变补码表示的数字。

截断数字

总结

为了避免出现错误或漏洞,我们绝不使用无符号数

整数运算

无符号加法

两个无符号数相加,如果完整的整数结果不能放到数据类型的字长限制中去,那么就会发生溢出,当无符号数加法发生溢出时,结果为丢弃溢出的最高位后的结果,即减去$2^w$。

补码加法

分为正溢出、正常、负溢出三种情况。

  • 正溢出:和减去$2^w$
  • 负溢出:和加上$2^w$

补码的非

当$x=\text{TMin}_w$时,补码的非的结果为:$\text{TMin}_w$,否则结果为$-x$

无符号乘法

乘积可能需要$2w$位来表示,C语言中无符号被定义为产生w位值,即2w乘积结果的低2w位。将一个无符号数截断为w位等价于计算该值模$2^w$

补码乘法

总结

计算机的整数运算实际上是一种模运算,表示数字时的有限字长限制了可能的值的取值范围,结果运算溢出。

补码提供了一种既能表示整数也能表示负数的灵活方法,同时使用了与执行无符号算术相同的位级实现。

浮点数

二进制小数

IEEE浮点数表示

舍入

浮点运算


最后修改于 2021-07-12