CSAPP 第二章 信息存储
昨晚加班到2点钟，今天稀里糊涂的，还是做点题目来冷静一下。目前进度到40页，把第二章的第一部分，信息存储看完了。
第一大部分是进制之间的转换，目前主要是十六进制和二进制以及十进制之间的转换。
2.1 完成数字转换
- 0x39A7F8，转换成二进制，就是把每位16进制展开，得到0011 1001 1010 0111 1111 1000
- 1100 1001 0111 1011转换为16进制，就是把每四位转换成16进制，为0xC97B
- 0xD5E4C，转换成二进制是 1101 0101 1110 0100 1100
- 二进制 1001 1011 1001 1110 1101 01，先重新分组，按照4位补齐 0010 0110 1110 0111 1011 0101，在转换成16进制，结果是26E7B5
有一种将2的整数次幂快捷转换成16进制的方式：由于2的n次方直接可以写成1加上n个0，而四个二进制的0对应一位十六进制的0。只要计算出n里边有几个4(n/4)和n的余数(n%4)，几个4就是几个16进制的0，如果正好整除，说明是16的倍数，最开头补一个1。而余数的可能值为1,2,3。余数是1的时候就是十进制的2，是2的时候是十进制的4，是3的时候就是十进制的8，直接转换成十六进制写在最前边即可。
举一个例子：2的15次方，15/4 = 3, 15%4 = 3,则 2的15次方就是余数3对应的8加上3个十六进制0，结果是0x8000。
2.2 完成数字转换
| n |
2的n次方（十进制） |
2的n次方（十六进制） |
| 9 |
512 |
0x200 |
| 2的19次方 = 4*4+3 |
512*512*2 = 524288 |
0x80000 |
| 2的14次方 = 4*3+2 |
16384 |
0x4000 |
| 第一位是1，说明能整除。后边4个0，说明一共4*4 = 16 |
2的16次方 = 65536 |
0x10000 |
| 17 = 4*4+1 |
=16384*8 = 131072 |
0x20000 |
| 2的5次方，5= 4*1+1 |
32 |
0x20 |
| 第一位8表示余数3，然后是1位表示4，所以是2的7次方 |
128 |
0x80 |
2.3 转换字节到16进制
| 十进制 |
二进制 |
十六进制 |
| 0 |
0000 0000 |
0x00 |
| 167 |
1010 0111 |
0xA7 |
| 62 |
0011 1110 |
0x3E |
| 188 |
1011 1100 |
0xBC |
| 55 |
0011 0111 |
0x37 |
| 136 |
1000 1000 |
0x88 |
| 243 |
1111 0011 |
0xF3 |
| 82 |
0101 0010 |
0x52 |
| 172 |
1010 1100 |
0xAC |
| 231 |
1110 0111 |
0xE7 |
2.4 十六进制加法
- 0x503C+0x8 ，直接相加 C=12+8 = 20,进1，余4，得到 0x5044
- 0x503C-0x40 ，3-4不够减，借16，借完之后前一位变成F，得到0x4FFC
- 0x503C+64 ，64是0x40，得到0x507C
- 0x50EA-0x503C ，可以列竖式来计算，得到0xAE
C语言的长度和大小端表示整数
这里要注意的是指针的长度和位数也就是字长相等，所以32位下long=4，char * 也是4；64位下long = 8，char * 也是8。
其他C语言的数值的位数在32和64位X86上默认没有区别。
使用64位还是32位编译，要使用gcc -m32/-m64 main.c来指定编译。C99还有固定的int32_t和int64_t，固定长度的类型。
大端法和小端法。简单的说，就是计算机如果按照我们阅读的顺序，在内存的从小到大的地址中存放分组后的字节，就是大端法。反着来就是小端法。
INTEL X86使用小端法。除了硬件之外，大小端还和操作系统有关系。
通用的打印内存地址的程序：
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer start, size_t len) {
size_t i = 0;
for (; i < len; i++) {
printf("%.2x ", start[i]);
}
printf("\n");
}
void show_int(int x) {
show_bytes((byte_pointer) &x, sizeof(int));
}
void show_float(float x) {
show_bytes((byte_pointer) &x, sizeof(float));
}
void show_double(double x) {
show_bytes((byte_pointer) &x, sizeof(double));
}
由于要打印字节，一般都要使用 char *，这里要注意使用无符号整数的指针，否则会出现错误。另外长度和循环也要统一使用无符号整数互相比较，这样就不会出错。
运行的时候，指针指向的是最低字节，这个程序会打印指定的数据在内存中的实际存放方式。
在main函数中实验：
int main()
{
int x = 12345;
float y = (float) x;
show_int(x);
show_float(y);
}
结果是：
39 30 00 00
00 e4 40 46
先看上边的整数，由于12345很明显是0x3039，所以显然是大端。而强制转型并不是什么都没做，可以发现机器的表示发生了变化。
这说明浮点数和int有着某种对应换算关系，之后再回来看。现在可以知道，强制转型会让底层表示方法有变化，从而这些数值的操作（比如加减乘除）的方式也会有变化。
2.5 大小端表示法
很显然0x87654321的大端存放顺序就是 87 65 43 21，小端存放顺序是 21 43 65 87，所以：
| 函数 |
小端 |
大端 |
| show_bytes(valp,1) |
21 |
87 |
| show_bytes(valp,2) |
21 43 |
87 65 |
| show_bytes(valp,3) |
21 43 65 |
87 65 43 |
2.6 整数与浮点数的表示
0x00359141写成二进制是：0000 0000 0011 0101 1001 0001 0100 0001。
0x4A564504写成二进制是：0100 1010 0101 0110 0100 0101 0000 0100。
移动一下找匹配的部分：
00000000001101011001000101000001
01001010010101100100010100000100
有21位相同。看上去除了最高的一位1，整数的部分都包含在float中。
表示字符
ACSII字符可以被解释成带符号的char类型数值，也就是整数。正好十进制的0-9，对应十六进制的0x30-0x39，方便转换。而大小写字母的转换，在于第五位的不同。
2.7的结果很显然就是打印出来61-66
布尔逻辑 - 位运算
~取反，&与，|或，^异或。
其他的都好懂，异或只要记住，两个数字相同就是0，不同就是1。取反和与1异或相同。与0异或结果不变，与&运算相同。而设置成1是使用|，设置成0则使用&0。
除了可以对标量进行逻辑运算，对向量也可以，遵循的方法是对向量的每一个相同的位进行逻辑运算。
2.8 位向量布尔运算
| 运算 |
结果 |
| a |
01101001 |
| b |
01010101 |
| ~a |
10010110 |
| ~b |
10101010 |
| a&b |
01000001 |
| a|b |
01111101 |
| a^b |
00111100 |
一个位和自己的异或必定是0，而0和另外一个数字异或，结果还是另外一个数字。用这个方法可以有很多简化的算法。
位向量的用法很多，可以表示集合，或者取掩码。需要灵活掌握。
2.9 用三位位向量表示8种颜色的组合
- 000 黑色的补是111 白色
- 001 蓝色的补是110 黄色
- 010 绿色的补是101 红紫色
- 011 蓝绿色的补是100 即红色
另外四种颜色的补色，就是反向关系。
蓝色 | 绿色 = 001 | 010 = 011 蓝绿色
黄色 & 蓝绿色 = 110 & 011 = 010 绿色
红色 ^ 红紫色 = 100 ^ 101 = 001 蓝色
2.10 异或交换变量值
void in_place_swap(int *x,int *y){
*y = *x ^ *y; /* STEP 1 */
*x = *x ^ *y; /* STEP 2 */
*y = *x ^ *y; /* STEP 3 */
}
各步的值如下：
| 步骤 |
*x |
*y |
| 初始 |
a |
b |
| 第一步 |
a |
a^b |
| 第二步 |
b |
a^b |
| 第三步 |
b |
a |
2.11 会失败的交换元素位置：
void print_array(int a[], int cnt){
int i = 0;
printf("[");
for (; i < cnt; i++) {
printf("%d", a[i]);
if(i!=cnt-1){
printf(", ");
}
}
printf("]\n");
}
void reverse_array(int a[], int cnt){
int first, last;
print_array(a, cnt);
for(first=0,last= cnt-1;
first<=last;
first++,last--){
in_place_swap(&a[first], &a[last]);
}
print_array(a, cnt);
}
这样一个程序，如果长度为奇数，会失败：
int main()
{
int a[] = {1, 2, 3, 4, 5, 6};
int b[] = {1, 2, 3, 4, 5, 6, 7};
reverse_array(a, 6);
reverse_array(b, 7);
}
结果是：
[1, 2, 3, 4, 5, 6]
[6, 5, 4, 3, 2, 1]
[1, 2, 3, 4, 5, 6, 7]
[7, 6, 5, 0, 3, 2, 1]
这是因为长度在奇数的时候，&a[first]与&a[last]两个地址会指向同一个位置，即索引为(cnt+1)/2的元素，此时如果采用这种取异或的方法，直接会导致变量变成0。
修改这个方法也很简单，如果指向同一个元素的时候，不做任何工作就可以，所以直接将first=last的条件排除在for循环之外即可：
void reverse_array(int a[], int cnt){
int first, last;
print_array(a, cnt);
for(first=0,last= cnt-1;
first<last;
first++,last--){
in_place_swap(&a[first], &a[last]);
}
print_array(a, cnt);
}
位向量常做的是掩码运算。掩码的特点是，如果用1去做与运算，得到的是掩码的值。如果用0去做与运算，是将其置零。
想要取一个数值的某段掩码，就可以将指定的位数设置成1然后取出。而~0可以直接得到全1的掩码用于取出所有的值。
2.12 掩码取字节
x = 0x87654321，字长任何大于等于8的时候都能工作。
由于对于任何字长都要大于0，因此不能考虑符号。
//Question A
x & 0xFF /* 0xFF 的最低8位是1，高位不管多少，全都是0 */
//Question B 取补就是异或，但是最低8位不能变。很显然取补是和1异或，而和0异或就是不变。因此有：
x ^ (~0xFF)
//Question C 最低有效字节全部设置成1，其他字节不变。设置成1就是将位于1进行或运算，结果一定是1。
x | 0xFF
总之一句话，如果要不考虑字长的限制，则必须使用~来获得高位为1的掩码，而不能直接写死定长的掩码。
2.13 模拟bis和bic指令
bis指令是将掩码为1的地方强行设置为1，而其他地方不变。很显然设置为1就是用or，而且一位和0做or运算，结果不变。所以bis就是一个按位或运算。
所以实现按位或就是bis函数本身，即int result = bis(x, y)
bic是在m为1的地方，将z设置为0。实际上就是取反然后做与运算来设置为0。即 x&(~y)。
这个时候翻出计算机系统要素第10页的布尔函数表，发现异或是 x.(~y) + (~x).y
由于bic就是x&(~y),根据这个公式，只要bis(bic(x,y),bic(y,x))就可以得到异或了。
布尔逻辑 - 逻辑运算
C语言里有 ! && ||，原理和位运算的符号不同，而且|| 带有短路效果，在第一个表达式为TRUE的时候，不会再去判断后边的表达式。
依靠短路特性就可以写出很多简洁的代码比如：a&&5/a, p&&*p++。
2.14 位运算与逻辑运算的结果
x 是 0x66,也就是 01100110，y 是 0x39，也就是 00111001。
| 表达式 |
值 |
表达式 |
值 |
| x & y |
20 |
x && y |
01 |
| x | y |
7F |
x || y |
01 |
| ~x | ~y |
DF |
!x || !y |
00 |
| x & !y |
00 |
x && ~y |
01 |
2.15 x==y
编写一个表达式，仅使用位级和逻辑运算，当x和y相等的时候返回1，不相等的时候返回0。
首先是如何判断两数字相等，如果两个数字的位全部一样，就算相等。看到相等就想到异或。如果两个数字各个位全部相等，则异或得到0。再对异或的结果使用逻辑取反，就得到1。
因此表达式就是!(x ^ y)
移位
移位分为两种，逻辑移位和算术移位。其中左移都是一样的，在右边补0。
而右移的时候，算术逻辑根据最高位补对应的符号位，而逻辑移位只在最高位补0。
| x |
x<<3 |
x>>2(逻辑) |
x>>2(算术) |
| 十六进制 |
二进制 |
二进制 |
十六进制 |
二进制 |
十六进制 |
二进制 |
十六进制 |
| 0xC3 |
11000011 |
00011000 |
18 |
00110000 |
30 |
11110000 |
F0 |
| 0x75 |
01110101 |
10101000 |
A8 |
00011101 |
1D |
00011101 |
1D |
| 0x87 |
10000111 |
00111000 |
38 |
00100001 |
21 |
11100001 |
E1 |
| 0x66 |
01100110 |
00110000 |
30 |
00011001 |
19 |
00011001 |
19 |
