CSAPP 第二章 信息存储

昨晚加班到2点钟，今天稀里糊涂的，还是做点题目来冷静一下。目前进度到40页，把第二章的第一部分，信息存储看完了。
第一大部分是进制之间的转换，目前主要是十六进制和二进制以及十进制之间的转换。

2.1 完成数字转换

1. 0x39A7F8，转换成二进制，就是把每位16进制展开，得到0011 1001 1010 0111 1111 1000
2. 1100 1001 0111 1011转换为16进制，就是把每四位转换成16进制，为0xC97B
3. 0xD5E4C，转换成二进制是 1101 0101 1110 0100 1100
4. 二进制 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 十六进制加法

1. 0x503C+0x8 ，直接相加 C=12+8 = 20,进1，余4，得到 0x5044
2. 0x503C-0x40 ，3-4不够减，借16，借完之后前一位变成F，得到0x4FFC
3. 0x503C+64 ，64是0x40，得到0x507C
4. 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种颜色的组合

1. 000 黑色的补是111 白色
2. 001 蓝色的补是110 黄色
3. 010 绿色的补是101 红紫色
4. 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