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
中的说明
/* * Instructions to Students: * * STEP 1: Read the following instructions carefully. */ You will provide your solution to the Data Lab by editing the collection of functions in this source file. INTEGER CODING RULES: Replace the "return" statement in each function with one or more lines of C code that implements the function. Your code must conform to the following style: int Funct(arg1, arg2, ...) { /* brief description of how your implementation works */ int var1 = Expr1; ... int varM = ExprM; varJ = ExprJ; ... varN = ExprN; return ExprR; } Each "Expr" is an expression using ONLY the following: 1. Integer constants 0 through 255 (0xFF), inclusive. You are not allowed to use big constants such as 0xffffffff. 2. Function arguments and local variables (no global variables). 3. Unary integer operations ! ~ 4. Binary integer operations & ^ | + << >> Some of the problems restrict the set of allowed operators even further. Each "Expr" may consist of multiple operators. You are not restricted to one operator per line. You are expressly forbidden to: 1. Use any control constructs such as if, do, while, for, switch, etc. 2. Define or use any macros. 3. Define any additional functions in this file. 4. Call any functions. 5. Use any other operations, such as &&, ||, -, or ?: 6. Use any form of casting. 7. Use any data type other than int. This implies that you cannot use arrays, structs, or unions. You may assume that your machine: 1. Uses 2s complement, 32-bit representations of integers. 2. Performs right shifts arithmetically. 3. Has unpredictable behavior when shifting an integer by more than the word size. EXAMPLES OF ACCEPTABLE CODING STYLE: /* * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31 */ int pow2plus1(int x) { /* exploit ability of shifts to compute powers of 2 */ return (1 << x) + 1; } /* * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31 */ int pow2plus4(int x) { /* exploit ability of shifts to compute powers of 2 */ int result = (1 << x); result += 4; return result; } FLOATING POINT CODING RULES For the problems that require you to implent floating-point operations, the coding rules are less strict. You are allowed to use looping and conditional control. You are allowed to use both ints and unsigneds. You can use arbitrary integer and unsigned constants. You are expressly forbidden to: 1. Define or use any macros. 2. Define any additional functions in this file. 3. Call any functions. 4. Use any form of casting. 5. Use any data type other than int or unsigned. This means that you cannot use arrays, structs, or unions. 6. Use any floating point data types, operations, or constants. NOTES: 1. Use the dlc (data lab checker) compiler (described in the handout) to check the legality of your solutions. 2. Each function has a maximum number of operators (! ~ & ^ | + << >>) that you are allowed to use for your implementation of the function. The max operator count is checked by dlc. Note that '=' is not counted; you may use as many of these as you want without penalty. 3. Use the btest test harness to check your functions for correctness. 4. Use the BDD checker to formally verify your functions 5. The maximum number of ops for each function is given in the header comment for each function. If there are any inconsistencies between the maximum ops in the writeup and in this file, consider this file the authoritative source. /* * STEP 2: Modify the following functions according the coding rules. * * IMPORTANT. TO AVOID GRADING SURPRISES: * 1. Use the dlc compiler to check that your solutions conform * to the coding rules. * 2. Use the BDD checker to formally verify that your solutions produce * the correct answers. */
- 文件建议保存在工作目录
/mnt/cgshare
下,该目录不会随着容器的销毁而更改
- 运行dlc时,可能会出现如下warning,忽略即可:
Non-includable file <command-line> included from includable file /usr/include/stdc-predef.h.
实验记录
1. bitNor
使用
~
和&
实现~(x|y)
- 示例:
bitNor(0x6, 0x5) = 0xFFFFFFF8
- 可用操作:
~ &
- 最大操作数:8
- 难度:1
代码
int bitNor(int x, int y) { return ~x & ~y; }
2. copyLSB
将x的所有位都设置为它的最低位的值
- 示例:
copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
- 可用操作:
! ~ & ^ | + << >>
- 最大操作数:5
- 难度:2
代码
int copyLSB(int x){ return x<<31>>31; }
3. isEqual
x==y返回1,否则返回0
- 示例:
isEqual(5,5) = 1, isEqual(4,5) = 0
- 可用操作:
! ~ & ^ | + << >>
- 最大操作数:5
- 难度:2
代码
int isEqual(int x, int y){ return !(x^y); }
4. bitmask
产生一个在[lowbit, highbit]区间内均为1的掩码
- 说明:0 <= lowbit <= 31,0 <= highbit <= 31;若lowbit>highbit,则返回0
- 示例:
bitMask(5,3) = 0x38
- 可用操作:
! ~ & ^ | + << >>
- 最大操作数:16
- 难度:3
代码
int bitMask(int highbit, int lowbit){ return (~0 << lowbit) & (~0 + (1 << highbit << 1)); }
注意左移的溢出问题:(以4bytes的int类型为例)
1<<31 ⇒ 0xffffffff
1<<32 ⇒ 0x1
1<<31<<1 ⇒ 0x0
5. bitCount
计算x中1的数目
- 示例:
bitCount(5) = 2, bitCount(7) = 3
- 可用操作:
! ~ & ^ | + << >>
- 最大操作数:40
- 难度:4
分组逐步进行:
每2位为一组,则直接将前后两位相加,可得到每组的1的个数;
每4位为一组,将前后两个2位相加,可得到每组的1的个数;
以此类推。
代码
int bitCount(int x) { // 计算x中1的数目 【30/25】 int mask1, mask2, mask4, mask8, mask16; // 转化为8bits一组 需要的掩码 mask4 = 0x0F | (0x0F << 8); // 0000 1111 0000 1111 mask4 |= mask4 << 16; // 0000 1111 0000 1111 0000 1111 0000 1111 // 转化为4bits一组 需要的掩码 mask2 = mask4 ^ (mask4 << 2); // 0011 0011 0011 0011 0011 0011 0011 0011 // 转化为2bits一组 需要的掩码 mask1 = mask2 ^ (mask2 << 1); // 0101 0101 0101 0101 0101 0101 0101 0101 // 转化为16bits一组 需要的掩码 mask8 = 0xFF | (0xFF << 16); // 0000 0000 1111 1111 0000 0000 1111 1111 // 转化为32bits一组 需要的掩码,得到最后的结果 mask16 = (~0) + (1<<16); // 0000 0000 0000 0000 1111 1111 1111 1111 x = (x & mask1) + ((x >> 1) & mask1); x = (x & mask2) + ((x >> 2) & mask2); x = (x + (x >> 4)) & mask4; x = (x + (x >> 8)) & mask8; x = (x + (x >> 16)) & mask16; return x; }
6. tmax
返回最大的补码
- 可用操作:
! ~ & ^ | + << >>
- 最大操作数:4
- 难度:1
代码
int tmax(void) { return ~(1<<31); }
7. isNonNegative
如果x>=0,返回1,否则返回0
- 示例:
isNonNegative(-1) = 0. isNonNegative(0) = 1
- 可用操作:
! ~ & ^ | + << >>
- 最大操作数:6
- 难度:3
代码
int isNonNegative(int x) { return !(x>>31); }
8. addOK
确定x+y是否不溢出
- 示例:
addOK(0x80000000,0x80000000) = 0, addOK(0x80000000,0x70000000) = 1
- 可用操作:
! ~ & ^ | + << >>
- 最大操作数:20
- 难度:3
先判断x和y是否异号,若异号则必不溢出;
再判断x+y的符号与x的符号是否相同,不同则溢出;
代码
int addOK(int x, int y) { int sign_x = x>>31; int sign_y = y>>31; return !!((sign_x ^ sign_y) | !(sign_x ^ (x+y)>>31)); }
9. rempwr2
计算
x%(2^n)
- 示例:
rempwr2(15,2) = 3, rempwr2(-35,3) = -3
- 可用操作:
! ~ & ^ | + << >>
- 最大操作数:20
- 难度:3
先保留符号,若x为负数则转正,提取[n-1,0]位,最后再将正负转换回来;
代码
int rempwr2(int x, int n) { int sign, sign_; sign = x>>31; sign_ = sign & 1; x = (sign ^ x) + sign_; x &= (~0 + (1<<n)); return (sign ^ x) + sign_; }
10. isLess
x<y返回1,否则返回0
- 示例:
isLess(4,5) = 1
- 可用操作:
! ~ & ^ | + << >>
- 最大操作数:24
- 难度:3
代码
int isLess(int x, int y) { // 【10/12】 int res1, same, sub, res2, _y; _y = ~y; // 若x负y正,则直接通过,a=1; res1 = (x&_y); // 若x正y负,则直接不通过,无需考虑; // 若x,y同号,则根据x-y符号判断 same = ~(x^y); //x,y是否同号 sub = x + (_y+1); // x-y res2 = (same & sub); return ((res1 | res2)>>31) & 1; }
11. asbVal
x的绝对值
- 示例:
absVal(-1) = 1
- 可用操作:
! ~ & ^ | + << >>
- 最大操作数:10
- 难度:4
代码
int absVal(int x) { return (x ^ (x>>31)) + (1 & (x>>31)); // 当x为正数,前者为本身,后者为0;当x为负数,前者为取反,后者为1 }
12. isPower2
判断是否为2的幂
- 示例:
isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
- 可用操作:
! ~ & ^ | + << >>
- 最大操作数:20
- 难度:4
代码
int isPower2(int x) { // 若x为2的幂,则x-1(即~0+x)的后面几位都是1,则r=0 int r = x & (~0+x); // 之后排除x为负数和0的情况 return (!r) & (!(x>>31) & !!x); }
13. float_neg
计算
-f
- 说明:参数与返回值都是无符号整数;当
f=NaN
,返回参数本身
- 示例:
isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
- 可用操作:所有整数相关操作,
||, &&, if, while
- 最大操作数:10
- 难度:2
代码
unsigned float_neg(unsigned uf) { // 若为NaN,直接返回参数 if((uf & 0x7fffffff) > 0x7f800000) // exp部分全为1,且frac部分不全为0 return uf; return uf ^ 0x80000000; }
14. float_half
0.5*f
的位级表示- 说明:参数与返回值都是无符号整数;当
f=NaN
,返回参数本身
- 示例:
isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
- 可用操作:所有整数相关操作,
||, &&, if, while
- 最大操作数:30
- 难度:4
代码
unsigned float_half(unsigned uf) { int sign_, exp_; // 若为INF或NaN,直接返回参数 if((uf & 0x7fffffff) >= 0x7f800000) // exp部分全为1 return uf; sign_ = uf & 0x80000000; exp_ = (uf & 0x7f800000) >> 23; // 将exp右移frac占的23位,得到exp的值 // 若exp>1,则乘0.5后依旧是规格化数 if(exp_ > 1) return (uf & 0x807fffff) | (exp_-1)<<23; // 若exp<=1,则乘0.5后变为非规格化数。此时只处理其frac部分,exp_直接为0 if((uf & 0x3) == 0x3) // 舍入默认“偶数进位规则”,当末尾为11时才需要进位 uf += 0x2; return ((uf>>1) & 0x007fffff) | sign_; }
❌错误代码
frac_+=0x2
时可能发生进位,这个进位本应该因溢出而舍去.unsigned float_half(unsigned uf) { // 若为INF或NaN,直接返回参数 if((uf & 0x7fffffff) >= 0x7f800000) // exp部分全为1 return uf; int sign_ = uf & 0x80000000; int exp_ = (uf & 0x7f800000) >> 23; // 将exp右移frac占的23位,得到exp的值 int frac_ = (uf & 0x007fffff); // 若exp>1,则乘0.5后依旧是规格化数 if(exp_ > 1) return sign_ | (exp_-1)<<23 | frac_; // 若exp<=1,则乘0.5后变为非规格化数。此时只处理其frac部分,exp_直接为0 if((frac_ & 0x3) == 0x3) // 舍入默认“偶数进位规则”,当末尾为11时才需要进位 frac_ += 0x2; return (frac_>>1) | sign_; }
15. float_i2f
(float)x
的位级表示- 说明:返回值是无符号整数,是浮点数的位级表示;
- 示例:
isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
- 可用操作:所有整数相关操作,
||, &&, if, while
- 最大操作数:30
- 难度:4
代码
unsigned float_i2f(int x) { int s_, n_; s_ = x & 0x80000000; n_ = 30; if(!x) return 0; if(x == 0x80000000) return 0xcf000000; if(s_) x = ~x+1; while(!(x & (1 << n_))) n_--; if(n_ <= 23) x <<= (23-n_); else{ x += (1 << (n_-24)); // 先进位 if(x << (55-n_)) ; // 32-(n_-23) = 32 - 多出来的位数 => 如果末尾多出来的位数不全为0的话 else x &= (0xffffffff << (n_-22)); if(x & (1<<n_)) ; // 若最高位进位,则n_++ else n_++; x >>= (n_-23); } x = x & 0x007fffff; n_ = (n_+127) <<23; return x | n_ | s_; }
更可读但更笨的方法
unsigned float_i2f(int x) { // 返回(float)x的位级表示 【40/27】 int sign_ , frac_, exp_, n, mask1, mask2, mask3; // 处理特殊情况:0和TMIN;后者取反为本身,因此无法通过取绝对值来常规转换 if(!x) return 0; if(x == 0x80000000) return 0xcf000000; // sign sign_ = x & 0x80000000; // 取绝对值 if(sign_) // x = (sign ^ x) + (1 & sign); x = ~x + 1; // 判断INF n = 30; while(!(x & (1 << n))) // 获取除符号位外的有效位长度n+1,其中frac位数为n --n; // frac if(n <= 23){ // 不用舍入 x = x << (23-n); }else{ // 超过精度范围,需要舍入 mask1 = ~0+(1<<(n-22)); // 取x左移后将丢弃的多余末尾串 mask2 = 0x1 << (n-24); // 左移后刚好为0.1的掩码表示 mask3 = (0x3<<(n-24)); // 左移后刚好为1.1的掩码表示 if(((x & mask1) > mask2) | (((x & mask1) == mask2) & ((x & mask3) == mask3))) // 若右移后,末尾是1.1或(>0.1)则进位 x += mask2; if(x & (1<<n<<1)) // 若最高位进位,则++n ++n; x = x >> (n-23); } frac_ = x & 0x7fffff; // exp exp_ = (n+127) << 23; return sign_ | exp_ | frac_; }
网上cpoy的贼快代码
unsigned float_i2f(int x) { //即将x变为float型。按照IEEE和向偶取整的规则即可。 int signbit,highbit,exp,flag; unsigned temp,result; if(!x) return x; //由于规范数情况不包含0,所以先处理0情况。 signbit=(x>>31)&0x01; if(signbit) x=~x+1; //获得符号位,并将x变为正值。 highbit=0; temp=x; while(!(temp&0x80000000)) { temp<<=1; highbit++; } //获得x的最高有效位,即确定fraction的位数。 temp=temp<<1; exp=127+31-highbit; //根据单精度浮点数规则计算出exp,和fraction位数。 flag=0; //进行向偶舍入 if((temp&0x1ff)>0x100) flag=1; //出现在规定位置后大于0b100的情况就进1. if((temp&0x3ff)==0x300) flag=1; //出现最后一位为1,且下一位为1的情况也进1(向偶取整) result=(signbit<<31)+(exp<<23)+(temp>>9)+flag;//计算最终结果 return result; }
- 作者:Antony_Zhang
- 链接:https://antonyzhang.cn/article/csapp-datalab
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。