type
status
date
slug
summary
tags
category
icon
password
终于入坑了CSAPP的lab
A thousand-mile journey begins with the first step.(千里之行始于足下)
Let's start！
Data lab内容
用一个非常有限的C语言子集实现简单的逻辑和算术运算函数
函数名 | 功能实现 | 要求 |
bitXor(x,y) | x ^ y | 最大操作数14，只能用 ~ 和 & 运算符，返回结果 |
tmin() | 最小的整数补码 | 最大操作数4，！~ & ^ | + << >> |
isTmax(x) | 如果 x 是二进制补码最大值，则返回 1，否则返回 0 | 最大操作数10，只能用！~ & ^ | + |
allOddBits(x) | x 的奇数位都为 1 时为真，最左侧为第31位，最右侧为第0位 | 最大操作数12，！~ & ^ | + << >> |
negate(x) | 使用操作符返回 -x | 最大操作数5，! ~ & ^ | + << >> |
isAsciDigit(x) | 0x30⩽x⩽0x39 时为真 | 最大操作符15，! ~ & ^ | + << >> |
conditional | 等同于 x ? y : z | 最大操作符16，! ~ & ^ | << >> |
isLessOrEqual(x, y) | x⩽y时为真，否则为假 | 最大操作符24，! ~ & ^ | << >> |
logicalNeg(x)) | 计算 !x | 最大操作数12，不用 ! 运算符 |
howManyBits(x) | 表示x的二进制补码的最小位数 | 最大操作符90，! ~ & ^ | + << >> |
floatScale2(uf) | 计算 2 * uf，若 uf 为特殊值值时，直接返回 uf | 最大操作符30，Integer/unsigned 相关运算；||，&&，if 和 while 等判断语句 |
floatFloat2Int(uf) | 将浮点数 uf 转换成整数 | 最大操作符30，Integer/unsigned 相关运算；||，&&，if 和 while 等判断语句 |
floatPower2(x) | 使用浮点数表示 2x。无法表示时：过小返回 0，过大返回 +INF | 最大操作符30，Integer/unsigned 相关运算；||，&&，if 和 while 等判断语句 |
Data lab过程
int
1.bitXor
用按位与 & 和按位取反 ~ 实现按位异或 ^
先解释一波：
- &：当两个操作数的对应位都是1时，结果位为1，否则为0
- ~：相当于求该整数的补码
- ^：当两个操作数对应位不同时，结果位为1，否则为0
先用的二进制数据去凑，正数凑出来满足~ ( ~ x & ~ y)
但是用负数验证又不对，想了一下使用真值表法进行操作
x | y | ~x | ~y | x & y | ~x & ~y | ~ (x & y) | ~ (~x & ~y) | ~ (x & y) & ~ (~x & ~y) | 目标结果x ^ y |
0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
验证：
2.tmin
返回最小的二进制补码
补码最小值，C语言中int类型数据是4字节32位，相当于第32位为1，其余位为0
3.isTmax
如果 x 是二进制补码最大值，则返回 1，否则返回 0
以C语言int类型思考，最大值为：
由于不能进行移位操作，所以简化为取头四位和末四位也不影响：
想到最小值和最大值是挨着的，操作就从它两来思考
- !：逻辑非，用于将一个布尔表达式的值取反
- |：按位或，用于对两个整数的每一位进行或操作，如果两个对应位中至少有一个是1，则结果位为1；否则，结果位为0
使用#include <limits.h>来调用min
检查发现(这里才注意到可以用指令去验证)
限制了字符，不能直接定义INT_MIN
重新思考：
4.allOddBits
如果所有的奇数位都为1则返回1，最左侧为第31位，最右侧为第0位
同样输入(only 0x0 - 0xff allowed)
5.negate
返回相反数
emm，不就是求补码，秒了
6.isAsciiDigit
判断ascii码是否在0到9之间
若x - 0x39为负数的话，说明小于等于0x39内；若0x30 - x为负数的话，说明大于等于0x30
然后都满足则返回1
想到上面求negate相反数，把求-x转化为求 ~x + 1
7.conditional
等价于 x ? y : z
解释：
- 若x为真，则返回y，否则返回z
结果检查发现不能用if
重新想：
8.isLessOrEqual
又是解决比较大小，参考isAsciiDigit
9.logicalNeg
不用 ! 解决 !x1
可以发现，~x + 1后的数据，非0的第0位是1，0的第0位是0
据此做文章：
10.howManyBits
表示x的二进制补码的最小位数
逐渐缩小范围来判断'1'
float
32bit的float变量(IEEE 754标准)
例如：5.25 => 0101.01 => 1.0101 * 22
- 符号位：正数为0，负数为1
- 指数位(又叫阶码)：就像例如中的指数2，再加上127，然后转为二进制
- 尾数部分：例如中的小数部分，后面补0占满23位
有特殊的1：例如：5.20 => 0101. 0011 0011 0011...(无限循环) => 1.01 0011 0011 0011…… * 22
这种情况下，尾数部分无限循环，只取23位(这就是float的精度体现)
有特殊的2：上述例子都是规格化float，还存在非规格化float
- 两者的区别在于阶码的值以及尾数的表示方式。规格化数的
阶码非零且隐含1，而非规格化数的阶码为零且无隐含1
- 规格化浮点数 用于表示绝大多数浮点数，具有较高的精度
非规格化浮点数 用于表示非常小的数，精度较低，但能表示的范围更广
有特殊的3：无穷大，符号位：正无穷大为
0，负无穷大为1；阶码：全部为1，即11111111；尾数：全部为0有特殊的4：NaN(非数值)，用于表示未定义或无法表示的数值，如无效操作的结果。符号位无意义，阶码全为
1，尾数至少有一个111.floatScale2
将传来的参数当成float的位级表示，返回浮点数乘2的位级表示，如果是NAN(非数值)和极大值(阶码全部为1)则返回本身
对于常规化float，乘2只需要将阶码+1，其它位保持不变
对于非常规化float，乘2需要左移1位
12.floatFloat2Int
将浮点型转换为位级等价整数
NaN和无穷大返回0x80000000
解释一下为什么是150分别较大较小数据：
- 尾数有23位，即它能表示的最小单位是 223
- 如果
e - 127 = 23，这意味着浮点数的整数部分会刚好扩展到第23 + 1位（1 是隐含位）。也就是说，所有位都用来表示整数部分
- 如果e >= 150的话，尾部所有位都用来表示了整数，只需要左移(e - 150)即可表示位级等价整数
- 如果e < 150，尾部不是所有位都用来表示整数，表示整数的部分靠左，右移(150 - e)即可
13.floatPower2
得到
2.0^x 的准确浮点数位级表示无法表示时：过小返回 0，过大返回 +INF(正无穷大)
想到x为指数，就与阶码相关
Data lab end!!!
- 作者:Sh4d0w
- 链接:https://sh4d0w.life//article/c9c82ad6-b1ba-4846-be70-772a399e97df
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。