CSAPP 第二章学习

学习 CSAPP 的主要原因是在学完基础汇编之后，发现自己对于一些 C 上基础的各种东西，还是非常不熟练的，所以需要再学习一遍 CSAPP

里面有一些内容和汇编入门学习，确实也是相近的，但是我也会不厌其烦地再 review 一遍。

信息存储

数字表示

二进制：区别于我们平时计数使用的十进制，二进制使用的是逢二进一原则，而我们的十进制则是逢十进一，比如我们十进制的 9+1 中的 9，答案应该是十，但是十应该进一，因此得出了我们常规的答案 10。在二进制里面，每一位只要大于等于 2 则都要向高位进一。为了方便表示，还衍生出了二进制的子类，比如八进制，十六进制等，主要是二进制向这些进制转换较为容易，而计算机平时又都处理二进制数据，因此就出现了这些常见的进制计数。

信息存储

大多数计算机使用的都是8位（在计算机中，除特殊说明外，一位均指的是二进制的位）的块，或者叫字节，字节是作为计算机可寻址的最小单位。一般来说我们并不习惯于将一个字节写成八位二进制的数，而是会写成两位十六进制的数。十六进制与二进制之间的转换也会十分容易，举个例子：

0x99->0b10011001  
0x88->0b10001000

我们可以发现我们并不用像十进制那样权值相加或者是除二取余那么麻烦，我们把一位十六进制视为四位二进制即可，这样我们在转换的时候就是直接每一位分别转了，可以看出十分的方便。

字数据大小

每台计算机都有一个字长，字长为计算机 CPU 一次能处理的最大数据，也有一种说法是能表示的最大内存。其实意思是差不多的，比如我们都知道 32 位的计算机最多能装 4GB 的内存，再多它也是只能使用这么多的内存，那是因为 CPU 要访问内存的时候，也只能使用一个 32 位的数据来表示地址，32 位的数能表示的数的个数也就是 2^32 这么多，而地址指示的单位是字节，所以最多就是 2^32 字节，那就是熟知的 4GB 了。

C 语言中 sizeof() 会返回一个对象所占的字节数，我们对比输出下 32 位机子和 64 位机子的各个基本数据类型所占的字节数。我们不必找两个机子，只需要在 64 位的机子上分别编译 32 位和 64 位的程序即可。

#include<stdio.h>  
  
int main(){  
    printf("char:%d\n",sizeof(char));  
    printf("short:%d\n",sizeof(short));  
    printf("int:%d\n",sizeof(int));  
    printf("long:%d\n",sizeof(long));  
    printf("char *:%d\n",sizeof(char *));  
    printf("float:%d\n",sizeof(float));  
    printf("double:%d\n",sizeof(double));  
}

32 位的结果：

64 位的结果

我们总结出如下表格

C声明	32位字节数	64位字节数
char	1	1
short	2	2
int	4	4
long	4	4
char *	4	8
float	4	4
double	8	8

其实有些时候， long 的字节数也会随机器字长有所变化的，只是好像某个版本区分了 64 位整数就叫 long long 而 long 地位与 int 一致了。但是除了这个问题，可以发现只有指针类型的数据会随着机器字长发生变化，这也如我们所说，机器字长决定了指针就多少位，决定了有多少个地址，能用多少内存，多出的内存机器就无法做区分了。

寻址和字节顺序

对于多字节的数据类型我们必须确定两点：

1. 这个对象地址在哪里
2. 这个对象中的字节按什么顺序排列

比如一个 int 它有四个字节，那么我定义 int a=0x12345678。首先它一定是连续排列的，因此我们确定一个 int 的地址只需要确定它的最高字节的位置即可确定整个 int 的位置。假如 int 的地址是在 0x100 的，那么它应该怎么排列这些字节呢？

我们最初可能按照惯性，认为它是按照如下方式存储的：

字节：12  34  56  78  
地址：100 101 102 103

这个也很符合我们的书写规则，但是实时却恰恰相反，在现在大部分的机器中，它是反着存储的。也就是

字节：78  56  34  12  
地址：100 101 102 103

这两种存储方式我们分别叫大端序和小端序。

• 大端序：最高有效字节在低地址
• 小端序：最高有效字节在高地址

由上图来看，大端序更符合人类平时的阅读习惯，但需要注意的是，大多数的 Intel 兼容机器使用的都是小端模式。我们在编写汇编语言时，也需要按照小端序的方式书写。

比如我给 eax 寄存器加上 0x12345678 你会发现它的字节码是：

mov    $0x12345678,%eax   
b8 78 56 34 12

我们通过定义以下的函数以十六进制来逐个显示内存中的字节。

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

其中 start 参数为该对象的起始地址，len 参数为显示的字节数，可以任意定义变量调用这个函数来查看这个对象在内存中的排布，理解浮点数的时候这个函数非常有用。

来查看下面的一个例子：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* $begin show-bytes */

typedef unsigned 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]);    //line:data:show_bytes_printf
    printf("\n");
}
int main() {
    int x = 0x3039;
    show_bytes(&x, sizeof(x));
    float y = x;
    show_bytes(&y, sizeof(y));
}

输出结果如下

可以看到虽然两种类型的数据都是对 12345 编码，但他们有不同的字节模式。浮点数的输出在整数形态下为 0x4640E400，与整数的存储有着截然不同的结果。

但是我们对这个结果的二进制适当移位就会发现它们有13个相匹配的位。

0 0 0 0 3 0 3 9  
000000000 0000000001000000111001  
4 6 4 0 E 4 0 0  
0100011001000000111001 0000000000

我们换其他的数据再次尝试就可以发现，匹配的总是 int 型的低位，但匹配位数不固定，float型的匹配部分也不是总是从最高位开始。

原因是浮点数的尾数基本是和原二进制的值一致的，接下来浮点数部分会有相关原理解释

表示字符串

字符串的定义就是一个以 null 字符结尾的字符数组，如果将字符串看成一个数据类型的话，那么它是以大端形式存储的，但是其实实际上应该说是数组是大端存储的。我们在书写的时候，一般下标 0 是最小的，但是我们习惯把它称为高位，高位在低地址便是大端序。比如 char s[]="1234"; 那么 s[0]='1',s[1]='2',s[2]='3',s[3]=4,s[4]=NULL。请注意末尾的空字节也会包括在字符串里面，但是我们算长度不会算上这个字节。在 gcc 编译器中，我们编译如下的程序：

#include<stdio.h>  
char s[]="0123456789ABCDEF";  
int main(){  
    char buf[16];  
    strcpy(buf,s);  
    printf("%s",s);  
}

编译器会发出可能存在溢出的警告，因为在拷贝的时候会多携带一个 0 字节过来，这在后面堆利用中也是很常见的 off by null 的手段。

再比如我们用这样的方式：

#include<stdio.h>  
char s[]="0123456789ABCDEF";  
int main(){  
    printf("%d",sizeof(s));  
}

运行我们也可以发现这个 char 数组占用了 17 个字节的空间。

布尔代数简介

布尔代数是一个建立在二元集合集合 G={0,1} 上的定义。

非

非0即为1，非非0即为0。

与

全1为1，不全1为0

或

全0为0，不全0为1

异或

相同为0，不同为1

---

结论

1. 非0为1，非1为0
2. 1与1为1，1与0为0，0与1为0，0与0为0
3. 1或1为1，1或0为1，0或1为1，0或0为0
4. 1异或1为0，1异或0为1，0异或1为1，0异或0为0

在C语言中也有一个类型是 bool，它们有特殊的运算符：

• 与：&&
• 或：||
• 非：!

不一样的是，在进行这些运算的时候，统统会把参与运算的值转为 bool 类型，0 就是 0，不是 0 一律都是 1

C 语言中的位级运算

位逻辑运算

我们平时C语言的位运算会扩展到每一位，位之间独立地运算，我们可以把一个整数(int)视为32维的向量，每个维度为0或者1，对整数进行位逻辑运算相当于每一位分别做逻辑运算，每一位结果为新向量对应位的结果。在 C 语言中，以上逻辑运算对应的符号分别为：

• 非：~
• 与：&
• 或：|
• 异或：^

我们可以在只拥有非和其它任意一个双目运算来实现所有的位逻辑运算。

比如我不用异或实现异或的功能，那么就是：

一个为 1，一个为 0 那么为或者一个为 0，一个为 1 的情况都是 1，其余都是 0。我们知道与的特性就是只有全 1 的时候为 0，那么如果我其中一个取非了，再与还是1的话就说明一个为 1 一个为 0 了，两边都非一下，最后把符合条件的位或一下就能得到异或的结果了。

int or(int x,int y){  
    return ~(~x&~y);  
}

那与和或，把非运用到位了它们两个也能运用自如自由转换。

比如我用与和非实现或，首先我对两个元素都非一下然后与起来，是不是就变成了：

全 0 为 1，其余为 0 了，这和或的全 0 为 0，其余为 1 差了什么？很显然结果反了，那么我就对结果再非一下，最后就变成了：

int or(int x,int y){  
    return ~(~x&~y);  
}

或和非实现与运算同理。

移位运算

这里分逻辑移位和算数移位，其实差不多，只不过逻辑移位适用无符号整数，算数移位适用有符号整数。

分左移和右移，分别用符号 << 和 >> 来表示，假设整数一共 w 位，右移 n 位表示丢弃低 n 位，原来的高w-n 位变为低 w-n 位，高 n 位变为0。左移 n 位表示丢弃高 n 位，原来的低 w-n 位变为高 w-n 位，低 n 位变为0。

逻辑位移

左移右移就是字面意思

算数移位

正数与逻辑移位一样，负数则会在右移的时候高位添1.

左移x相当于对该数乘 2 的 x 次方，右移相当于对该数除 2 的 x 次方取整。当移位的位数大于等于该整数的最大位数，则会取模再移位。

整数表示

整数我们之前讲过了它的字节排布规律，但是对于负数计算机又将如何处理呢？

整数数据类型

我们先来看一张表格

C定义	最小值	最大值
char	-128	127
unsigned char	0	255
short	-32768	32767
unsigned short	0	65535
int	-2147483648	2147483647
unsigned int	0	4294967295
long	-9223372036854775808	9223372036854775807
unsigned long	0	18446744037709551615

我们可以很清楚地看到，有符号数在正数和负数的范围并不严格对称，这是为什么我们接下来再看。

无符号数的编码

无符号数的编码就是用一个固定长度的向量来表示，每个维度上的值取 0 或者 1，那么有

这个是我们最容易理解的。

补码编码

有符号数因为需要表示负数，因此它规定：最高位的权值为负。

也就是说若最高位为1，而我们知道，在等比数列 ai=2^i 中，数列的前n项和永远比第 n+1 项小 1，根据等比数列前 n 项和的公式。因此若最高位为1，那么其它位不管是是怎样都不会使这个数变为一个正数。而前 n-1 项可以表示 0~2^n-1 的范围，所以负数的范围就是-2^n+0~-2^n+2^n-1 也就是我们熟知的 -2^n~-1 再加上正数表示的 0~2^n-1 连起来的范围就是 -2^n~2^n-1 。

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

隐式转换按顺序遵从以下原则：

1. 浮点数参与运算就是浮点数，出现过double则结果一定为double
2. 若都是整数参与运算则结果也是整数
3. 整数运算的结果为出现过的位数最大的整数，若最大的整数中有无符号类型的则结果无符号。

因此，如果

• 运算中有 unsigned short 和 int 则结果为 int。
• 运算中有 unsigned int 和 int 则结果为 int。
• 运算中有 unsigned int 和 float 则结果为 float。

也就不一一列举了。

有符号与无符号的位于区别就是最高位的权值正负问题，比较的时候任意一方出现无符号则另一方也会变成无符号比较，所以如果我们做以下运算：

-1<(unsigned)1

会发现它结果为0.

因为 -1 的补码全为 0，转为无符号之后会变成无符号整数的最大值。

扩展一个数字的表示

将一个位数较小的整数扩展为位数较大的整数非常简单，我们只需要在开头添加 0 即可，但是如果是负数，则需要开头添 1，我们运行以下代码试试看：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* $begin show-bytes */

typedef unsigned 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]);    //line:data:show_bytes_printf
    printf("\n");
}
int main() {
    short x = 0x1234;
    short y = -0x1234;
    show_bytes(&x, sizeof(x));
    show_bytes(&y, sizeof(y));
    int x1 = x;
    int y1 = y;
    show_bytes(&x1, sizeof(x1));
    show_bytes(&y1, sizeof(y1));
}

运行可以看到结果如我们所说。

截断数字

我们需要减少一个数字的位数时就需要截断数字，当我们将 w 位的数字截断为 k 位数字时，我们就会丢弃有效位的高 w-k 位，补码数字的符号位是始终不变的。

需要注意有符号数的阶段可能会发生溢出现象。例如，一个8位带符号整数，其范围是从 -128 到 127。如果原始带符号整数为 -150，将其截断为 8 位带符号整数会导致溢出，因为 -150 不在 -128 到 127 的范围内。截断后的结果可能是正数 106，这是 -150 的溢出结果，这不是原始值的正确表示。

整数运算

加法

无符号加法遵循二进制的加法规则，从最低位（最右边的位）开始逐位相加，进位会传递到高位。

补码加法仍然遵循标准的二进制加法规则，但符号位也会参与计算。当执行补码加法时，符号位与其他位一起相加，如果有溢出，则溢出会影响符号位。

乘法

无符号乘法遵循标准的乘法规则，乘法有 x*y=(x*y) mod 2^w 其中 w 为 x 和 y 的位数。需要注意，因为 x 和 y 相乘可能得到最大 2w 位的整数，因此可能会发生截断。

补码乘法同样遵循标准的乘法规则，但符号位也会参与计算。可以理解为先像无符号乘法，乘出来截断之后再转为补码就是结果。

除以 2 的幂

除以 2 的幂通过右移运算来实现，无符号和补码数分别使用逻辑移位和算术移位来实现。

浮点数

二进制小数

二进制小数的表示方法和十进制原理相同，只不过十进制的底数为 10，二进制的权值底数变成了 2。

IEEE 浮点数表示

IEEE浮点标准用如下的公式来表示一个数：

• 符号(s)：1 表示负数，0 表示正数
• 尾数(M)：是一个二进制的小数，取值范围为 [1,2)
• 阶码(E)：为浮点数加权。

这个方法就相当于是二进制的科学计数法。

浮点数可以分为三个字段：符号位，阶码字段和小数字段。

我们知道实际上我们经常用的浮点数有两类，一类是 float 一类是 double，float 为 32 位，double 为 64 位。

• 对于 float，最高位表示符号位，第 2 到第 9 位表示阶码，第 10 位到第 32 位均为尾数
• 对于 double，最高位表示符号位，第 2 到第 12 位表示阶码，第 13 位到第 64 位均为尾数

我们具体以 float 来分析：

第一位是符号位没啥大问题。后面的八位是指数，这个指数需要能表示无穷大，也要能表示无穷小，因此指数必须有正有负。我们定义一个数 Bias=2^(k-1)-1 其中 k 为阶码的位数，在 float 中，这个值为 127，在 double 中，这个值为 1023。阶码实际值 E=e-Bias，其中 e 表示阶码本身的无符号二进制的数值。然后就是这个尾数了，因为我们的范围是 [1,2)，在这个范围内的小鼠，不难发现小数点前有一位一直是 0，因此这个 0 我们就不必多花一位存储它了，因此我们的尾数都是小数点后的值。

如果一个 32 位浮点数在内存中的二进制表示如下：

bin:0b01000000010000000000000000000  
hex:0x40400000

那么可以发现它是正数，阶码为 128，尾数为 100000……，因为小数点后面的0都能忽略，因此尾数实际就是 1。然后注意这个阶码并不是真正的实际值，这只是它表面上看上去的值，再给它减去一个 127 之后可以发现指数为 1。小数位数因为有一个隐含的 1，所以它的实际值为 1.1，十进制值就是 1.5，所以最后结果就是 1.5*2^1=3。

然后我们再运行程序看看 3 的字节显示。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* $begin show-bytes */

typedef unsigned 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]);    //line:data:show_bytes_printf
    printf("\n");
}
int main() {
    float x = 3.0;
    show_bytes(&x, sizeof(x));
}

舍入

因为浮点数的表示方法限制了浮点数的范围和精度，多以我们需要利用特定的系统的方法使存储的数据无限接近于实际的数字，这就是舍入的工作。

总共有四种舍入的方法，下表为原理示例：

方式	1.40	1.60	1.50	2.50	-1.50
向偶数舍入	1	2	2	2	-2
向零舍入	1	1	1	2	-1
向下舍入	1	1	1	2	-2
向上舍入	2	2	2	3	-1

其中，向偶数舍入也就是向最近的值舍入，其他的方法原理均和字面含义相同

浮点运算

浮点数的加法和减法遵循一般的二进制加法和减法规则，但需要额外考虑指数部分的对齐。

浮点数的乘法和除法也遵循一般的二进制乘法和除法规则，但需要额外的处理来正确处理指数和尾数。具体来说，乘法时将指数相加，尾数相乘，然后对结果进行规范化。除法时将指数相减，尾数相除，然后对结果进行规范化。

比如最经典的：

1+1e111-1e111!=1e111-1e111+1

CSAPP - DataLab

int

bitXor

题目要求：只使用 ~ 和 & 来实现 ^ 操作

~ 按位非（每位二进制取反）
& 按位与（对应位同为1结果位才为1）
| 按位或（只要有一位是1结果位就是1）
^ 亦或（对应位相同为0，不同为1）

首先可以想到 x^y = x&~y + ~x&y = (x&~y)|(~x&y)

接下来想办法替代 |，x|y=~(~x&~y)，所以最后的结果是：

/*
 * bitXor - x^y using only ~ and &
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ and &
 *   Max ops: 14
 *   Rating: 1
 */

#include <stdio.h>
int bitXor(int x, int y) {
    return ~(~(x & ~y) & ~(~x & y));
}

int main() {
    int x = 12;
    int y = 11;
    int result = bitXor(x, y);
    printf("bitXor(%d, %d) = %d\n", x, y, result);
    return 0;
}

tmin

题目要求：使用 ! ~ & ^ | + << >> 来获取 int 的最小值