CSAPP Data Lab 笔记

发表于 更新于 分类于 阅读次数：

禁用大量常见运算符, 强制规定特定位运算运算符和运算符数量限制实现特定运算

所谓 Hacker’s Delight

在写 CSAPP Lab 之前一定要仔细阅读文档, 一行要求都不能落下, 比如这个 lab 就有一些无聊的要求:

  1. 要求变量声明必须在开头(这 C89 古董规则太搞了)
  2. 不允许使用大字面量(超过 0xFF 的)

为了您的阅读方便, 本文对于特定位/位模式采用行内引用 (0 或 1, 1000, 1101), 对于数字的十进制值, 位的编号等采用 \(\LaTeX\) 的数字字体 (\(3, 4, 5, 6\))

0x1 bitXor

实现位运算的异或

众所周知 \(x \oplus y = (x \wedge \lnot y) \vee (\lnot x \wedge y)\)

取两次反, 德摩根定律化简 \(\lnot (\lnot (x \oplus y)) = \lnot (\lnot(x \wedge \lnot y) \wedge \lnot (\lnot x \wedge y))\)

1
int bitXor(int x, int y) { return ~(~(~x & y) & ~(x & ~y)); }

收获: 没有 德摩根定律其实是能化简一些逻辑表达式的, 但是在这个例子中完全体现不出来. 所以还是没有

0x2 tmin

返回 \(32\) 位补码能表示的最小值. 补码的最高位是负权重, 其他位都是正权重, 所以就是最高位为 1

1
int tmin(void) { return 1 << 31; }

如果对左移的位数有点反应不过来, 可以这样想: \(32\) 位补码的 \(32\) 位从低到高编号 \(0 \sim 31\), 对于 1 << n 就是向左移动 \(n\) 位从最低位 \(0\) 位移动到编号为 \(n\) 的那一位上.

收获: 没有. 没有。

0x3 isTmax

判断 x 是否是 \(32\) 位补码能表示的最大值. \(32\) 位补码能表示的最大值是最高位为 0, 其他位为 1 的 01111..., 纯按照位模式 \(+ 1\) 后即为 10000... (补码最小值), 但是注意这在标准 C 中是未定义行为, 我想了很久也查阅了很多做法都没有得到可以不依赖 UB 的解决方案, 这某种程度上算这个 lab 的败笔.

回到正题, 注意到 \(\text{Tmax} + 1\) 正好是 \(\text{Tmin}\), 而 \(\text{Tmax}\) 和 \(\text{Tmin}\) 的位模式恰好全部相反, 直接比较 ~(x + 1) 是否等于 x 即可, 但注意除了后面几个浮点数的题目, 所有题目都是禁用比较运算符的, 所以只能用异或再取反实现.

然后我跑了一下发现没过。 除了这个, 全 \(1\) 的位模式 11111... 在 \(+1\) 后是 00000..., 同样完全相反, 所以要特判一下 \(x\) 不是 ~0 (11111...)

1
int isTmax(int x) { return !(~(x + 1) ^ x) & !!(x ^ ~0); }

收获:

  1. 用 !(x ^ y) 判断 x == y, 相对地, 用 !!(x ^ y) 判断 x != y
  2. 判断某些特殊值可以考虑通过特殊值进行某些运算(\(+1\), \(-1\) 等)后的特殊性, 但是要注意满足这个特殊性的不一定就是这个特殊值
  3. ~0 表示全 1 的位模式, 记住这个 ~0, 后面还会用到的

0x4 allOddBits

如果 \(x\) 的全部编号为奇数的位都是 1, 返回 \(1\), 否则返回 \(0\)

这个通过上一题的特殊运算很难大规模改变很多位以形成特殊值,

但是要求本身具有特定的模式1*1*1*1*1*1*1*, 所以是掩码发挥长处的地方

构造一个掩码 mask = 1010 1010 1010 1010 1010 1010 1010 1010 来表示要判断的模式

但这里其实还剩一个点: 偶数位是不做要求的, & 与 1 运算不改变但是与 0 运算改变原值, 所以应该用 |, 与 0 运算不改变原值但是与 1 运算改变原值 (不进位加法). 所以如果 x 的奇数位上都是 1, (x | mask) 将不会改变任何位, 根据上一题的收获 !(x ^ y) 判断是否相等, 就得到了解决方案

1
2
3
4
5
6
7
8
int allOddBits(int x) {
    int mask = 0xAA;
    // 1010 1010
    mask |= (mask << 8);
    // 1010 1010 1010 1010
    mask |= (mask << 16);
    return !((x | mask) ^ x);
}

收获:

  1. 根据运算符的特性, 使用特定运算符
  2. 掩码的构造与应用 但是对字面量的 < 256 限制又导致掩码在后面的题没什么优势区间了 所以这个 lab 经常左右脑互搏, 感觉是助教出的

0x5 negate

取负数, 最简单的一个 让我想起了我还是选手时写快读的快速(乐)时光

可以写 ~x + 1 (补码等于反码加一) 也可以写 ~(x - 1), 我当时的快读板子都是后者

简单证明: 令 y = x + 1, ~(x - 1) + 1= ~y + 1 = -y = -(x - 1) = -x + 1

不过我觉得对于极端值可能会有溢出的问题, 还是随手写前者了

1
int negate(int x) { return ~x + 1; }

收获: 没有 一个很绝妙而且这里空白很大写的下的证明 -x = ~x + 1, 这个后面很有用

0x6 isAsciiDigit

判断是否为 ASCII 数字 \(0 \sim 9\), 也就是 0x30 到 0x39

写出对应二进制, 发现高两位都是 1, 初步判断 x >> 4 是否等于 \((11)_2 = 3_{10}\)

剩下四位是 0000, 0001, .., 0111 或 1000, 1001.

首先 !((x >> 3) & 1) 通过右移提取第三位并判断是否为 0, 这样 0000, .., 0111 都匹配上了

然后对于 1 为最高位的后四位, 也就有 1000 和 1001, 只需要判断中间两位全为 0 即可, 也就是中间两位不全为 1, (x & 0b0110) 意味着中间两位全为 1, not 一下就是不全为 1

1
2
3
4
5
6
7
int isAsciiDigit(int x) {
    int zero = 0x30; // 0b 110000
    int nine = 0x39; // 0b 111001
                     // 0b 11****
                     //      0110
    return (!((x >> 4) ^ 3)) & (!((x >> 3) & 1) | !(x & 6));
}

收获:

  1. 右移 \(n\) 位并与 \(1\) (...0001) 运算提取并判断第 \(n\) 位
  2. 遇到判断范围的, 观察位模式进行匹配就行了, 难度不大

0x7 conditional

用位运算实现条件判断, 根据 \(x\) 的真假条件返回 \(y\) 或 \(z\)

根据 “非 \(0\) 为真” 的原则, 为 \(1, 2, 3, 4, ...\) 等任意非 \(0\) 的数都应该算作真, 我们先 !!x, 把不规则的真值统一为全一的位模式 (当然如果 x == 0 那就不会变)

然后就是经典的 (cond & if_statement) | (~cond & else_statement)

1
2
3
4
5
int conditional(int x, int y, int z) {
    int xp = ~(!!x + ~0); // =0000 if x=0000; =1111 if x has 1;
                          // replace `-1` with `+ ~0`
    return (y & xp) | (z & ~xp);
}

收获: 这两个无论是 lab 里还是实际应用中都挺重要的。

  1. 两次 ! 统一不规则值
  2. (cond & if_statement) | (~cond & else_statement)

0x8 isLessOrEqual

从这里开始整数部分的运算就开始逐渐有一些坑了, 9 和 10 更是开始上难度

首先抛开特殊情况之外考虑还是很简单的, 用 x + ~y + 1 表示 x - y, 判断这个值小于等于 \(0\) 即可, 也就是要么是 \(0\) 要么符号位为 1

然后跑了一遍没过, 试了几个值才想起来 \(x, y\) 符号位可能相反导致计算溢出, 这个时候直接提取符号位然后用上面的位级条件语句特判一下就行了

1
2
3
4
5
6
7
int isLessOrEqual(int x, int y) {
    int signx = !!(x & (1 << 31));
    int signy = !!(y & (1 << 31));
    int diff = (signx ^ signy);
    int d = x + ~y + 1;
    return (diff & (signx & !signy)) | (~diff & (!!(d & (1 << 31)) | !d));
}

收获:

  1. 要考虑多种情况, 尤其是可能导致溢出的情况
  2. 草

0x9 logicalNeg

实现逻辑 NOT, 当然出题人没那么好忽悠, 这题特殊把 ! 禁用了

NOT 也是一个把不规则值统一的运算, 我选择的是先 lowbit 操作获取最低位 (lowbit 是一个比较常见的操作, 我第一次接触是在学树状数组的时候), 此时如果原值是 \(0\) 那么 lowbit 就是 \(0\), 否则就是 ...0001000..., (特别地, 对于 \(\text{Tmin}\), lowbit 为 10000..., 对于 \(1\), lowbit 为 ...00001).

但这样还不够统一, 我们最后要统一归类到 \(0\) 和 \(1\) (NOT 只会返回 \(0\) 或 \(1\)). 注意到非 \(0\) 值的 lowbit 除了 \(\text{Tmin}\) 以外都是$ $ 的正数, 考虑 \(-1\) 运算, 使得正数 lowbit 变为 $ $ 的非负整数, 特殊值 \(\text{Tmin}\) 在大多数环境下也会环绕到正数 \(\text{Tmax}\) (注意这里还是一个 UB!), 但若 lowbit 为 \(0\), \(-1\) 后就会变成负数, 此时检查符号位再转换一下即可.

不过想到这还有一个问题, 就是这个右移是分算术右移和逻辑右移的, 逻辑右移不考虑计算, 高位直接补 0, 而算术右移是对于正数高位补 0, 对于负数高位补 1. (由于 C 规定 >> 是算术右移) 所以 ((lowbit + ~0) >> 31) 的可能值为 \(0\) 或 \(-1\), 后面的你就应该能够看得懂了.

1
2
3
4
5
int logicalNeg(int x) {
    int lowbit = x & (~x + 1); // 0 if x = 0; 001000 if x = 001***
    int xp = ((lowbit + ~0) >> 31) + 1;
    return ~xp + 1 + 1;
}
  1. \(\text{lowbit}(x)\) 的应用
  2. 一些统一不规则数的技巧 (感觉也可以算把相对连续的东西离散化)
  3. 看到右移一定要反应过来算术右移是高位补 1 的

0xA howManyBits

个人认为是最难的一个, 比后面浮点数什么的难多了

判断 \(x\) 在用补码表示的情况下最少需要几位

根据补码的规则不难看出答案是 \((\log_2(\text{highbit}(x)) + 1) + 1,\) 特别地, 对于 \(x = 0\) 或 $ x = -1$, 答案是 \(1\).

其中 \(\text{highbit}(x)\) 是与 \(\text{lowbit}(x)\) 相对的最高位的 1 所表示的数值, \(\log_2(\text{highbit}(x) + 1)\) 则是这个为 1 的位加上后面的 0 总共的位数(编号 \(+ 1\)), 而再 \(+1\) 是符号位.

  • 对于 \(x = 0\) 不成立是因为 \(x = 0\) 不需要符号位, 还记得吗, 补码的 \(0\) 是唯一的, 只有全 0 为 \(0\)
  • 对于 \(x = -1\) 不成立是因为单一个 1 会被认为是符号位, 计算为 \(-1\). 因此与之对应地, 比较难绷的是, \(1\) 却需要至少两位补码才能表示 (符合公式, 故不特殊列出)

那么难点主要有两个:

  1. 如何计算 \(\text{highbit}(x)\)? (事实上, 我认为 \(\text{lowbit}(x)\) 的 x & -x 也很传奇了)
  2. 如何计算 \(log_2(x)\)? 当然这里说的是只用位运算

\(\text{hightbit}(x)\) 也算一个不规则数统一的操作, 规整化后就可以通过 \(+1\) 来消除连续的 1 了, 那么就要考虑如何把最高位的 1 后面全填为 1, 我一开始的做法里, 对 \(\text{highbit}(x)\) 采用了一个小巧思, 通过每次 OR 上一个 \(2\) 的幂次个 1, 把最高位 1 以后的位都填为 1, 前面的位还是 0 不变, 现在就是 ...0000111111.. 了, 再 \(+1\) 并右移一位就是 \(\text{hightbit}(x)\) 也就是 \(...000010000...\) 了, 代码如下:

1
2
3
4
5
6
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x = (x + 1) >> 1;

算 \(log_2(x)\) 我则采用直接构建. 注意到我们已有的是一个只有一位为 1 的二进制数, 而我们要得到一这个 1 所在位的编号——一个应该理解为十进制的数, 通过位运算我们只能通过二进制来构造这个十进制数.

于是依次构建每一位, 先从最后一位开始考虑: 如果最后这一位是 1, 那么编号一定是奇数, 于是突然想起之前那个 allOddBits 的题, 用掩码做, 此时我内心的感觉就像突然和出题人心意相通, 于是很快通过找规律得到每一位对应的掩码

1
2
3
4
5
r |= !!(x & 0xAAAAAAAA) << 0; // r odd; 1010
r |= !!(x & 0xCCCCCCCC) << 1; // r = 2/3, 6/7, 10/11; 1100
r |= !!(x & 0xF0F0F0F0) << 2; // r = 4/5/6/7; 1111_0000
r |= !!(x & 0xFF00FF00) << 3; // r = 8~15; 1111_1111_0000_0000
r |= !!(x & 0xFFFF0000) << 4; // pattern

\(r + 1\) 则为最终的结果. 不过 当 \(x = -1\) 或 \(x = 0\) 时是不能 \(+1\) 的, 顺手的事: return r + (!!(x ^ 0) & !!(x ^ ~0));

结果 ./driver.pl 后我以为整数部分就结束了, 结果发现没过, 这时才想起来禁用大常量, 0xFFFF0000 这些肯定是超过 0xFF 了 (写到这突然觉得这个掩码或许可以通过一个小一点的常量移位构造出来, 因为 AllOddBits 实际上也是通过移位构造的掩码, 但之前做的时候并没有想到)

于是我便只好考虑其他方案.

我甚至考虑了写 32 行语句挨个判断每一位, 从高到低找第一个 1, 显然这样是不行的, 没那么多运算符给我用.

从高到低的思路应该是没问题的, 那么想要减少查找的数量, 就想到了二分查找. 虽然不能使用循环, 但是对于 \(32\) 位 (\(32\) 个元素) 的二分查找其实只有 \(\log_2(32) = 5\) 次 (左右), 完全可以手写出来. 这何尝不是一种循环展开

确定好二分查找, 简单梳理一下查找逻辑:

  1. 从高到低, 高 \(16\) 位有 1 吗?
  2. 如果有就继续检查这高 \(16\) 位的高 \(8\) 位, 同时结果加上 \(16\), 因为编号必然大于 \(16\) 了 (低 \(16\) 位编号是 \(15 \sim 0\)), 然后继续在这高 \(16\) 位里面继续找 (注意我们要找的是且仅是最高位 1)
  3. 否则就找这 \(16\) 位之后的 \(8\) 位有没有 \(1\)
  4. 就这样不停迭代下去

判断是高 \(p\) 位是否有 1: !!(y >> p), 这里使用到了之前的两次 NOT 转换成纯粹 \(0/1\) 的技巧

为了保持运算的统一性(减少运算符数量防止撞上限制), 使用 !!(y >> p) >> 4 表示是否乘上 \(16\) (如果高 \(16\) 位没有 1 则乘上 \(0 \times 2^4 = 0\))

同时 “然后继续在这高 \(16\) 位里面继续找” 和”找这 \(16\) 位之后的 \(8\) 位有没有 \(1\)” 在我们的情况下也不便条件判断, 也是采用移动的方式, 如果高 \(16\) 位有 1 就右移丢弃低 \(16\) 位, 没有的话就不右移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
r += !!(y >> 16) << 4;
y >>= r;

shift8 = !!(y >> 8) << 3;
r += shift8;
y >>= shift8;

shift4 = !!(y >> 4) << 2;
r += shift4;
y >>= shift4;

shift2 = !!(y >> 2) << 1;
r += shift2;
y >>= shift2;

r += (y >> 1) + 1;	// 到这里时只剩下最后两位, 即 0/1/2/3

这段代码实际上是计算 \((\log_2(\text{highbit}(x)) + 1)\), 把两个活一起干了, 后面的逻辑是相同的.

帅吗? 还是没过.

\(x\) 可能是负数, 对于负数要找绝对值所对应的正数, 对于正数则不变, 写一个比较帅的无分支:

1
2
int sign = x >> 31;
int y = x ^ sign;

反正不限制局部变量数量 cache lab 就开始限制局部变量数量了, 满足你

这里统一处理逻辑的话其实有点麻烦, 我直接近似 ~x 了(x ^ sign), 这是错的, 但是这个神人评测没查出来, 我就懒得改了 (写 (x ^ sign) + !!sign 结果会错, 因为补码的正负值域不对称性导致对 \(\text{Tmin}\) 取绝对值会溢出, 见 CSAPP3e第二章(整数的表示) | Amiriox’s Storage, 是个比较典型的问题)

呃, 总体上就是实现了一个 C++20 的 std::bit_width. 不得不感叹一下刚学的时候说起 C++20 都感觉很新潮很先进, 现在还是觉得很先进, 现在 C++23 都是过去式了, 我也再也没有青春的挡箭牌, 终归是走进了大学生活。

事到如今只好祭奠嗎

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int howManyBits(int x) {
    // The prohibition of using large constants is
    // the most disgusting thing about this disgusting lab.
    // It forced me to abandon the more elegant masking method
    // and use binary division like enumeration.

    /* shit, i almost forgot macros are also banned.
#ifdef ENABLE_LARGE_CONSTANTS
    // int lowbit = x & (~x + 1);
    // replace lowbit with highbit
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x = (x + 1) >> 1;
    int r = 0;
    r |= !!(x & 0xAAAAAAAA) << 0; // r odd; 1010
    r |= !!(x & 0xCCCCCCCC) << 1; // r = 2/3, 6/7, 10/11; 1100
    r |= !!(x & 0xF0F0F0F0) << 2; // r = 4/5/6/7; 1111_0000
    r |= !!(x & 0xFF00FF00) << 3; // r = 8~15; 1111_1111_0000_0000
    r |= !!(x & 0xFFFF0000) << 4; // pattern
    return r + (!!(x ^ 0) & !!(x ^ ~0));
#endif
    */
    int sign = x >> 31;
    int y = x ^ sign;
    int r = 0;
    int shift2 = 0, shift4 = 0, shift8 = 0;

    r += !!(y >> 16) << 4;
    y >>= r;

    shift8 = !!(y >> 8) << 3;
    r += shift8;
    y >>= shift8;

    shift4 = !!(y >> 4) << 2;
    r += shift4;
    y >>= shift4;

    shift2 = !!(y >> 2) << 1;
    r += shift2;
    y >>= shift2;

    r += (y >> 1) + 1;

    return r + (!!(x ^ 0) & !!(x ^ ~0));
}

收获:

  1. 倍增填 1 获取 highbit
  2. 掩码计算 highbit 的编号
  3. 二分查找实现 std::bit_width

0xB floatScale2

我突然想起来我完全忘记写 IEEE 754 浮点数相关的博客了, 而这恰好是 CSAPP 第二章最有价值的一块

简单说下 IEEE 754,

对于阶码不全为 0 也不全为 1 的规格化数:

  • \(f = 1^\text{sign} \times \text{M} \times 2^\text{E}\)
  • \(\text{M}\) 表示 \(\text{1.frac}\) (对于大多数数可以额外多表示一位, 多一位的精度)
  • \(\text{E}\) 表示 \(e - \text{Bias}\), 其中 \(e\) 为阶码 \(\text{exp}\) 的原码, \(\text{Bias} = 2^{k-1} -1\), \(k\) 为阶码 \(\text{exp}\) 的位数 (这里之所以采用偏移表示负数而不使用补码是因为易于比较, 而浮点数的比较操作可能很多)

对于阶码全为 0 的非规格化数:

  • \(f = 1^\text{sign} \times \text{M} \times 2^\text{E}\)
  • \(M\) 表示 \(\text{0.frac}\)
  • \(\text{E}\) 表示 \(1 - Bias\), 其中 \(e\) 为阶码 \(\text{exp}\) 的原码, \(\text{Bias} = 2^{k-1} -1\), \(k\) 为阶码 \(\text{exp}\) 的位数 (这里之所以采用 \(1 - \text{Bias}\) 而不是 \(0 - \text{Bias}\), 是因为最小的规格化数的阶码就是当 \(e = 1\) 时的 \(1 - \text{Bias}\), 以此保证了规格化数与非规格化数之间的连续性)

对于阶码全为 1 的特殊值:

  • 如果 \(\text{frac}\) 全为 0, 则为无穷大 (说明是计算溢出来的)
  • 如果 \(\text{frac}\) 不全为 0, 则为 \(\text{NaN}\) (不瞒你说, 我现去搜了一下 Not a number 用 \(\LaTeX\) 怎么打, 但是没有)

舍入什么的有时间再补吧, 先看题

则对于本题, 本题是什么来着, \(\text{uf} \times 2\) 还是比较好写的, 先提取三个段然后处理:

  1. 如果是 \(-0\) (很遗憾, IEEE 754 的 \(0\) 有两个表示, 因为除 \(0\) 可得正负无穷), 直接返回
  2. 如果是无穷大或者 \(\text{NaN}\), 直接返回
  3. 如果是阶码全 0, 且较小(不涉及乘 \(2\) 后变成规格化数)的非规格化数, 直接对 \(\text{frac}\) 乘 \(2\). 注意此时就不能对阶码 \(+1\)
  4. 如果是阶码全 0, 较大的非规格化数, 除了 \(\text{frac} \times 2\), 阶码还是要 \(+1\)
  5. 如果是规格化数, 阶码 \(+ 1\) 即可
  6. 最后再拼好数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
unsigned floatScale2(unsigned uf) {
    //   1 | 8 | 23
    // sign exp frac
    unsigned sign = (uf >> 31);
    unsigned exp = (uf << 1) >> (24);
    unsigned frac = (uf << 9) >> 9;
    unsigned dt = 1;
    if (!(uf << 1))
        return uf;
    if (exp == 0xFF) /*if(!frac)*/
        return uf;
    if (!exp) {
        if (!(frac >> 22)) {
            dt--;
        }
        frac <<= 1;
    }
    return (sign << 31) | ((exp + dt) << 23) | frac;
}

0xC floatFloat2Int

float 转换为 int. 回顾转换规则, float 转换到 int 不仅会向零舍入, 还可能会溢出, 所以要考虑溢出的情况

仍然是三段提取, 开始计算:

  1. 计算一下应该乘的权重 \(e - \text{Bias}\) (如果 \(e \lt \text{Bias}\), 说明是小于 \(1\) 的浮点数, 直接返回 \(0\))
  2. 补上规格化数 \(\text{frac}\) 缺省的小数点前的 \(1\), 此时小数点相当于位于最高位 1 前, 需要准备恢复出本身带有的权重(右移 \(23\) 位), 以及乘权重 \(E\). (\(\text{frac}\) 表示小数点后 \(2\) 的负整数次幂的数值, 直接乘 \(2\) 的正整数次幂提升权重是兼容的)
  3. 按照 \(\text{Tmax}\) 的值注意一下可能会溢出的情况. 实际上这行 ((E >= 31 && (!sign || (sign && frac))) || exp == 0xFF) 是主要的难点
  4. 如果先右移移动 \(23\) 位可能会丢精度, 所以这里考虑和 \(E\) 计算差值转移.
  5. 最后根据符号位转一下符号. 由于允许了 if else, 我懒得写无分支了
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
28
29
int floatFloat2Int(unsigned uf) {
    //   1 | 8 | 23
    // sign exp frac
    unsigned sign = (uf >> 31);
    unsigned exp = (uf << 1) >> (24);
    unsigned frac = (uf << 9) >> 9;
    unsigned E = 0, A = 0;
    if (!(uf << 1) || /*!exp*/ exp < 0x7f)
        return 0;

    E = exp - 0x7f;
    A = (1U << 23) | frac;
    // check overflow
    // INT_MAX = T32Max = 0b_0111_1111_1111_1111_1111_1111_1111_1111
    if ((E >= 31 && (!sign || (sign && frac))) || exp == 0xFF) {
        return 0x80000000u;
    }
    if (E >= 23) {
        A <<= (E - 23);
    } else {
        A >>= (23 - E);
    }

    if (sign) {
        return ~A + 1;
    } else {
        return A;
    }
}

0xD floatPower2

构造 \(2.0 ^ {x}\) 的 \(32\) 位 IEEE 754 浮点数

主要考察对非规格数, 规格数的值域以及其连续性

\(\text{exp}\) 是 8 位无符号整型, 分类讨论一下

  • 0b11111111 $ = 2^8 - 1$, 说明浮点数是 \(\infty /\text{NaN}\)
  • 0b11111110 \(= 2^8-2 = 254\)
  • \(\text{U8Min} = 0\), 是非规格化数; 对于规格数, 最小的阶码就是1
  • 规格化数可表示的 \(2^x\), \(x = {e - 127}\), 取值范围: \([-126, 127]\) 连续 (保持 M 为 0.0, 即 1.0)
  • 非规格化数: \(x < 0\), 算入阶码权重计算出来是这样的: \(2^{-1-126}+2^{-2-126}+2^{-3-126}+...+2^{-23-126}\), 取值范围 \([-149, -127]\)

得出值域后分别构造 IEEE 754 标准浮点数处理就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
unsigned floatPower2(int x) {
    unsigned exp = 0, s = 0;

    if (x > 127) {
        return 0x7f800000; //(0xFF << 23);
    } else if (x >= -126 && x <= 127) {
        exp = (127 + x);
        return (exp << 23);
    } else if (x >= -149 && x < -126) {
        s = 149 + x;
        return (1U << s);
    }
    return 0;
}

Summary

我个人对这个 Lab 的评价不是很高, 感觉不是很有意思

但是确实对于数的表示上有很大的作用, 就是枯燥了些