CSAPP笔记
# 第一讲
# 位运算
# &运算 (and)
| & | 1 | 0 |
|---|---|---|
| 1 | 1 | 0 |
| 0 | 0 | 0 |
# ｜运算 (or)
| ｜ | 1 | 0 |
|---|---|---|
| 1 | 1 | 1 |
| 0 | 1 | 0 |
# ^运算
| ^ | 1 | 0 |
|---|---|---|
| 1 | 0 | 1 |
| 0 | 1 | 0 |
# ~(取反)
| ~ | 取反结果 |
|---|---|
| 1 | 0 |
| 0 | 1 |
# signed and unsigned
signed的数第一位「二进制」，代表了符号，1为负，0为正。
unsigned的数第一位「二进制」，不代表符号，也只是代表值。
Unsigned & Signed Numeric Value
| x | B2U(X) | B2T(X) |
|---|---|---|
| 0000 | 0 | 0 |
| 0001 | 1 | 1 |
| 0010 | 2 | 2 |
| 0011 | 3 | 3 |
| 0100 | 4 | 4 |
| 0101 | 5 | 5 |
| 0110 | 6 | 6 |
| 0111 | 7 | 7 |
| 1000 | 8 | -8 |
| 1001 | 9 | -7 |
| 1010 | 10 | -6 |
| 1011 | 11 | -5 |
| 1100 | 12 | -4 |
| 1101 | 13 | -3 |
| 1110 | 14 | -2 |
| 1111 | 15 | -1 |
TMax && TMin && UMax
TMax: 有符号数的最大值，即二进制下符号位为0，其他位的数为1的情况。
TMin: 有符号数的最小值，即二进制下符号位为1，其他位的数为0的情况。
UMax: 无符号数的最大值，即二进制下所有位数都为1的情况
规律
|TMin| = TMax + 1;
|UMax| = 2 * TMax + 1;
| 8 | 16 | |
|---|---|---|
| UMax | 255 | 65,535 |
| TMax | 127 | 32,767 |
| TMin | -128 | -32,768 |
样例表格
| Constant1 | Constant2 | Relation | Evaluation |
|---|---|---|---|
| 0 | 0U | == | unsigned |
| -1 | 0 | < | signed |
| -1 | 0U | > | unsigned |
| 2147483647 | -2147483647-1 | > | signed |
| 2147483647U | -2147483647-1 | < | unsigned |
| -1 | -2 | > | signed |
| (unsigned)-1 | -2 | > | unsigned |
| 2147483647U | 2147483648U | < | unsigned |
| 2147483647U | (int)2147483648U | > | signed |
位的延伸和收缩
1.延伸：
(1)如果是signed的数，延伸最左边的符号位，不改变该数的值。
(2)如果是unsigned的数，延伸最左边的位数，如果为1则翻倍加1；如果为0则不改变。
2.收缩：
(1)如果最左和最左右边一个相同并且是signed，则我们不改变值。
(2)如果是signed，并且最左和最左右边一个不相同，最左位为1，则变大，最左位为0，则减小。
(3)如果是unsigned,最左位为0，不改变，最左位为1，改变。
(4)收缩相当于对这个数做取模「2^w」运算
# 第二讲
# signed和unsigned的加减乘与溢出问题
加减
先看看unsigned的运算
| + | 二进制 | ans |
|---|---|---|
| 5 | 0101 | 7 |
| 7 | 0111 | 5 |
| 12 | 1100 | 12 |
没啥问题
再看看signed运算
| + | 二进制 | ans |
|---|---|---|
| -3 | 1101 | -3 |
| -6 | 1010 | -6 |
| -9 | 0111 | 7 |
并不是-9，而是7哦。
| + | 二进制 | ans |
|---|---|---|
| 5 | 0101 | 7 |
| 7 | 0111 | 5 |
| 12 | 1100 | -4 |
并不是12，而是-4哦。
溢出问题
上面两个signed运算，-3+-6=7，以及5+7=-4
前者是负溢出，负数变成了正数，后者是正溢出，正数变成了负数。
原因是向前无法补位，只有四个位置，没有更大的位置给你放。
乘法
假设word.size()是w比特
1.unsigned:可以达到2*w比特
Result range: 0 <= x * y <=(2^w-1)^2 = 2^(2*w)-2^(w+1)+1;
2.两个补码相乘的最小值:可以达到(2*w-1)比特
Result range: x * y >= ((-2)^(w-1)) * (2^(w-1)-1) = (-2)^(2*2-2) + 2^(w-1);
3.两个补码相乘的最大值:可以达到2*w比特，但是只到(TMin)^2
Result range: x * y <= (-2^(w-1))^2 = 2^(2*w-2)
乘法必然会溢出，但是我们还是只考虑范围内的，也就是只考虑word.size()的。
范围内求法
怎么得到这个范围内的数呢？==>mod！
eg:
5 * 5 = 25
而在二进制中，25是9。
25 mod 2^4 = 9
u * v mod 2^w
小端序/大端序