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
小端序/大端序