CMU15213 CSAPP course files stored in Linux (WSL)
CS:APP is an excellent material for learning computer systems and systems programming. However, it is inconvenient to use a virtual machine for self-learners. In this repo, I build a Docker image with most pre-requistes installed and attached all lab materials in it. You can directly use this Docker image xieguochao/csapp.
The original materials of CS:APP is from CMU: CS:APP labs.
The code server is based on https://github.com/cdr/code-server.
Install Docker or Podman
Clone Repository
git clone --branch 1.8 https://github.com/XieGuochao/csapp.git.cd csapp.
Build Image (Optional)
cd csapp-dockerdocker build -t csapp ..
Run
Under the root directory.
docker run -p 7777:7777 -v "$PWD/labs:/home/csapp/project" csapp
Then you can access your labs via browser http://localhost:7777/ with password csapp. You can find all files in labs under /home/csapp/project.
在我看来csapp更像是一个c语言的基础教程，里面涉及了许多更底层的原理，比如为什么强制类型转化只是把解释类型的作用更换了，而其比特位不变？为什么3<4<3最后返回结果是0？负数的反码+1为什么等于反码？
这些都是CSAPP所涉及到的内容，不过由于时间关系我会省去一些控制流相关的章节，毕竟我们知道if-else,switch等都是需要逻辑完备的东西。底层细节的布尔代数就不再赘述。
int val = 0x887654321;
byte_pointer valp=(byte_pointer) &val;
show_bytes(valp,1);
show_bytes(valp,2);
show_bytes(valp,3);A:小端法21 大端法:87
B:小端法21 43 大端法:87 65
C:小端法21 43 65 大端法:87 65 43| 表达式 | 结果 |
|---|---|
| !0x41 | 0x00 |
| !0x00 | 0x01 |
| !!0x41 | 0x01 |
| 0x69&&0x55 | 0x01 |
| 0x69||0x55 | 0x01 |
只使用位级和逻辑运算，编写一个C表达式，它等价于x==y。换句话说，x和y相等时它讲返回1，否则就返回0
return !(x^y);C 语言还提供了一组移位运算，向左或者向右移动位模式。对于一个位表示为
有一个相应的右移运算
让我们来看一个例子，下面的表给出了一个8位参数 x 的两个不同的值做不同的移位操作得到的结果：
| 操作 | 值 |
|---|---|
| 参数 x | [01100011] [10010101] |
| [00110000] [01010000] | |
|
|
[00000110] [00001001] |
|
|
[00000110] [11111001] |
斜体的数字表示的是最右端 (左移) 或最左端 (右移) 填充的值。可以看到除了一个条目之外，其他的都包含填充 0。唯一的例外是算术右移 [10010101]的情况。因为操作数的最高位是1，填充的值就是 1。
C 语言标准并没有明确定义对于有符号数应该使用哪种类型的右移——算术右移或者逻辑右移都可以。不幸地，这就意味着任何假设一种或者另一种右移形式的代码都可能会遇到可移植性问题。然而，实际上，几乎所有的编译器/机器组合都对有符号数使用算术右移。
与C相比，Java对于如何进行右移有明确的定义。表达是x>>k会将x算数右移k个位置，而x>>>k会对x做逻辑右移操作。
算数右移会保留符号位，因此可以直接将无符号数转换为有符号数，而逻辑右移会将符号位补0，因此需要先左移24位，再右移24位，
#include <stdio.h>
int fun1(unsigned word){
return (int)((word<<24)>>24);
}
//算数右移会保留符号位，因此可以直接将无符号数转换为有符号数。
//而逻辑右移会将符号位补0，因此需要先左移24位，再右移24位，
int fun2(unsigned word){
return ((int)(word<<24)>>24);
}
//将无符号数转换为有符号数后，再进行算数右移。
//注意：在C语言中，右移操作符的行为取决于操作数的类型。
int main(){
unsigned int a[]={0x00000076,0x87654321,0x000000c9,0xEDCBA987};
for(int i=0; i<4; i++){
printf("fun1(0x%08x) = %d\n", a[i], fun1(a[i]));
printf("fun2(0x%08x) = %d\n", a[i], fun2(a[i]));
}
return 0;
}
1<<2+3<<4，在程序看起来则是1<<(2+3)<<4
| 符号 | 类型 | 含义 |
|---|---|---|
| B2Tw | 函数 | 二进制转补码 |
| B2Uw | 函数 | 二进制转无符号数 |
| U2Bw | 函数 | 无符号数转二进制 |
| U2Tw | 函数 | 无符号数转补码 |
| T2Bw | 函数 | 补码转二进制 |
| T2Uw | 函数 | 补码转无符号数 |
| TMinw | 常数 | 最小补码值 |
| TMaxw | 常数 | 最大补码值 |
| UMaxw | 常数 | 最大无符号数 |
| +tw | 操作 | 补码加法 |
| +uw | 操作 | 无符号数加法 |
| *tw | 操作 | 补码乘法 |
| *uw | 操作 | 无符号数乘法 |
| -tw | 操作 | 补码取反 |
| -uw | 操作 | 无符号数取反 |
Note
反码的计算如下:
- 对于正数，反码与原码相同
- 对于负数，符号位保持不变，其余按位取反。
e.g:-3的原码是1011，反码为1100
对向量$\vec{x}=[x_{w-1},x_{w-2},...,w_0]:$ $$ B2U_w(\vec{x})=\sum^{w-1}_{i=0} x_i2^i $$
在这个定义中，将字的最高有效位解释为负权(negative weight）。我们用函数$B2T_{w}$(Binary to Two's-complement，长度为$w$)来表示: A
**原理：**补码编码的定义
对向量$\vec{x}=[x_{w-1},x_{w-2},...,w_0]:$ $$ B2T_w(\vec{x})=-x_{w-1}2^{w-1}+\sum^{w-2}{i=0} x_i2^i $$ 最高有效位$x{w-1}$也成为符号位，它的“权重”为$-2^{w-1}$，是无符号表示中权重的负数。 $$ B2T_4([0001])=-02^3+02^2+02^1+12^0=0+0+0+1=1\ B2T_4([0101])=-02^3+12^2+02^1+12^0=0+4+0+1=5\ B2T_4([1011])=-12^3+02^2+12^1+12^0=-8+0+2+1=-5\ B2T_4([1111])=-12^3+12^2+12^1+12^0=-8+4+2+1=-1 $$ **原理：**补码（Two's complement）编码的唯一性
函数$BWT_w$是一个双射。
我们定义函数$T2B_w$(即"补码到二进制")作为$BWT_w$的反函数，其长度为$w$位模式到$TMin_w$和$TMax_w$之间数字的映射，写作$B2T_{w}:{0,1}^w\rightarrow{TMin_w,...,TMax_w}$
补码的范围是不对称的:$|TMin|=|TMax|+1$，也就是说，TMin没有与之对应的正数。
反码(Ones' Complement):除了最高有效位的权是$-(2^{w-1}-1)$而不是$-2^{w-1}$，它和补码是一样的： $$ B2O_w(\vec{x})=-x_{w-1}(2^{w-1}-1)+\sum^{w-2}{i=0}x_i2^i $$ 原码(Sign-Manitude):最高有效位是符号位，用来确定剩下的位应该取负权还是正权： $$ B2S_w(\vec{x})=(-1)^{x{w-1}}\sum^{w-2}_{i=0}x_i2^i $$
short x = 12345;
short mx = -x;
printf("Bytes for x (12345):\n");
show_bytes((byte_pointer) &x, sizeof(short));
printf("Bytes for mx (-12345):\n");
show_bytes((byte_pointer) &mx, sizeof(short));在大端法机器上运行时，这段代码的输出为30 39和cf c7，指明x的十六进制表示为0x3039，而mx的十六进制表示为0xCFC7。
(在WSL中是小端存储)
E.g:
short int v =-12345;
unsigned short uv =(unsigned short)v;
printf("v = %d,uv =%ud",u,uv);原理：补码转换为无符号数 对满足$TMin_w \leq x \leq TMax_w$的x有： $$ T2U_w(x)= \begin{cases} x + 2^w & \text{if } x < 0 \ x & \text{if } x \geq 0 \end{cases} $$
推导：补码转换为为无符号数 $$ B2U_w(T2B_w(x))=T2U_w=x+x_{w-1}2^w $$
原理：无符号数转换为补码，对满足$0\leq u \leq UMax_w$的u有 $$ U2T_w(u)= \begin{cases} u, &\text{if } u\leq TMax_w \ u-2^{w},&\text{if } u> TMax_w \end{cases} $$
常用的运算是在不同字长的整数之间转换，同时又保持数值不变。当然，当目标数据类型太小以至于不能表示想要的值得时候，这根本就是不可能的。然而，当一个较小的数据类型转换到一个较大的数据类型，应该是总能可能的。
要将一个无符号数转换为一个更大的数据类型，我们只需要简单地在表示的开头添加0。这种运算被称为零扩展 (zero extension)，表示原理如下：
原理: 无符号数的零扩展
定义宽度为
原理: 补码数的符号扩展
定义宽度为 w 的位向量$\vec{x}=[x_w−1,x_w−2,cdots,x_0]$和宽度为 w′ 的位向量
short sx = -12345; /* -12345 */
unsigned short usx = sx; /* 53191 */
int x = sx; /* -12345 */
unsigned ux = usx; /* 53191 */
printf("sx = %d:\t", sx);
show_bytes((byte_pointer) &sx, sizeof(short));
printf("usx = %u:\t", usx);
show_bytes((byte_pointer) &usx, sizeof(unsigned short));
printf("x = %d:\t", x);
show_bytes((byte_pointer) &x, sizeof(int));
printf("ux = %u:\t", ux);
show_bytes((byte_pointer) &ux, sizeof(unsigned));在采用补码表示的 32 位大端法机器上运行这段代码时，打印出如下输出：
sx = -12345: cf c7
usx = 53191: cf c7
x = -12345: ff ff cf c7
ux = 53191: 00 00 cf c7
我们看到，**尽管 -12345 的补码表示和 53191 的无符号表示在 16 位字长时是相同的，但是在 32 位字长时却是不相同的。**特别地，-12345 的十六进制表示为
Tip
这里的意思是说：
-
符号扩展是针对有符号数的，它通过复制符号位来保持数值在扩展后不变。
-
零扩展是针对无符号数的，它通过在前面填充 0 来保持数值在扩展后不变。
虽然在 16 位时，-12345 的补码和 53191 的无符号表示在二进制上是相同的，但由于它们是不同类型的数（一个有符号，一个无符号），当它们被扩展到 32 位时，会遵循不同的扩展规则，从而得到不同的 32 位表示。
从字长
对它应用符号扩展，得到位向量 [1101]，表示的值 −8+4+1=−3。我们可以看到，对于 w=4，最高两位位的组合值是 −8+4=−4，与 w=3 时符号位的值相同。类似地，位向量 [111] 和 [1111] 都表示值 −1。
有了这个直觉，我们现在可以展示保持补码值的符号扩展。
推导：补码数值的符号扩展
令 w′=w+k，我们想要证明的是 $$ B2T_{w+k}([x_{w-1}, \cdots, x_{w-1}, x_{w-2}, \cdots, x_0]) = B2T_w([x_{w-1}, x_{w-2}, \cdots, x_0]) $$ 下面的证明是对 k 进行归纳。也就是说，如果我们能够证明符号扩展一位保持了数值不变，那么符号扩展任意位都能保持这种属性。因此，证明的任务就变成了： $$ B2T_{w+1}([x_{w−1},x_{w−1},x_{w−2},⋯,x_0])=B2Tw([x_{w−1},x_{w−1},⋯,x_0]) $$
用等式 (2.3) 展开左边的表达式，得到： $$ \begin{align*}
B2T_{w+1}([x_{w-1}, x_{w-1}, x_{w-2}, \cdots, x_0]) &= -x_{w-1}2^w + \sum_{i=0}^{w-1} x_i 2^i \
&= -x_{w-1}2^w + x_{w-1}2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i \
&= -x_{w-1}(2^w - 2^{w-1}) + \sum_{i=0}^{w-2} x_i 2^i \
&= -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i \
&= B2T_w([x_{w-1}, x_{w-2}, \cdots, x_0])
\end{align*}
$$
我们使用的关键属性是
当一个 w 位的数
原理：截断无符号数
令等于 w 位的向量$ x=[x_{w−1},x_{w−2},⋯,x0]$，而 x′ 是将其截断为 k 位的结构：$x′=[x_{k−1},x_{k−2},⋯,x_{0}]$。令
该原理背后的直觉是所有被截去的位在其权重形式都为
推导：截断无符号数
通过对等式 (2.1) 应用取模运算就可以看到：
$$
\begin{align*} B2U_w([x_{w-1}, x_{w-2}, \cdots, x_0])
\bmod 2^k
&=\left[\sum_{i=0}^{w-1} x_i 2^i\right] \bmod 2^k \
&= \sum_{i=0}^{w-1} (x_i 2^i \bmod 2^k) \
&= \sum_{i=0}^{k-1} x_i 2^i \
&= B2U_k([x_{k-1}, x_{k-2}, \cdots, x_0]) \end{align*}
$$
在这些推导中，我们利用了属性：对于任何
Note
实际上这些截断也只是把目标位数的赋值变为0。
可以从下面代码中遇见:
int u =32768;
short a = (short)u;
unsigned short ua = (unsigned short)a;
printf("u=%d, a= %d \n",u,a);
printf("a = %d, uv = %u\n", a, ua);
-
short a = (short)u;发生了截断。int 通常是 32 位，short 是 16 位。32768在 32 位表示中是一个正数，但它在 16 位补码中的最高位是 1，因此会被解释为负数。$32768bmod2^{16}=32768$，而$U2T_{16}(32768)=32768−65536=−32768$ 。所以a的值是 -32768。 -
unsigned short ua = (unsigned short)a;将a的位模式（补码）重新解释为无符号数，因此ua的值是 32768。
补码截断也具有相似的属性，只不过要将最高位转换为符号位：
原理：截断补码数
令等于 w 位的向量
在这个公式中，$x \mod2^k$ 将是 0 到
推导：截断补码数
使用与无符号数截断相同的参数，则有 $$ B2Uw([x_{w−1},x_{w−2},⋯,x0])mod2^k=B2U_k([x_{k−1},x_{k−2},⋯,x_0]) $$
也就是说，$x\mod2^k$ 能够被一个位级表示为
总而言之，无符号数的截断结果是： $$ B2U_k([x_{k-1}, x_{k-2}, \cdots, x_0]) = B2U_w([x_{w-1}, x_{w-2}, \cdots, x_0]) \bmod 2^k \quad (2.9) $$ 而补码数字的截断结果是： $$ B2Tk([x_{k−1},x_{k−2},⋯,x_{0}])=U2Tk(B2Uw([x_{w−1},x_{w−2},⋯,x0])mod2^k) \quad(2.10) $$
Note
换而言之
由于数据的加减是通过补码进行运算的。我们通常会将数据从原码转换到补码，即取反码+1
对于满足$0\leq x,y\leq UMax_w$的$x$和$y$有: $$ x\times^{u}_{w}y = (x\times y) mod \ 2^w \quad\quad\quad(2.16) $$
对满足$TMin_w \leq x,y\leq TMax_w$的x和y有: $$ x\times ^{t}_wy=U2T_w(x\times y)mod2^w) \quad \quad \quad (2.17) $$
Tip
对于双精度浮点数，有负零和正零之分，但是他们取值是相同的：
While -0.0 and 0.0 have the same mathematical value, they are represented differently in a computer's memory according to the IEEE 754 standard for floating-point numbers. They have the same value because the standard defines them as numerically equal, but they exist as distinct bit patterns to preserve directional information from certain calculations.
Floating-point numbers are stored in three parts: a sign bit, an exponent, and a mantissa (or significand).
-
Sign Bit: This single bit determines if the number is positive (0) or negative (1). For both
0.0and-0.0, the exponent and mantissa bits are all zero. The only difference is the sign bit. For0.0, the sign bit is 0, while for-0.0, the sign bit is 1. -
Numerical Equality: The IEEE 754 standard specifies that when a comparison is made (e.g., using
==), the sign bit is ignored for zero values. This means the result of-0.0 == 0.0will always be true. This is why they have the same value in a logical or mathematical sense, even though they have different bit representations.The distinction between
0.0and-0.0is critical for preserving sign information, particularly in calculations involving division or functions likeatan2.
For example, consider the function 1.0 / x.
- If
xapproaches zero from the positive side (e.g.,0.0001,0.00001, etc.), the result approaches positive infinity. This is represented in the floating-point standard as+INF. - If
xapproaches zero from the negative side (e.g.,-0.0001,-0.00001, etc.), the result approaches negative infinity. This is represented as-INF.
If a calculation results in a value that is mathematically zero but came from a negative direction, the use of -0.0 preserves this directional information. This is useful for numerical stability and correctness in specific algorithms, especially those that deal with complex numbers or trigonometry.