Essay2026 / 03 / 23

DataLab-题1到8解答

😭😭CSAPP看完三章才听说官网上还有实验，于是就尝试了下。做了的感受就是，不做等于没看这本书。中间踩了很多坑，花了一个下午加晚上才做完一到九题。真的难.国外的教学感觉和国内很不一样啊，但是收获也是比国内的多。😭😭

怎么做

CSAPP内lab的核心在于其提供的那个压缩包，其内包含你要编辑的源代码，检验你代码是否符合题目要求的程序，还有检验你的代码是否通过打分的程序。请确保你的设备可以运行linux，并且安装有gcc，makhexe，以及32位运行时库那么将某个实验的压缩包解压，输入命令类似于

tar xvf 压缩包名称

在解压后的文件中，包含有README，要编辑的源码，源码的规范检测程序dlc，评分脚本(以.pl结尾)，构建文件Makefile等。你的流程就是，编辑源码，完成题目，然后使用make构建程序，同时使用dlc检查解答是否规范，并最后通过评分脚本检查自己的得分。下面以CSAPP的第一个实验，我自己的做答流程来进行熟悉

DATA_LAB

这是CSAPP的第一个实验,本实验对你能够使用的操作符，操作符数量等做了限制。并且本程序需要你的环境下的int为32位。本实验要你编辑的文件为bits.c，里面有很多类似puzzle的题目，要求你去完成一个又一个函数。你可以在编写完一个函数后就进行测试查看。下面就是我自己的作答流程。

第一题bitXOR

题目1仅使用~与&完成异或运算。先写好你的c函数。我的代码如下：

//1
/* 
 * 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 a = ~x & y;
  int b = ~y & x;
  return ~(~a & ~b);
}

写完之后，在该文件所在的目录，输入下面这个命令检查题目是否符合规范。

./dlc -e bits.c

如果通过，接下来先执行下面1这两条命令

make clean
make btest

这样你就会得到一个名为btest的可执行文件。接下来测试我们写的bitXOR对不对，输入

./btest -f bitXOR

其会输出下面这个结果

Score   Rating  Errors  Function
 1      1       0       bitXor
Total points: 1/1

说明我们刚刚写对了。如果你写的答案不对，就会输出下面这样

Score   Rating  Errors  Function
ERROR: Test bitXor(-2147483648[0x80000000],-2147483648[0x80000000]) failed...
...Gives -1[0xffffffff]. Should be 0[0x0]
Total points: 0/1

其中，如果你修改了源码，需要再次执行刚刚的两条make指令重新生成可执行文件。然后再按上面的流程进行测试。

第二题tmin

返回最小int整数。我的C代码如下

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

第三题isTmax

//2
/*
 * 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 a = x +1;
  int b = ~x;
  int c = !(a ^ b);
  int d = !!(a);
  return  c&d;
  return !res;
}

第四题allOddBits

判断二进制的奇数位是否全为1

/* 
 * 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 mask  = 170 << 24;
  mask += 170<<16;
  mask += 170<<8;
  mask += 170;
  mask ^= mask & x;
  //printf("x = %x , mask = %x ,result = %x\n",x,mask,result);
  return !mask;
}

第五题negate

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  int result = ~x;
  result = result +1;
  return result;
}

第六题isAsciiDigit

这道题挺难的，第一次没做出来。核心就在于用构造精妙的位操作来进行大小判断。这里判断0x30与0x38就在于高4位始终为0011，低四位的范围为0000到1001. 所以如果要是，就要满足两个条件

高4位 = 3
低4位 <= 9

/* 
 * 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 isAsciiDigit(int x) {
    int high = x >> 4;          // 取出高4位
    int low = x & 0xF;          // 取出低4位
    int cond1 = !(high ^ 0x3);  // 高4位是否为 0x3,high ^ 0x3天然排除高位非0的情况
    int cond2 = !((low + 6) >> 4); // 低4位是否 <= 9
    return cond1 & cond2;
}
}

第七题conditional

这个题目有一个小结论，对于 a? b :c，在a只有全1与全0两种情况时，可翻译为 (a & b) | (~a & c)

/* 
 * 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 a = !!x;
  a = a << 31;
  a = a >> 31;
  return (a & y) | (~a & z);
}

第八题isLessOrEqual

这题的思路很简单,但是对于一些边界问题的处理有点麻烦。思路就是result = y-x,然后看result的符号位。但是y-x会有溢出的情况就非常麻烦从数学角度分类讨论，结果如下

x的符号位	y的符号位	是否溢出
正	正	不会
正	负	会
负	负	不会
负	正	会

那么我们要知道一个点，x,y如果同号减法不会发生溢出，异号就会发生溢出 而恰好x,y异号的话就可以直接判断大小了，不用看减法结果

思路为先计算减法,这是机器比较大小必须经过阿一步

int diff = y+(~x+1)//如果你看不懂~x+1是在干什么说明你应该好好复习补码知识了

获取到x，y的符号位，获取到二者是否同号

int s_X = x >> 31;
int s_Y = y >> 31;
int same = !(s_X ^ s_Y);

如果二者同号,由于减法不会溢出，看减法结果

int cond1 = same & !signal_diff;

如果二者不同号，直接就看其中一方的符号。如x<0就代表y>0,y>=x成立

int cond2 = (!same) & (!!sign_x);

于是，我们就得到了下面的答案

/* 
 * 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 diff = (~x +1) + y;
  int signal_x =x >> 31;
  int signal_y = y >>31;
  int signal_diff = diff >> 31;
  int same = !(signal_x ^ signal_y);
  int cond1 = same & !signal_diff; //同号根据diff符号位判断
  int cond2 = (!same) & (!!sign_x); //异号情况就看x或者y的符号位判断
  return cond1 | cond2; //合并上面两个判断
}

总结

也是体验了一下CSAPP的这个实验，只能说难是确实有难度，坐下来只感觉自己像是个废物。但是只要做掉肯定有收获。至少比我学校里教计算机系统的实验，看下汇编代码这样地复现性实验要强的多。其实从这个实验来看，要的就是让你真正地去模拟底层CPU，以此完成那些在高级编程语言中感觉稀疏平常的工作。毕竟CPU最底层没有减法，没有乘法除法，没有大于号小于号条件判断，而是各种位运算与加法。做下来大概就有一点理解底层的CPU完成这些活到底有”多费劲”,感知到现代编程语言的伟大。当然，还有对位操作浙西东西有了更加深刻的理解。

比如a == b就可以表示为! ( a ^ b ),a != b可以表示为 a !!(a^b)。在a以全1表示true，全0表示false的情况下，a ? b : c可以表示为(a&b) | (!a&c).还有-a，其实就是执行~a+1,比较a < b，就会执行一步减法操作，在不溢出的情况下根据符号位来判断，溢出的情况特殊处理。这些都可以对应到底层的逻辑门之类的。还是很有收获的。(虽然可能过几个月忘了)