type
date
slug
summary
status
tags
category
password
Last edited time
Apr 25, 2025 10:10 AM
icon
简介
系WHU2021级《系统级程序设计》实验1，节选于CSAPP Lab。
任务介绍
在本实验中，需要实现15个待补充的原型函数，一共分为三种类型：
函数内的操作数越少、分数越高； 若全部函数的操作数都少于“基准操作数”，则成功达成“Winner”称号🥇
- 表 1 位运算
ID | 函数名称 | 功能描述 | 难度等级 | 最大操作数 | 基准操作数 |
1 | bitNor(x, y) | 只用 ~和& 实现 ~(x|y) | 1 | 8 | 3 |
2 | copyLSB(x) | 将x的所有位都设置为它的最低位的值 | 2 | 5 | 2 |
3 | isEqual(x, y) | x==y返回1，否则返回0 | 2 | 5 | 2 |
4 | bitMask(highbit, lowbit) | 生成一个掩码，lowbit位至highbit位均为1 | 3 | 16 | 8 |
5 | bitCount(int x) | 计算x中1的数目 | 4 | 40 | 25 |
- 表 2 二进制补码运算
ID | 函数名称 | 功能描述 | 难度等级 | 最大操作数 | 基准操作数 |
6 | tmax() | 返回最大的补码 | 1 | 4 | 2 |
7 | isNonNegative(x) | 如果x>=0，返回1，否则返回0 | 3 | 6 | 3 |
8 | addOK(x, y) | 确定x+y是否不溢出 | 3 | 20 | 9 |
9 | rempwr2(x, n) | 计算x%(2^n) | 3 | 20 | 11 |
10 | isLess(x, y) | 如果x<y，返回1，否则返回0 | 3 | 24 | 12 |
11 | absVal(x) | x的绝对值 | 4 | 10 | 5 |
12 | isPower2(x) | 如果x是2的幂，返回1，否则返回0 | 4 | 20 | 11 |
- 表 3 浮点数运算
ID | 函数名称 | 功能描述 | 难度等级 | 最大操作数 | 基准操作数 |
13 | float_neg(uf) | 计算-f | 2 | 10 | 5 |
14 | float_half(uf) | 返回0.5*f的位级表示 | 4 | 30 | 19 |
15 | float_i2f(x) | 返回(float)x的位级表示 | 4 | 30 | 27 |
文件介绍
bits.c文件： 源码文件，里面包含了 15 个待实现的函数原型。
dlc：- 查看文件中的代码是否符合要求，命令为
./dlc bits.c - 查看使用的运算符数量，命令为
./dlc -e bits.c
btest：用于检测程序得分- 编译，命令为：
make dtest - 重新编译，命令为：
make clean，make dtest - 执行
- 全部执行，命令为：
./dtest - 执行指定函数，命令为
./dtest -f func - 查看帮助，命令为：
./dtest -h
自动评测
执行命令：
./driver.pl -u "学号"注意事项
bits.c中的说明
- 文件建议保存在工作目录
/mnt/cgshare下，该目录不会随着容器的销毁而更改
- 运行dlc时，可能会出现如下warning，忽略即可：
实验记录
1. bitNor
使用
~和&实现~(x|y)- 示例：
bitNor(0x6, 0x5) = 0xFFFFFFF8
- 可用操作：
~ &
- 最大操作数：8
- 难度：1
代码
2. copyLSB
将x的所有位都设置为它的最低位的值
- 示例：
copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
- 可用操作：
! ~ & ^ | + << >>
- 最大操作数：5
- 难度：2
代码
3. isEqual
x==y返回1，否则返回0
- 示例：
isEqual(5,5) = 1, isEqual(4,5) = 0
- 可用操作：
! ~ & ^ | + << >>
- 最大操作数：5
- 难度：2
代码
4. bitmask
产生一个在[lowbit, highbit]区间内均为1的掩码
- 说明：0 <= lowbit <= 31，0 <= highbit <= 31；若lowbit>highbit，则返回0
- 示例：
bitMask(5,3) = 0x38
- 可用操作：
! ~ & ^ | + << >>
- 最大操作数：16
- 难度：3
代码
注意左移的溢出问题：（以4bytes的int类型为例）
1<<31 ⇒ 0xffffffff
1<<32 ⇒ 0x1
1<<31<<1 ⇒ 0x05. bitCount
计算x中1的数目
- 示例：
bitCount(5) = 2, bitCount(7) = 3
- 可用操作：
! ~ & ^ | + << >>
- 最大操作数：40
- 难度：4
分组逐步进行：
每2位为一组，则直接将前后两位相加，可得到每组的1的个数；
每4位为一组，将前后两个2位相加，可得到每组的1的个数；
以此类推。
代码
6. tmax
返回最大的补码
- 可用操作：
! ~ & ^ | + << >>
- 最大操作数：4
- 难度：1
代码
7. isNonNegative
如果x>=0，返回1，否则返回0
- 示例：
isNonNegative(-1) = 0. isNonNegative(0) = 1
- 可用操作：
! ~ & ^ | + << >>
- 最大操作数：6
- 难度：3
代码
8. addOK
确定x+y是否不溢出
- 示例：
addOK(0x80000000,0x80000000) = 0, addOK(0x80000000,0x70000000) = 1
- 可用操作：
! ~ & ^ | + << >>
- 最大操作数：20
- 难度：3
先判断x和y是否异号，若异号则必不溢出；
再判断x+y的符号与x的符号是否相同，不同则溢出；
代码
9. rempwr2
计算
x%(2^n)- 示例：
rempwr2(15,2) = 3, rempwr2(-35,3) = -3
- 可用操作：
! ~ & ^ | + << >>
- 最大操作数：20
- 难度：3
先保留符号，若x为负数则转正，提取[n-1,0]位，最后再将正负转换回来；
代码
10. isLess
x<y返回1，否则返回0
- 示例：
isLess(4,5) = 1
- 可用操作：
! ~ & ^ | + << >>
- 最大操作数：24
- 难度：3
代码
11. asbVal
x的绝对值
- 示例：
absVal(-1) = 1
- 可用操作：
! ~ & ^ | + << >>
- 最大操作数：10
- 难度：4
代码
12. isPower2
判断是否为2的幂
- 示例：
isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
- 可用操作：
! ~ & ^ | + << >>
- 最大操作数：20
- 难度：4
代码
13. float_neg
计算
-f- 说明：参数与返回值都是无符号整数；当
f=NaN，返回参数本身
- 示例：
isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
- 可用操作：所有整数相关操作，
||, &&, if, while
- 最大操作数：10
- 难度：2
代码
14. float_half
0.5*f的位级表示- 说明：参数与返回值都是无符号整数；当
f=NaN，返回参数本身
- 示例：
isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
- 可用操作：所有整数相关操作，
||, &&, if, while
- 最大操作数：30
- 难度：4
代码
❌错误代码
frac_+=0x2时可能发生进位，这个进位本应该因溢出而舍去.15. float_i2f
(float)x的位级表示- 说明：返回值是无符号整数，是浮点数的位级表示；
- 示例：
isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
- 可用操作：所有整数相关操作，
||, &&, if, while
- 最大操作数：30
- 难度：4
代码
更可读但更笨的方法
网上cpoy的贼快代码
- 作者:Antony_Zhang
- 链接:https://antonyzhang.cn/article/csapp-datalab
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。