「CSAPP学习笔记」 Data Lab

观看《深入了解计算机系统》(CSAPP) 和 CMU15213 后的笔记,与做$\text{Data Lab}$时遇到的困难与解答。

书本 |《深入了解计算机系统》
网课地址0 | Here
Labs地址1 | Here

$\text{Bits, ints and float}$

$\text{Data Lab}$ 主要用于加深了我对数字 在计算机中的编码($\text{encoding}$)表示 的印象,以及一些位($\text{bit}$)级别的转换和计算操作,帮助我更好的理解了,二进制中数字的表示和处理,所以笔记侧重记录于 二进制编码用二进制的方式看待计算

$\text{Bits & Ints}$

无符号编码

$\text{Unsigned Encoding}$

$\text{B2U(X) = } \sum_{i \leq 0}^{n}{X_i * 2^i}$

二进制补码编码

$\text{Two’s-Complement Encoding}$

$\text{B2T(X) = } -X_w * 2^n + \sum_{i \leq 0}^{n-1}{X_i} \qquad (X_w = \text{sign bit})$

布尔代数

$\text{And}$ $\text{Or}$ $\text{Not}$ $\text{Xor}$
and_ba or_ba Not_ba xor_ba

实例如下

tmp_ba

一些杂记

  • $\text{Unsigned}$
    • $U_{max} = \text{0xFFFFFFFF} = 2^{32}-1$
    • $U_{min} = 0$
  • $\text{Two’s-Complement}$
    • $T_{min} = 10000… = \text{0x80000000}$
    • $T_{max} = 01111… = \text{0x7FFFFFFF}$
    • $T_{min} = -T_{max}-1$
    • $abs(T_{min}) = T_{min}$ overflow
    • $\text{0xFFFFFFFF} = -1$
  • $\text{U2T & T2U}$
    • $U_{max} = T_{max} \ll 1 + 1$
  • 位扩展($\text{Sign Extension}$)
    • 扩展k位 = 向右复制k位符号位
理论公式 正数位扩展 负数位扩展
sign extension po_sex neg_sex
  • >> 右移 ($\text{Right shift}$)
    • 逻辑右移($\text{Logical shift}$)
      • 特点:左侧都填充 0
    • 算数右移($\text{Arithmetic shift}$)
      • 特点:左侧都填充的为 符号位
      • C语言默认为算数右移

$\text{Float}$2

用二进制表示小数

表示 $b_i$ $b_{i-1}$ $b_2$ $b_1$ $b_0$ . $b_{-1}$ $b_{-2}$ $b_{-3}$ $b_{-j}$
权值 $2^{i}$ $2^{i-1}$ 4 2 1 . $\frac{1}{2}$ $\frac{1}{4}$ $\frac{1}{8}$ $2^{-j}$

例子:

$\text{IEEE Standard 754}$

有意思 的是使用IEEE754标准,来编码的时候会出现 +0-0

由于直接使用二进制表示小数的范围十分有限,所以 C语言 采用了 IEE754 标准来对浮点数($\text{Float}$)进行编码,来表示小数。

浮点数的数学表示形式为 $\text{Float} = {(-1)^s}{M}{2^E}$,其中$M$表示尾数($Mantissa$)4,$E$表示指数($Exponent$),$s$表示符号,含义同二进制补码中的符号位($sign \ bit$)。

二进制例子:

编码($\text{Encoding}$)

  • $\text{s = S}$
  • $\text{E = exp - bias or 1 - bias}$5
    • $\text{bias}$6 $ \ = 2^{sizeof(exp)-1}-1$
    • 32位的 $\text{bias}$ 为 127
    • 64位的 $\text{bias}$ 为 1023
  • $\text{frac = M}$
32位 64位
32_fencoding 64_fencoding

根据 exp 的不同,我们被编码的值分为 三种 情况。

exp 皆为0 既有0,又有1 皆为1
$\text{Values}$ $\text{Denormalized}$ $\text{Normalized}$ $\text{Special}$
  • $\text{s}$ 的计算方法
    • 正数 = 0
    • 负数 = 1

规格化($\text{Normalized}$)

  • $\text{frac}$ 的 计算方法。
    • 需要将 $(11111.11011)_{2} \rightarrow {(1.111111011)_{2}}*{2^4}$,即将 $\text{1xxxx.xxxx} \rightarrow \text{1.xxxxxxx}*{2^n}$。
    • $\text{frac = xxxxxx…} \leftarrow$ 指 1.xxxxx 中的 .xxxxx
    • 当然,只取 23/54 位数。 这就是为什么 浮点数不准的原因(并不是所有十进制小数都能 完美/有限 转化为二进制)。
  • $\text{E = exp - bias}$
  • 值 $ = (-1)^s*{1. \text{frac}}*{2^{exp-127}}$

非规格化($\text{Denormalized}$)

$\text{exp}$ 全都为 0 的情况
非规格化即为对 $\text{0.xxxxxx}$ 进行编码

  • $\text{E = 1 - bias = 127}$
  • $\text{frac = xxxxxx…} \leftarrow$ 指 0.xxxxx 中的 .xxxxx
  • $\text{exp = 0}$
  • 值 $= (-1)^s*{0. \text{frac}}*{2^{-126}}$

特殊值($\text{Special}$)

$\text{exp}$ 全为0

  • $\infty \text{(Infinity)}$
    • $\text{frac}$ 全为0
    • $\text{s = 0} \rightarrow +\infty$
    • $\text{s = 1} \rightarrow -\infty$
  • $\text{Not-a-Number(NAN)}$
    • $\text{frac}$ 不全为0

舍入($\text{Rounding}$)

其他舍入方法详见 《CSAPP》 其余舍入方式都很好理解

IEEE754标准的默认取舍方式是 向偶数舍入($\text{round to even}$),也称 向最近舍入($\text{round to the neartest}$)。
这种舍入方式的方式是 只有在被取舍部分为,当前的 中间值 时,向保留位的最近偶数位舍入,其余状况按照正常的’四舍五入’。

举个例子3

十进制 二进制
d_nround b_nround

一些杂记

乘法($\text{Multipcation}$) 加法($\text{Addition}$) 加法的解释
mul_fl add_fl add2_fl

$\text{Data Lab}$

综述

The Puzzles

$\text{datalab-handout}$

右上角带星号(*) 的 为可执行文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Makefile	- Makes btest, fshow, and ishow
README - Data Lab的介绍和使用
bits.c - 所有Puzzels所在的文件,即要补全的文件
bits.h - 头文件
btest.c - btest* 的源文件,详情可见Makefile
btest.h - 用于编译btest
decl.c - 用于编译btest
tests.c - 用于编译btest
tests-header.c- 用于编译btest
dlc* - 用于检查 bits.c 是否规则 (注意: btest 不会检查规则)
driver.pl* - 用于自动打分,调用了 dlc+btest
Driverhdrs.pm - "Beat the Prof" 模式的头文件(可选,详见REAME)
fshow.c - 查看 Float 表示的工具的源代码
ishow.c - 查看 Int 表示的工具的源代码

自测/使用工具

$\text{dlc/btest/driver.pl}$

温馨提示: 若 drivel.plbtest 结果不符,可以调用 dlc 来检测是否 bits.c 合规。

$\text{dlc}$使用指南

dlc 用于检测 bits.c 是否符合 规则限制,若不符合规则,则会报错。一切合规的话,就什么不会返回。

1
2
# 检测是否符合规则
./dlc bit.c

也可以添加 -e 选项,来显示每个函数所用的 操作符的个数

1
2
# 显示操作符个数
./dlc -e bits.c

使用例子

合规 不合规
dlc_ok dlc_nok

$\text{btest}$使用指南

注: btest 并不会检测 bits.c 是否符合规则。

使用make 来编译 btest*,详情的编译命令,在同目录下的 Makefile 中。编译成功后生成btest*,运行btest*即可测试函数正确性。

1
2
3
4
5
6
7
8
# 编译 btest*
make btest

# 测试 bits.c
./btest

# 查看 btest 帮助
./btest -h

由于 btest* 不会随着 bits.c 文件的更改而自动更改,所以当你修改了bits.c时,需要对btest*进行重新编译,来使得更改生效。

1
2
3
4
5
# 清理之前编译产生的中间文件
make clean

# 重新编译
make btest

$\text{drivel.pl}$使用指南

drivel.pl 的作用,约等于是 dlc + btest,但是不会提示错误信息。

1
2
# 运行自动打分程序
./drivel.pl

$\text{ishow/fshow}$

ishowfshow 是一个很好的辅助工具,用来帮助理解 数字 在 计算机中的 编码

可以使用make进行单独编译,也可以直接一次性全编译。(btest+ishow+fshow)

1
2
3
4
5
# 一次性全编译 btest + ishow + fshow
make

# 单独编译 ishow (fshow同理)
make ishow

使用案例:

$\text{ishow}$ $\text{fshow}$
ishow fshow

规则描述8

具体的函数会有具体的限定,此处只是综述。

$\text{Int}$ 规则

你的代码风格,可以参考如下

1
2
3
4
5
6
7
8
9
10
11
int Funct(arg1, arg2, ...) {
/* brief description of how your implementation works */
int var1 = Expr1;
...
int varM = ExprM;

varJ = ExprJ;
...
varN = ExprN;
return ExprR;
}

每个Expr表达式 仅允许使用:

  1. 0~255 (0xFF) 范围内的Int常量,包括0和255。(像 0xffffffff 此类的大常量不能使用)
  2. 函数所传入的变量,和函数内参数。(不能使用全局变量)
  3. 三元运算符 ~!
  4. 位运算符 &^|+<<>>

禁止使用:

  1. 所有的控制结构,例 if, do, while….
  2. 定义任何 。 (即预处理)
  3. bits.c 中新增函数。(你只能填空,不能自定义新函数)
  4. 调用函数
  5. 使用其他运算符,例 &&||- 或者 ? :
  6. 使用类型转化 (隐式也不行)
  7. 使用除了 int 以外的其他数据结构,例 arraysstructsunions….

检查你的机器:

  1. 确认你的机器使用 补码 来表示 32位的 int
  2. >> 操作是使用 算术右移
  3. 确认 << 小于0 和 >>大于31 的行为是不可预测的。

$\text{Float}$ 规则

禁止使用:

  1. 定义任何 。 (即预处理)
  2. bits.c 中新增函数。(你只能填空,不能自定义新函数)
  3. 调用函数
    4.使用类型转化 (隐式也不行)
  4. 使用除了 intunsigned 以外的其他数据结构,例 arraysstructsunions….
  5. 使用任何浮点指针数据类型,运算符 或 常量。

$\text{Puzzles}$ 笔记

$\text{bitXor}$

思路:

$\textbf{xor}$ 为 同0,异1a&b只会保留 全为1 的,而 (~a)&b 只会保留 a0/b1 的,所以答案是 a0/b1 | a1/b0,那么只要用 &~ 来复现 | 即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
/* 
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
int bitXor(int x, int y) {
int var1 = (~x) & y;
int var2 = x & (~y);
return ~((~var1)&(~var2));
}

$\text{tmin}$

思路:

显然补码的 $T_{min} \text{ = 0x80000000}$

代码:

1
2
3
4
5
6
7
8
9
/* 
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 1<<31;
}

$\text{isTmax}$

思路:

补码中有两个数很特殊, 0 和 $T_{min}$,这两个数的~+1皆为本身(后者是溢出,前者是排除 $\pm$ 0)。
思路就是使用这个特性(利用^),后排除x=0的可能情况即可。

$T_{min} \text{ = } \sim T_{max}$

代码:

1
2
3
4
5
6
7
8
9
10
11
12
/*
* isTmax - returns 1 if x is the maximum, two's complement number,
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 10
* Rating: 1
*/
int isTmax(int x) {
int var1 = ~x;
int var2 = x+1;
return !((var1^var2)|(!var1));
}

$\text{allOddbits}$

思路:

一直对半|即可,由于是偶数位,所以最后判断的是倒数第二位(即需要 >>1)。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 
* allOddBits - return 1 if all odd-numbered bits in word set to 1
* where bits are numbered from 0 (least significant) to 31 (most significant)
* Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
*/
int allOddBits(int x) {
int var1 = (x >> 16) & x;
int var2 = (var1 >> 8) & var1;
int var3 = (var2 >> 4) & var2;
int var4 = (var3 >> 2) & var3;
return (var4>>1)&1;
}

$\text{negate}$

思路:

在 CMU15213 的网课中有提及。

负数的补码就是源码取反+1

代码:

1
2
3
4
5
6
7
8
9
10
/* 
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return (~x)+1;
}

$\text{isAsciiDigit}$

思路:

先判断是否是0x30,然后判断是否在 0x0 ~ 0x9 之间。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 
* isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
* Example: isAsciiDigit(0x35) = 1.
* isAsciiDigit(0x3a) = 0.
* isAsciiDigit(0x05) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 3
*/
int isAsciiDigit(int x) {
int var1 = !(x >> 6);
int var2 = (x + 0x10) >> 6;
int var3 = x >> 3;
int var4 = (x >> 2) | (x >> 1);
var2 = var1 & var2;
var4 = var3 & var4;
return var2 & (~var4);
}

$\text{conditional}$

思路:

利用 xor 中 $ x \oplus 0 = x$ 和 $x \oplus x = 0$ 的特性进行实现。

所以可以得到一个表达式 $\text{ans = exp1^y^x^exp2}$,和下述表格。

$x$ 0 1
exp1 0 x
exp2 y 0

用位运算实现上述表格中的 exp 即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
* conditional - same as x ? y : z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) {
int var1 = !x;
int var2 = (~var1) + 1;
var1 = ~var2;
return (var2&y)^y^z^(var1&z);
}

$\text{isLessOrEqual}$

思路:

分类讨论三种情况,分别为同号异号相等
如果不考虑溢出(即同号情况),显然$x-y \leq 0$。

小提示:由于当 y = $T_{min}$ 时,转化为 -y 会溢出,但是如果限定为同号,则不会对判断造成影响。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLessOrEqual(int x, int y) {
int var1 = x>>31;
int var2 = y>>31;
int var3 = !(x^y); //x == y
int var4 = (~y)+1;
int var5 = ((x+var4)>>31)&1; //x-y < 0
int var7 = (var1^var2)&1;
int var8 = var7&var1; //1 when x<0 + y>0
int var9 = !(var7&var2); //0 when x>0 + y<0

return (var8|var3|var5)&var9;
}

$\text{logicalNeg}$

思路:

思路和 isTmax 相同,只有0的补码^源码 = 0,其余 最高位 都为1

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
* logicalNeg - implement the ! operator, using all of
* the legal operators except !
* Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int logicalNeg(int x) {
int var1 = (~x)+1;
int var2 = ((x>>31)|(var1>>31))&1;
return (~var2)+2;
}

$\text{howManyBits}$

思路:

这边使用^是一个很有意思的小技巧。

只有0/1所需要的位数是1位,其余答案是n+1n指从右向左第n位,从左向右第一个 1或07 的数字。

二分寻找第一次出现的位置,每次二分移动的长度,刚好为需要加入答案的长度。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* howManyBits - return the minimum number of bits required to represent x in
* two's complement
* Examples: howManyBits(12) = 5
* howManyBits(298) = 10
* howManyBits(-5) = 4
* howManyBits(0) = 1
* howManyBits(-1) = 1
* howManyBits(0x80000000) = 32
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int howManyBits(int x) {
int var = x^(x<<1);
int s16 = (!!(var>>16))<<4;
int b16 = var >> s16;
int s8 = (!!(b16>>8))<<3;
int b8 = b16 >> s8 & 0xff;
int s4 = (!!(b8>>4))<<2;
int b4 = b8 >> s4 & 0xf;
int s2 = (!!(b4>>2))<<1;
int b2 = b4 >> s2 & 3;
int s1 = !!(b2>>1);

return s16 + s8 + s4 + s2 + s1 + 1;
}

$\text{floatScale2}$

思路:

对 $\text{uf}$ 进行分类讨论操作。

  • 如果是 $\text{uf = NAN}$ 就直接返回 $\text{uf}$。
  • 如果是 $\text{Denormalized}$,直接将$\text{frac}$ 向右移1即可,因为$\text{Denormalized}$和$\text{Normalized}$之间有完美的过度。
  • 如果是 $\text{Normalized}$。
    • 若溢出,则返回 $\text{inf}$ (注意符号)
    • 否,则正常编码返回即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* 
* floatScale2 - Return bit-level equivalent of expression 2*f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's, but
* they are to be interpreted as the bit-level representation of
* single-precision floating point values.
* When argument is NaN, return argument
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned floatScale2(unsigned uf) {
unsigned uf_s = uf&0x80000000;
unsigned uf_exp = (uf>>23)&0xff;
unsigned uf_frac = uf&0x007fffff;
unsigned res;
if(uf_exp == 0xff && uf_frac != 0) res = uf^uf_s;
else if(uf_exp == 0) res = uf<<1;
else {
unsigned res_exp = uf_exp+1;
if(res_exp > 0xff) res = 0x7f800000;
else res = (res_exp << 23)|uf_frac;
}
return res^uf_s;
}

$\text{floatFloat2int}$

思路:

按照 $\text{IEEE754}$ 标准来解码即可。

  • $\text{Denormalized}$ 情况下即返回 0
  • $\text{Nan && Inf}$ 返回 0x80000000 (即$T_{min}$)。
  • $\text{Normalized}$ 情况下。
    • 超出 $\text{Int}$ 表示范围,返回0x80000000
    • 其余正常返回即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* 
* floatFloat2Int - Return bit-level equivalent of expression (int) f
* for floating point argument f.
* Argument is passed as unsigned int, but
* it is to be interpreted as the bit-level representation of a
* single-precision floating point value.
* Anything out of range (including NaN and infinity) should return
* 0x80000000u.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
int floatFloat2Int(unsigned uf) {
int uf_s = !!(uf>>31);
int uf_E = ((uf >> 23) & 0xff) - 127;
int uf_frac = (uf & 0x007fffff) | 0x008fffff;
int res;
if(uf_E < 0) res = 0;
else {
int right_shift = -(23-uf_E);
if(right_shift > 7) res = 0x80000000;
else if(right_shift < 0) res = uf_frac >> (-right_shift);
else res = uf_frac << right_shift;
if(uf_s) res = (~res)+1;
}
return res;
}

$\text{floatPower2}$

按照$\text{IEEE754}$标准编码即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 
* floatPower2 - Return bit-level equivalent of the expression 2.0^x
* (2.0 raised to the power x) for any 32-bit integer x.
*
* The unsigned value that is returned should have the identical bit
* representation as the single-precision floating-point number 2.0^x.
* If the result is too small to be represented as a denorm, return
* 0. If too large, return +INF.
*
* Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
* Max ops: 30
* Rating: 4
*/
unsigned floatPower2(int x) {
unsigned inf = 0x7f800000;
unsigned res = 0;
int exp = x + 127;
if(exp >= 255) res = inf;
else if(exp < 0) res = 0;
else res = exp << 23;
return res;
}

$\text{Self Evaluate}$

以下为使用 drivel.pl 对上述解答的打分截图

done


0. 课程为CMU15213,来源 Bilibili
1. CSAPP书本官网,此次为 Data Lab
2. IEE754标准,并不是所有CPU都支持,例如 Cell BE
3. CMU15213课件 “04-float.pdf”
4. 尾数的范围 $[1.0 ,2.0)$
5. 当exp全为0时,E = 1 - bias
6. bias 即 偏移量
7. 负数为0,正数为1
8. 详细可见 datalab-handout/bits.c


--------------------------END--------------------------
喜欢的话,不妨请我喝杯奶茶(≧∇≦)ノ