[C++知识库]CSAPP reading & solution records

CSAPP reading & solution records

Chapter1 Introduction/Preface

skip (read offline /doge)

Chapter2 Representation and processing of information

page33 旁注

man ascii在linux中可以生成ASCII表
注：
Oct - Octal - 八进制(O/Q)
Dec - decimal - 十进制
Hex - hexadecimal - 十六进制
Bin - binary - 二进制

page33 2.5

铺垫：定义了show_bytes函数
其中涉及知识：

1. size_t类型：“它是一种“整型”类型,里面保存的是一个整数,就像int, long那样。这种整数用来记录一个大小(size)。size_t 的全称应该是size type,就是说“一种用来记录大小的数据类型”。通常我们用sizeof(XXX)操作,这个操作所得到的结果就是size_t类型。因为size_t类型的数据其实是保存了一个整数,所以它也可以做加减乘除,也可以转化为int并赋值给int类型的变量。”
   ——摘自NickWei的博客
2. show_type函数

#include <stdio.h>
typedef unsigned char *byte_pointer; //定义字节指针（也就是指向某个字节的指针）

void show_types(byte_pointer start, size_t len)
{
    size_t i;
    for(i = 0; i < len; i++)
    printf("%.2x", start[i]); //打印16进制数字，并且默认是两位
    printf("\n");
}

void show_int(int x) //通过这种形式将int使用16进制字节形式打印出来
{
    show_bytes((byte_pointer) &x, sizeof(int));
}

书上32页的实验证明了
Linux32、Linux64、Windows都是小端机（最高位为权值较小的十六进制数字），而Sun是大端机。
值得一提的是，这个函数的字节输出检验大端OR小端方法并不适用于Pointer类型，原因是不同的机器/操作系统配置使用了不同的存储方式。
另外，由poinetr的字节表示可以看出的是Linux32、Sun、Windows使用的是4字节地址，而Linux64使用的是8字节地址。

结果是这道题的答案是显然的

page34 2.6

naive

page34 2.7

naive
需要注意的几点：

1. ‘a’ ~ 'z’的ASCII码为 0x61 ~ 0x7A
2. 二进制代码在不同的机器之间是不兼容的

page35 2.8

naive
需要注意：将bool运算扩展到位向量的运算上[a₁, a₂, a₃, …]

网络旁注: boolean ring

对于任何值a来说，a ^ a = 0，并且重新排列顺序仍然成立
例如：(a ^ b) ^ a = b

page37 2.9

naive

page38 2.10

exchange *x and *y by exclusive-or options
*x = *x ^ *y;
*y = *x ^ *y;
*x = *x ^ *y;
so interesting~

page39 2.11

不要进入思维误区，考虑的重点是 中间的两个元素的地址都是相等的 ，所以说一旦第一次运算得到的*x = 0之后，无论进行多少次运算，得到的都是0。

page38 掩码

作用就是将想要的位体现出来，不想要的位变成0
方式例如一个掩码时0xFF，一个数是x，那么就可以通过x & 0xFF将x的后八位(Bin)留下，其他位变成0。

page39 2.12

B: x ^ ~0xFF(最低有效字节不变，其他字节取补)
应用性质: 0 ^ x 不变，1 ^ x 取补
_A&C:naive

*page39 2.13

很有意思的一道题，给了我一些对于异或的思考：
集合的对称差运算实际上也叫做异或运算，异或运算(a ^ b)等价于$(?a\cap b)\cup (?b\cap a)$
这就是这道题第二个空的思路来源

annotation

C语言中的位级运算 &, |, ~，以及逻辑运算 &&, ||, ~

page40 2.14

naive
让机器做

page40 2.15

思路就是使用异或思想(( ~ a & b)|( ~ b & a)，得到两个数的异或，如果结果为0，就输出，否则两次!得到1
my_code:

#include <stdio.h>

int main()
{
    int a, b, c;
	scanf("%d%d", &a, &b);
	c = !!((~a&b)|(~b&a));
	printf("%d", c);
}

annotation

for shifting

1. 左移只有一种，就是舍弃最高位，右边补0
2. 右移有两种，逻辑右移(左端补k个0)，算术右移(左端补k个符号位)
3. 移位从左至右是可结合的即a>>b>>c，亦即(a>>b)>>c
4. 无符号数的右移都是逻辑右移
5. C语言中没有明确说明有符号数是哪种右移，而绝大多数机器的有符号数都是算术右移
6. Java中a>>>b是逻辑右移，a>>b是算术右移
7. 加减法的优先级高于移位，因此1<<2+3<<4 <=> 1<<5<<4

笑死

当移动位数大于实际最大位数的时候C语言标准很小心地规避了说明在这种情况下如何做，实际上位移量k是通过k mod w得到的，其中w是最大位数。

几个数字

$2^{15}=32768$
$2^{16}=65536$
$2^{31}=2147483648$

C/C++/Java的有/无符号数

C和cpp两种都有，Java只有有符号数

page45 2.17

A2B实际上就是用B的方式来解读A这个数，二者之间传递关系是位级表示不变
T denotes Two’s Implement (补码)
W denotes number of the bits of the data presentation (位数)
That’s all you need to pay attention to…

annotation

1. 不同机器的补码表示范围不同，为了提高可移植性，可以使用C语言的<limit.h>库文件，其中定义了INT_MAX, INT_MIN, UINT_MAX的宏
2. ISO C99中给出了<stdint.h>文件，其中含有intN_t, uintN_t类型，其中N一般为8、16、32、64
3. C语言中几乎所有机器都使用补码，也就是将数字当作有符号数，只有当数字后面有U时才认为这是无符号数输入时可用%u.
4. C语言中有符号数和无符号数进行运算默认会将有符号数看成无符号数进行运算

page53 2.21

其余以此类推

annotation

short转换成unsigned，转换顺序，先改变大小(也就是长短)，再进行有符号到无符号的转换

page56 2.23/2.24

naive

page58

2.25

将unsigned改成int
因为length(unsigned)与-1(ffffffff)相加时，-1会被当成65535($2^{32}?1$)，相加得到一个很大的数，达不到停止程序循环的目的。
或者改成i < length，避免了有符号和无符号的混合计算

2.26

不能说naive，相反给出了我们一些编写程序的时候的注意事项，就像size_t这个数据类型表示的是无符号数

annotation

如何检验unsigned是否溢出，可以通过相加得到的数与加数（两个都行）进行比较，如果得到和小于加数，就说明发生了溢出。

page62 2.27

if(x + y < x)
printf("Overflow!");
else printf("In normal condition.")

annotation

1. 无符号加法逆元：注意是$2^w$减去无符号数（正常减法），两个无符号相加等于$2^w$也就是相当于等于0，因为溢出舍去了。
2. 有符号数加法逆元：实际上都是取反加一，但是在将补码转换为数值表示的时候，会发现除了$T_{Min}$等于本身之外其余都等于自己的相反数。
3. 补码加法中，如果向上溢出（$x+y\ge 2^{w?1}$），就减去$2^w$，如果向下溢出（$x+y<?2^{w?1}$），就加上$2^w$。
   实际上就是做了截断，最后的结果显现出来的就是这样。
4. 如何判断是否出现补码（有符号数）加法的溢出？如果两个正数得到负数，或者两个负数得到正数就是溢出了。

*page65 2.31

x, y的补码加法运算形成了阿贝尔群！仔细品味这个性质。

**page65 2.32

很好的题，指出了1000…000($T_{Min}$)的特殊性，因为这个补码没有对相应的相反数，他的相反数正是他自己，与之相呼应的是，$T_{Min}+T_{Min}=0$。（因为上一位的0无法体现，因此在补码表示中就无法改变自己的符号）
这提醒我们，函数的任何测试中，$T_{Min}$都应该成为一种测试情况。

***page68 2.35

看着脑袋疼，我承认是我不耐烦了，先留个坑

page69 2.36

本来想得到乘积，判断是不是在范围里面，但是答案的也挺好
但是有个问题

就是这样得到的(int64_t)x*y是用64位的x与32位的y相乘吗，得到的是64位数吗？