CS:APP(二)信息的表示与处理

30 Dec 2017

这一章开始的内容可就是实打实的计算机底层系统知识了,首先,系统信息的表示

首先约定,从这一章开始,CSAPP每篇博客,是以两部分组成,一部分是知识总结,另一部分是编码相关

语言的描述,仍然以C语言为主,系统基于x86_64的Linux平台

同时对于这一章的学习,是从数学原理入手的,不过不用担心,只要拥有高中代数的知识即可

PS: 美国高中代数的知识, 中国初中数学知识

信息存储

首先介绍了信息存储基于的几种进制方式,(2,8,16)

了解计算机的,基本上都懂,我就不赘述了

下面来看看字数据大小:

字(word):1 word = 2 bytes = 16 bits 1个字 = 2 个字节 = 16位

OK,上面这句话其实是错的,他指的是16位机的情况,字其实就是指计算机一次处理数据的字节数,

视具体的处理器而言,32位机,就是(4字节/字).64位机就是(8字节/字)

字长(word size): 指明指针数据的标称大小,是进行内存地址编码的描述,简单的讲,就是1个字的字节数

举个例子: W位字长的操作系统,即是可以访问的内存范围为 0 ~ $2^w-1$

近年来,32位过渡到64位的趋势越来越明显,内存可访问区域也从4GB扩展到16EB

而进行编译时,我们可以指定类型,程序如何运行,不决定于机器,而决定于它是如何编译的

linux> gcc -m32 prog.c     可以运行于32/64位
linux> gcc -m64 prog.c     运行于64位机

下面来看看C规定的数据类型大小

C声明		字节数
有符号	无符号	32位	64位
[signed] char	char	1	1
short	unsigned short	2	2
int	unsigned	4	4
long	unsigned	4	8
int32_t	uint32_t	4	4
int64_t	uint64_t	8	8
char *	\	4	4
float	\	4	4
double	\	8	8

从上表可以看出,字,是计算机处理数据的单位(基本单位是字节)

字是地址编码的标称值,所以,C指针的数据类型大小与字长保持一致,我们常说指针4字节,实际上是32位

而对于64位 sizeof(pointer) = 8

寻址与字节顺序

寻址

寻址的问题上,我们需要讨论的是,**址,到底指的是什么 ? **

实际上,地址指的是,该变量/数据首字节地址,为什么,多字节存储数据时,不可能表示出所有地址

所以,使用首字节地址进行表示即可.计算机知道每种数据类型的大小,最后进行切割获取即可

所以,就有 char *str = “abcd” 的用法, str指这个字符串的首地址

字节顺序

既然提到字节顺序的问题,那么就有一个不得不讨论的问题了

　在之前，数据较小的时候，需要多个字节进行存储时，　直接存储即可

　但随着时代的进步，对于一个数据需要进行多个字节存储时，如何安排顺序就是一个问题了！

对于字节顺序的问题，有两种解决方法，可以概括为：

１. 大端法

高字节，低地址的存储,与阅读习惯相同

２. 小端法

低字节,低地址的存储,与阅读习惯相反

看下面这个例子:

对于数字0x01234567编码

大端法
	0x100	0x101	0x102	0x103
...	01	23	45	67	...
小端法
	0x100	0x101	0x102	0x103
...	67	45	23	01	...

大端与小端法并没有优劣性得差异,根据情况去使用即可

但是,需要注意的是,只要使用了一种编码方式,就必须保持下来

选择任何字节顺序并没有技术上的差异.只要选择了一种规则,并且始终如一的坚持下去,对于哪种字节排序都是任意的

在以下三种情况下,字节顺序是十分重要的:

进行网络编程时,需要规定好Client/Server的字节顺序,否则,接受方收到的是反序数据
在阅读时,需要指定顺序,最常见的一种情况就是,在阅读反汇编器生成的代码时,若不清楚字节顺序很烦恼
编写规避正常的程序时,举个例子,进行C语言强制类型转换时,

下面是一个,查看当前机器时大端还是小端的程序

#include <stdio.h>
int main(void)
{
	int x = 0x12345678;
	printf("%.2x\n",*(char *)&x);    "78"为小端,"12" 为大端
	return 0;
}

简单解释: 取X地址指向的首地址,并打印其值,至于为什么不用10进制,因为中间的数值转换不够清晰明了

而且从上面可以看出:

所谓强制类型转换,并没有改变位模式中的内容,只是改变了解读的方式

从侧面也验证了:信息 = 位 + 上下文,单纯的位数据是没有意义的

C语言的位运算

首先,需要介绍的是布尔代数.

C中的位运算是基于布尔代数的.

主要介绍,位级运算,移位运算,逻辑运算

位级运算

主要由** & ,

, ^ , ~**等运算符组成

& 与	按位与或已经很常用了

重点介绍一下,^, 异或

异或,相当于位级运算中的逆元,异或一个重要的性质是:

** ( a ^ b ) ^ a = b **

那么,就可以处理一个很实际的问题,对于100w+1个数,其中50w对数是相同的,如何找出唯一不同的数

#include <stdio.h>
int main(int *array, size_t len)
{
	int res;
	for(int i = 0; i < len; i++)
		res ^= array[i];
	printf("%d\n",res);
	
	return 0;
}

就是利用异或的性质来处理这个问题 !

而位运算常用的最重要的性质,就是求掩码

而掩码的求解,其中需要用到 ~ 取反运算符

这个时候,使用~0 要比0xFF的可移植性更高

逻辑运算

C中的逻辑运算,就是 &&,

, ! 与或非,三种

不管是从符号上,还是从使用上,都很容易与位运算混淆

区分位运算与逻辑运算:

1.位运算只有在特殊的情况下,或者被限制在0~1之间,才会与逻辑运算有相同的行为

2,另一个重要的区别就是,逻辑运算的中断/短路原则,p&&*p++ 并不会导致空指针的访问

移位运算

移位运算中,具体概念不再赘述

更重要的是谈一谈两种移位方式以及对编程影响:

左移: 都是逻辑的,补0

右移: 分为算术右移,逻辑右移.unsigned为逻辑右移,补码为算术右移,要保证正负性

然而,问题来了,对于不同的编辑器与机器,右移到底是逻辑的,还是算术的,界定并不是很清楚,是情况而定

一般情况下,假定机器对于有符号数,算术右移.同时,对于无符号数,右移必须是逻辑的

在Java中,对于右移的类型界定十分清楚

”»” 表示逻辑右移

”»>” 表示算术右移

整数编码

*接下来的内容,可谓是本章的精华了,计算机如何存储数制与信息 ? 如何规避错误而写出正确的代码 ? *

一一,都会的到解答

简述本节: 介绍以无符号数(Unsigned)与补码(有符号数)T为主

接下来,会先引入一系列的数学术语

符号	类型	含义
$B2T_w$	函数	二进制转补码
$B2U_w$	函数	二进制转无符号数
$U2B_w$	函数	无符号数转二进制
$U2T_w$	函数	无符号数转补码
$T2B_w$	函数	补码转二进制
$T2U_w$	函数	补码转无符号数
$TMin_w$	常数	最小补码
$TMax_w$	常数	最大补码
$UMax_w$	常数	最大无符号数
$+_w^t$	操作	补码加法
$+_w^u$	操作	无符号数加法
$*_w^t$	操作	补码乘法
$*_w^u$	操作	无符号数乘法
$-_w^t$	操作	补码减法
$-_w^u$	操作	无符号数减法

32位机器与64位机器夹杂,是目前的趋势,下面看一看C语言要求的数据类型最低标准

C数据类型	最小值	最大值
[signed] char	-127	127
unsigned char	0	255
short	-32767	32767
unsigned short	0	65535
int	-32767	32767
unsigned	0	6555
long	-2147483647	2147483647
unsigned long	0	4294967295
int32_t	-2147483647	2147483647
uint32_t	0	4294967295
int64_t	-9223372036854775808	9223372036854775807
uint64_t	0	18446744073709551615

C/C++支持有/无符号数,Java只支持无符号数(更想学Java了,滑稽)

无符号数(U)与补码(T)的编码

先来上数学原理:

$B2U\_w(\vec x) \dot = \sum\_{i=0}^{w-1}x\_i2^i$ $B2T\_w(\vec x) \dot = -x\_{w-1}2^{w-1} + \sum\_{i=0}^{w-2}x\_i2^i$

由上面两式可以看出,不管是二进制位向量转无符号数还是补码,都是权值码

进行指定位权的赋值即可

补码的编码规则则是:

最高位位权为负权重,其余位权为正值,进行位权累加即可,

PS:这里想起了,~~刘建元~~发哥,大一讲计导的时候,补码的概念其实解释的不是很清晰,讲的是补码的求法

那么,为什么重点讲补码呢 ? ,这是因为现今的计算机基本上都是采用补码的,原因在下面:

数	字长w
数	8	16	32	64
$UMax_w$	0xFF	0xFFFF	0xFFFFFFFF	0xFFFFFFFFFFFFFFFF
$UMax_w$	255	65535	4294967295	18446744073709551615
$TMin_w$	0x80	0x8000	0x80000000	0x8000000000000000
$TMin_w$	-128	-32768	-2147483648	-9223372036854775808
$TMax_w$	0x7F	0x7FFF	0x7FFFFFFF	0x7FFFFFFFFFFFFFFF
$TMax_w$	127	32767	2147483647	9223372036854775807
-1	0xFF	0xFFFF	0xFFFFFFFF	0xFFFFFFFFFFFFFFFF
0	0x00	0x0000	0x00000000	0x000000000000000

从上面可以看出 $

TMin_w

= TMax_w + 1$

显而易见,稍不注意,便会产生因此而生的Bug,那么,为什么会有这样的情况出现

因为,补码表示的一半是负数,另一部分是非负数,占用了一个正数的位置,所以可表示的正数少1

那么,这与为什么采取补码有关系吗 ? 有 ! ,正因此,数字编码没有浪费,同时规避了一些问题

所以才采用了补码,而原码,反码的编码方式,存在+/-0,浪费了数字编码

PS:在java中,标准十分明确,而且只允许存在有符号数(Java越来越吸引我了,滑稽)

无符号数与补码转换

既然存在有两种编码方式,那么这两种方式,总归有需要进行相互转换的时候

补码转无符号数由下面的两个函数来实现:

$T2U\_w(x) = x + 2^w ,(x < 0)$ $T2U\_w(x) = x ,(x \ge 0)$

结合可得:

$T2U\_w(x) = x + x\_{w-1}2^w$

当x为负数时,则最高为定为负权值,$-x_{w-1}2^{w-1}$

而在无符号数中,对于此得解释是正权值,从负到正加上$2^w$,而$x\ge0$,相同

同上理,无符号数转补码就有下面两个函数实现:

$U2T\_w(x) = x - 2^w (x \ge TMax_w)$ $U2T\_w(x) = x (x < 0)$

结合,可得:

$U2T\_w(x) = -x\_{w-1}2^w + x$

同上理,不再赘述.

那么,无符号数与补码的转换,语言是如何实现的?

不清楚Java的实现机理.但是,在C/C++中,依靠的是强制类型转换

使用强制类型转换,可以进行不同类型间的转换

实质:对位的解释改变,不改变位中的值.解释后,位不变,表示的值可能会改变.具体实现,就是上面的函数

(注:目前讨论的还仅是相同位数的情况)

数位扩展与截断

数位扩展/截断有什么用呢?

这样和你讲吧,作用还是很大的!

在不同数位间,进行数的转换时,用到的就是数位的扩展(低位到高位)

那么,同理,(高位到低位)就是数位得截断了

先来说无符号的扩展

很简单,给左边加上要求数位的0即可,称为0扩展

那么,补码的扩展呢?

来看个公式:

$B2T\_{w+1}([x\_{w-1},x\_{w-1},\dots,x\_{w-2},\dots,x_0]) = B2T\_w([x_{w-1},\dots,x\_0])$

这种扩展称为,符号扩展

符号扩展的原理是,应用 : $2^w - 2^{w-1} = 2^{w-1}$这个属性的,推理略

上面这两种扩展,都会保证原数值不改变

下面来看看,数字的截断.

数字的截断遵循: 由低位开始截断,对于无符号数这这样

对于补码,先将补码视为无符号数,之后进行截断,最后转回补码

$x' = x \ mod \ 2^w$

原理是$2^{w+t} \ mod \ 2^w = 0 \ (t \ge 1)$

有符号数与无符号数的建议

因为程序中经常会使用显式的强制类型转换,或者隐式的自动类型转换,导致了某些非直观的错误

而这些非直观的细微错误,经常会导致程序的崩溃

看下面的例子:

#include <stdio.h>
float sum_length(float a[ ], unsigned length)
{
	for(int i = 0; i <= length-1; i++) {
		operation(...);
	}
	
	return float type
}

for循环中,如果有不怀好意的人,传入TMax,之类的数,便使程序进入死循环

实例:

在FreeBSD开源项目的getpeername()函数的实现上,出现了重大错误

实际问题出现在传递参数位负值,而memcpy()函数中,len为size_t无符号类型,会导致内存月越界

数位运算

前面讨论完了数字的表示,那么后面自然要谈谈数字的运算了

无符号加法

首先,根据数学知识,易得,两个w位的无符号数相加,可能会溢出为(w+1)位,

但是,只有w位来表示,所以就要进行数字的截断了

当未溢出时,即为原结果.溢出时,丢弃最高位,即求mod运算即可

整理后的公式为:

$x +_w^u y = (x+y) \ mod \ 2^w$

那么,我们很容易知道无符号加法溢出的条件:**当x + y = s, 且 x > s **时,则发生了溢出

同时,既然知道了加法,那么就可以用此加法来求反

$-x_w^u = 2^w -x (x > 0)$ $-x_w^u = x (x = 0)$

推理:即为加法求逆,即可

补码加法

补码加法,是一项很重要的内容.

常见的溢出问题,都是由此而生的

同理,有数学知识,易得,:补码加法,会发生上下溢出,

同理,还是进行数位的截断

正数,少1,表示少了$2^w$

负数,少1,表示多了$2^w$

中间值,并不会溢出

可以通过下面的公式表示:

$x +_w^t y = x + y -2^w (x+y\ge TMax_w)$ $x +_w^t y = x+y \ (TMin_w < x+y \leq TMax_w)$ $x +_w^t y = x+y+2^w (x+y < TMin_w)$

但是,实际上机器加法的实现,是这样:先进行补码转无符号数,之后进行加法运算,最后又转回无符号数

$x+_w^ty = U2T_w[(x+y)\ mod\ 2^w]$

实际实现方式如上

同理,我们可获取到,检查补码加法溢出的方法:

x > 0,y > 0, s <= 0 ,发生了正溢出

x < 0, y < 0, s > 0, 发生了负溢出

还可以得到补码的非:

$-x_w^t = TMin_w (x = TMin_w)$ $-x_w^t = -x (x > TMin_w)$

需要十分注意的是,TMin非是自身

推理:补码加法的逆

数字乘法

对于,乘法的内容,没有什么要谈得

对于无符号数:

乘法,便是对乘积取模即可

对于补码而言:

虽然乘积与无符号数是不同的,但是可以保证其低位等价性

所以,同加法实现,借助于无符号数的加法实现

公式如下:

$x*_w^u = (x\cdot y)\ mod \ 2^w$ $x*_w^ty = U2T_w[(x\cdot y)\ mod \ 2^w]$

乘以常数

下面要谈得是很好玩的东西了,乘法.

在计算机中,乘法不同与加减法和移位运算.

乘法的开销十分大,达到10个左右的时钟周期,加减法为1个.即使是Intel Core i7乘法也得3个周期

所以,计算机,一般情况下是不想做乘法的,更倾向于做加减法和移位

那么,用加减法和移位运算来优化乘法,不就好了么

先来看看,移位运算的实质

$x << k = x \cdot 2^k$

推导:

$B2U\_{w+k}[x\_{w-1+k},x\_{x-2+k},\cdots,x\_{0+k}]$ $= \sum_{i=0}^{w}x_i2^{i+k}$ $= 2^k\sum x_i2^i$ $=2^k\cdot x$

有上述推理,可得,移位运算的实质

那么,我们就可以如此优化乘法:

将乘数,拆开称为2的幂之和,在分开进行加法运算即可

举个例子:

$x \cdot 13 = x \cdot (2^2+2^3+2^0) = (x<<2)+(x<<3)+x$

如此,在一定情况下,可以加速乘法运算.至于实际,取决于机器的指令,与其高度相关

乘法如此优化,那么除法呢?

除法相对于乘法更慢,需要30个左右的周期

举一反三,我们此时应该使用的是右移,逻辑/算术右移具体视情况而定

而且,除法不能像乘法一样进行累加,只能除以2的幂(移位加速时)

在无符号数优化除法时,会得到向0舍入的值,而补码除法会视情况而定,正数向下舍入,负数向上舍入

这便不能保证统一,所以,需要设置”偏置’量,来进行优化调整

即对于,负值,进行偏置,然后进行移位运算

偏置值为x/y,则为 (y-1),推理见CS:APP(P73)

C语言表达式:

(x < 0 ? x+(1<<k)-1 : x) >> k

最后,总结一下,对于正数的运算,都是基于”模运算”的

浮点数

相对于,整数.对于浮点数的介绍,就不是那么多了.

计算机对于浮点数计算速度的需求 > 准确程度

首先,需要了解,负数的二进制表示–使用负幂,与十进制也是类似的

IEEE浮点表示

IEEE浮点表示,是这里的重点

IEEE浮点表示,基于这样的形式:

$V = (-1)^s \cdot M \cdot 2^E$

介绍一下各个符号的含义:

V: 表示浮点值

s: 表示符号位

M: 表示尾数,默认个位是1的

E: 阶码,即为2的幂

其中需要注意的是不同位数,M,E的数目不同

32位: s = 1 , k = 8 , n = 23

64位: s = 1 , k = 11 , n = 52

偏置量: $2^{w-1}-1$, 这里的偏置量是为阶码设置的,为了将阶码映射到正数范围

全部是使用无符号数表示,使用时,减去偏置值,即可获得真正的阶码值

非规格化值偏置为$\ 1-Bias$,规格化偏置值为$\ e-Bias$

舍入

表示的方法限制了浮点数的范围和精度,浮点数只能近似的进行计算,于是如何找到最近的匹配值成为问题

这就是舍入存在的意义了

一般情况下,舍入:有四种

向偶数舍入, 向0舍入, 向下舍入, 向上舍入

默认一般是先偶数舍入

因为目前对舍入要求不多,暂时掠过

编码相关

合适的数据类型

从数据类型上可以看出,在不同位数处理器上,对于数据类型的大小界定是不同的

为此,在ISO99的C标准,即C99中提供了两个新的类型

int32_t
int64_t

指定了处理器类型的int数据类型

显式的使用对应机器上的数据类型,可以避免一些意想不到的错误

同时,兼容性/可移植性与准确性,向来是相悖的,在某些情况下,准确的代码比可移植性更为重要

提高程序的可移植性

上面提到了使用准确的,对应于机器的数据类型,但同时,随着计算机的发展

编写可移植性高的代码,也是众望所归

那么,提高可移植性有哪些办法呢?

1.使用运行时确定数据类型的方法

比如,sizeof(elemtype)

typedef char * byte_pointer
void show_bytes((byte_pointer)start, size_t len)
{
	size_t i;
	for(i = 0; i < len; i++) {
		printf("%.2x",start[i]);
	}
	printf("\n");
}

void show_int(int x)
{
	show_bytes(byte_pointer(&x),sizefo(int));
}

其中便使用sizeof(int)提高程序可移植性

进行标准的编码

C/C++优化能多的内容是未定义的,需要根据实际情况去界定

而对于Java,反而是十分稳定的,对于任何的标准,都是一板一眼,(PS:搞的我都想学Java了)

进行标准规范的编码时,很有用的一个办法是,使用括号,尤其是在你对优先级不是很清楚时,

不要为了自己的代码优雅,而写出Bug代码

举个例子: *process_list->data ,就是错误的用法

而(*process_list)->data才是正确的用法,优先级的问题,需要十分注意

从数字编码中学习

上面提到了,U,T两类数字编码,那么,就有一个常见的问题了

当算式中使用的是不同的数字编码时,那么就需要进行强制类型转换,

在程序员不手动处理的时候,会自动类型转换

看下面的代码:

#include <stdio.h>
int main(void)
{
	unsigned a = 2;
	int i = -3;
	if (i > a)
		printf("Haha!\n);
	else
		printf("OK!"\n);
	return 0;

}

你认为结果会是什么?

实际上结果是,Haha,给个提示,类型转换的优先级,unsigned > int

从上面的例子,可以得出,我们要进行正确类型的编码(系统编程的特殊情形除外)

对于这一处,规定统一的数据类型即可规避这项错误

准确的了解不同数制的转换,十分重要

可以参考 CS:APP(P53) 图2-19的进制升级表来理解

数位的扩展与截断

short sx = -12345;
unsigned uy = sx;

此处发生的是:(unsigned int)(int)sx而不是(unsigned int)(unsigned short)sx

所以,对于强制类型转换时,需要十分注意运算符的顺序

浮点运算

这是这部分第二个重点的内容,

首先,强调,浮点运算不具有结合性,满足单调性

举个例子:

$(3.14 + \ln10)-\ln10 = 0$ $3.14 + (\ln 10 - \ln10) \neq 0$

这便是浮点加法的不可结合性,其他同理

也告诫我们,进行浮点运算时,需要十分小心

C语言中的浮点数

既然谈到了,浮点数,那么正数与浮点数之间的强制类型转换,就不得不提了

int –> float ,不会溢出,可能被舍入

int/float –> double , 能够保证准确的精度

double –> float , 因为表示范围,精度的减小,可能能够溢出或舍入,丢失精度

float/double –> int , 值会向0舍入,而且C标准对于这种情况是未定义的.

上面这些内容,是作为一个合格程序员,所必须要掌握的,不然是没办法处理好各种各样情况的

虽然,从理论上讲,应该使用相同的数据类型,但是,那毕竟是痴心妄想,除了某些奇葩语言 (Lisp)滑稽

总结

CSAPP–信息的表示和处理,是内容十分丰富的一章,也是看的我想shi的一章

因为,浮点数的内容并不是重点,所以并不是很详细,抱歉

另外,课后习题有时间也可做做,十分有用.

下一章可就是程序机器级表示了,也不是什么好啃的内容, . . .

December, 2017 5:17 AM

CSAPP