六星经典CSAPP笔记(2)信息的操作和表示

浏览数：108 / 时间：2015年06月11日

2.Representing and Manipulating Information

本章从二进制、字长、字节序，一直讲到布尔代数、位运算，最后无符号、有符号整数、浮点数的表示和运算。诚然有些地方的数学证明有些枯燥，但总体上看，本章还是干货十足的！

2.1 Decimal vs. Binary Notation

我们习惯十进制只是因为我们有十根手指头(？)，所以会对二进制感到不习惯。但是二值信号(two-value signal)在表示、存储、传输方面有巨大优势，从打孔带上的有没有孔洞(代码的表示)，到电线上的高低电压(数据的传输)，到磁畴(magnetic domain)的顺时针、逆时针旋转(磁盘上存储)。

2.2 Words

字长是CPU一次能够处理的数据长度，一般代表着能处理的数字长度，也代表了CPU数据通路的宽度(地址总线、数据总线)。

2.3 Addressing & Byte Ordering

字节序，大尾端小尾端，这些耳熟能详的词汇，仿佛已经翻来覆去学了好多回都要烂熟如心了。可这东西到底有什么用啊？答案是用处大着呢：

不同机器间的二进制数据传输：不知道是大尾端还是小尾端的话，解析时肯定是错啊！
反编译程序中的整数数据：指令倒无所谓什么顺序，但指令后面跟着的操作数要是不知道顺序那可就乱套了！例如反编译出程序中的一句：01 05 64 94 04 08。其中01 05表示add %eax寄存器，那么后面操作数64 94 04 08的字节序就至关重要了。小尾端的话，它就表示0x8049464，大尾端则完全相反。
避开类型系统直接访问底层字节：例如C语言中用cast将对象转换成与其创建时完全不同的类型。应用编程当然不推荐这样写，但是在系统编程中这却非常有用！

下面就再再温习一下字节序吧。假设地址0x100处存放了一个4字节的整数0x01234567，即从地址0x100到0x103。那么大小尾端的存放方式如下图所示。一定要注意的是：所谓大小都是相对内存地址来说的。大尾端就是从低地址到高地址，低地址存高位，高地址存低位，所以叫大尾端。如果地址是从左向右增长的话，那么大尾端就与我们习惯的书写方式的顺序相同。

但是，对于字符串来说则不存在这种区分。例如字符串"12345"的字节为：31 32 33 34 35 00(终止符)。在任何使用ASCII作为字符编码的机器上，不论字节序、字长等环境如何，结果都是这样。因为字符串都是由一个个字符组成的，对于单个字符来说是不存在顺序的。所以说，字符数据比二进制数据具有更好的平台独立性。

扩展一下：那用多字节表示字符的Unicode编码有没有这种问题呢？

“UTF-8以单字节为编码单元，没有字节序的问题。UTF-16以两个字节为编码单元，在解释一个UTF-16文本前，首先要弄清楚每个编码单元的字节序。例如收到一个“奎”的Unicode编码是594E，“乙”的Unicode编码是4E59。如果我们收到UTF-16字节流“594E”，那么这是“奎”还是“乙”？Unicode规范中推荐的标记字节顺序的方法是BOM，Byte Order Mark。BOM是一个有点小聪明的想法：在UCS编码中有一个叫做”ZERO WIDTH NO-BREAK SPACE”的字符，它的编码是FEFF。而FFFE在UCS中是不存在的字符，所以不应该出现在实际传输中。UCS规范建议我们在传输字节流前，先传输字符”ZERO WIDTH NO-BREAK SPACE”。这样如果接收者收到FEFF，就表明这个字节流是Big-Endian的；如果收到FFFE，就表明这个字节流是Little-Endian的。因此字符”ZERO WIDTH NO-BREAK SPACE”又被称作BOM。

关于尾端的典故也很有意思，摘抄一段放松一下：

“Lilliput和Blefuscu这两大强国在过去的三十六个月里一直在苦战。战争开始时由于一下原因：我们大家都认为，吃鸡蛋前，原始的方法是打破鸡蛋较大的一端，可是当今皇帝的祖父小时候吃鸡蛋，一次按古法打鸡蛋时碰巧将一个手指弄破了，因此他的父亲，当时的皇帝，就下了一道赦令，命令全体臣民吃鸡蛋是打破鸡蛋较小的一端，违令者重罚。老百姓们对这项命令极为反感。历史告诉我们，由此曾发生过六次叛乱，其中一个皇帝送了命，另一个丢了王位。这些判断大多都是由Blefuscu的王国大臣们煽动起来的。叛乱平息后，流亡的人总是逃到那个帝国区寻求避难。据统计，先后几次有一万一千人情愿受死也不肯去打破鸡蛋较小的一端。关于这一争端，曾出版过几百本大部著作，不过大端派的书一直是受禁的，法律也规定该派的任何人不得做官。"(摘自蒋剑锋译的《格利佛游记》第一卷第4章）Swift是在讽刺英国（Lilliput）和法国（Blefuscu）之间的持续的冲突。Danny Cohen，一位网络协议的早期开创者，第一次使用这两个术语来指代字节顺序。

2.4 Bit-level Operation & Logical Operation

香农创建了信息论，第一次在布尔代数和数字逻辑之间建立起了联系。

我们可以将布尔运算扩展到位向量上，那么位向量就有两个很有用的方式：

1）表示有限集合从而达到压缩的目的。我可以这样来编码集合A {0, 1, ... w-1}的任意子集，用位向量[aw-1, ..., a1, a0]。当i属于A时，将ai设为1。例如，我们用[01101001]表示[0, 3, 5, 6]，用[01010101]表示[0, 2, 4, 6]。也就是说位向量是“倒着”保存的！(待深入研究)

2）信号掩码。不同信号能中断程序的执行，所以我们可以用特定的位向量来启用或禁用不同的信号。

经典的位运算：

1）清除值：x & 0xFF（只保留最低的一字节）

2）设置值：x | 0x3

3）可移植的“1”：~0

4）反转值：x ^ 0xF（异或的特性1：101 ^ 111 = 010，而特性2：101 ^ 000 = 101）

5）清零：XOR %edx, %edx （异或的特性3。为什么不直接设值，因为这种方式生成的机器码只有两字节，而设值有五字节）

逻辑运算与上面讲过的位运算经常是搞混。二者还是有很大的不同的：

1）逻辑运算将任何非0参数看做TRUE，并且只返回1或者0。因此只有当参数是0和1时，逻辑运算才和位运算有着相同行为。

2）逻辑运算具有短路的效果。当某一部分逻辑运算后已经能确定整个表达式的真假时，后面部分的逻辑运算就不会执行了。这种行为也是位运算所不具有的。

2.5 Integer Representation

对于无符号整数就非常简单了，每一位都表示2的i次方就可以了。技术分享

对于有符号整数呢，先说一种我们直接能想到的，用二进制表示整数的方式：用最高位当符号位，0表示整数，1表示负数。但这种方式有个重要的缺陷：整数0有正负两种表示方式。现代计算机使用的都是另一种我们耳熟能详的二进制表示方式：补码(two‘s complement)！最高位是1时则最高位的值是其权值取负。所以我们看汇编或机器码时经常能看到0xFFFF...xx，就是因为最高位是权值的负数，所以要置很多个次高位为1来表示一个“小”负数。例如0xFFFFFEC8=-312。小尾端机器上也就是C8 FE FF FF。