CSAPP 实验I Data Lab

发表于 2023-03-09 更新于 2024-04-13 分类于 csapp 阅读次数：

CSAPP的第一个实验,处理二进制代码,解谜题。

更新历史

23.03.10：初稿

系列

任务目标

DataLab实验，需要我们完善函数，条件是使用限定的操作符，并且操作符的数量也有限制，“=”不做数量限制。

题目及解法

bitXor

题目要求：返回两个int的异或值
允许操作：~ &
操作数量：14
分值：1

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

tmin

题目要求：求补码的最小值
允许操作：! ~ & ^ | + << >>
操作数量：4
分值：1

32位机器码的补码最小值是最高位为1，其他位0，所以用1左移31位形成。

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

isTmax

题目要求：如果x是补码最大值返回1，否则返回0
允许操作：! ~ & ^ | +
操作数量：10
分值：1

补码的最大值是最高位0，其他位1。加1后是最小值，Tmin和Tmax每位都相反，Tmin^Tmax是全1，可以使用这个值进行返回。需要注意补码的特殊值Tmin，Tmax，还需要注意-1，32位全1 1111，因为-1 ^ 0 = 1，需要排除这种情况

flag_2 表示x是否等于 -1
1. 如果x==-1， y=0，y^0 == 0 flag_2为0
2. 如果x!=-1，y!=0， y^0 != 0，flag_2不为0，flag的值是0或1，所以需要取非两次，把非零值转换为1
flag_1 表示(x+1)^x，有两种情况结果为全1，x是Tmax和-1，我们只需要全为1的情况，所以先取反~，换成全0，再取非!，转为1。
返回值为两个标志相与，用flag_2排除掉flag_1中-1的这种情况，剩下的就是Tmax

int isTmax(int x) {
  int y = x + 1;  //Tmin
  int flag_1 = !(~(x ^ y)); 
  int flag_2= !!(y ^ 0);
  return flag_1 & flag_2; 
}

allOddBits

题目要求：如果每一个偶数位都是1返回1，否则返回0
允许操作：! ~ & ^ | + << >>
操作数量：12
分值：2

先从32比特中只保留所有偶数位的值，其他位赋值0，再和0xAAAAAAAA作对比相等返回1，因为不能用等号，所以用异或^代替判断，如果相等全为0，取非!值为1，否则为0。

移位和加法让变量y等于0xAAAAAAAA。
x与y相与，只留下x的偶数位的值
用异或判断x与y是不是相等

int allOddBits(int x) {
  int y = 0xAA; 
  //+优先级大于 << 
  y  = y + (y << 8);
  y = y + (y << 16);
  //只留下x的偶数位值
  x = x & y;
  return !(y ^ x) ;
}

negate

题目要求：返回-x
允许操作：! ~ & ^ | + << >>
操作数量：5
分值：2

这个比较简单，根据二进制补码x与-x就是按位取反再加1。

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

isAsciiDigit

题目要求：判断x是不是ASCII码的0-9，相当于判断x的值是不是0x30到0x39。
允许操作：! ~ & ^ | + << >>
操作数量：15
分值：3

先观察0-9的补码形式

0x30 110000

0x37 110111

0x38 111000

0x39 111001

首先需要满足除后6位外，高位全为0，满足第一个条件后0-7满足前三位为110，剩下的直接对比是不是等于8或9。不能使用等号所以用异或判断相等

flag_1 右移6位后，如果高位全为0，就是0，取非!为1，不然就是0
flag_2 右移3位后，满足第一个条件的除了低3位其他全为0，与110比较相等就是0到7中的值
flag_3， flag_4，直接判断是不是等于8，9。

int isAsciiDigit(int x) {
  int y = x & 0x3f; //截取x的后6位
  int flag_1 = !(x >> 6); //右移六位后,取非为1   x的高位全是0  符合条件
  int flag_2 = !((x >> 3) ^ 0x6);  //满足第一个条件后,右移3位   异或110   如果为0  就是属于'0' 到'7'
  int flag_3 = !(y ^ 0x38);  //满足第一个条件后   是'8'
  int flag_4 = !(y ^ 0x39);   //满足第一个条件后   是'9'
  return flag_1 & (flag_2 | flag_3 | flag_4);
}

conditional

题目要求：x不为0，返回y， x等于0，返回z。
允许操作：! ~ & ^ | + << >>
操作数量：16
分值：3

先找返回值，x等于0，return (x & y) ^ (~x & z)，x不等于0的时候，结果很多，这时候把x处理一下变为全1，返回值就相等了。

对于x不等于0的情况，换全1比较麻烦，对x取非!，把x简化成0或1。
把x扩展到全1和全0，用移位加也能做出来而且满足操作数量的限制，继续做后面的题目logicalNeg想到了一个快速扩展的方法，0或1，取反加1，就是全0或者全1。

int conditional(int x, int y, int z) {
  x = !x;   //取非 把x变为 0 1两种    把他们扩展到32位
  x = ~x + 1;  //01快速扩展到全0全1 
 // x = (x << 1) + x;
 // x = (x << 2) + x;
 // x = (x << 4) + x;
 // x = (x << 8) + x;
 // x = (x << 16) + x;
  return ((~x) & y) ^ (x & z);
}

isLessOrEqual

题目要求：x<=y，返回1，否则返回0。
允许操作：! ~ & ^ | + << >>
操作数量：24
分值：3

找出所以返回1的情况，一共两种情况，相等，小于。相等的时候比较好做，用异或判断相等，小于的情况比较复杂。

等于：flag_3表示相等的情况异或判断
小于：有两种情况 需要注意减法同号一点不会溢出
1. flag_5：x负数，y正数。
2. flag_4：x，y同号，x < y，转换为 y-x>0。
用flag_5 表示x负数，y正数。 用右移31位看符号看判断正负
用flag_6 表示x正数，y负数。
用sum=y - x，flag_4 表示符号。

int isLessOrEqual(int x, int y) {
  int nagete_x = ~x + 1;
  int sum = y + nagete_x; 
  int flag_3 = !(x ^ y);
  int flag_5 = (x >> 31) & !(y >> 31);   
  int flag_6 = !(x >> 31) & (y >> 31);   
  int flag_4 = !(sum >> 31) & !flag_5 & !flag_6;   //xy同号  减法不会溢出  减法有效
  return flag_3 | flag_4 | flag_5;
}

logicalNeg

题目要求：实现取非!的功能
允许操作：~ & ^ | + << >>
操作数量：12
分值：4

思路：取非结果只有0和1，把全0或全1加1，就是1或0，所以就需要把0转换为全1，非0转换为全0，然后加1，就是返回值。默认返回0，找出返回1的情况，也就是全1。只有0和Tmin的负值和自己符号相同，其他的符号都相反

取负值，对符号位扩展，然后自己的符号位和负值符号位相加，
1. 0和Tmin，结果为0。
2. 其他结果为全1。
flag_1：~sum，0和Tmin结果为全1，其他为全0。
flag_2：~Tmin 01111 ~0全1
flag_3：flag_1 中排除到flag_2的Tmin情况
1. Tmin 0111 0为1111 其余为0000
2. 取反，只保留符号位， Tmin 1111 0为0000 其余为1111
3. 加1后，0为0001，其余都统一为0000

int logicalNeg(int x) {
  int neg_x = ~x;
  int y = neg_x + 1;
  int hight_x = x >> 31;
  int hight_y = y >> 31;
  int flag_1 = ~(hight_x + hight_y);
  int flag_2 = neg_x;
  int flag_3 = (~(flag_1 & flag_2) >> 31) + 1;
  return flag_3;
}

howManyBits

题目要求：返回表示x的补码最短长度 注意-1，用一位
允许操作：! ~ & ^ | + << >>
操作数量：90
分值：4

思路：用上面做的函数 conditional 做两个if功能，一次返回分半查找的剩余一半函数，一次计算分半如果选择前一半，bit数要加上一半的长度，选择后面长度加0不做处理。

用0xffff0000 留下x的前16位,如果不等于0 说明位数大于16 等于0 说明位数小于16 在后16位内再进行分半查找

正负数的处理重点
都处理成正数，方便右移添0。加上符号位就是有效位数。

正数：找出最高位的1。
负数：找出最高位的0，Tmin也符合

负数高位连续的1都是无用数据，只需要找到高位连续的1后的第一个0在哪里，做法是取反，如1110010，有用的数据是10010，全部取反后0001101，有效位数是4位，加上符号位。
flag_nage： x是负数值为1
重点代码，
1. if函数功能
  
  x = (extend_f_n & (~x)) ^ ((~extend_f_n) & x); ：如果标记为全1，选择的~x，如果为全0，选择的x。异或的两边有一个一直为全0，结果一定是另一个。
2. 一个二分法
  
  x_32 = x & bit_32; ：取x的前16位
  x_32 = !x_32;：取非，如果前16位全0，值就是1，否则是0
  x_32 = ~x_32 + 1; 前16位全0，扩充到全1，否则扩充到全0
  flag_32 = ~x_32; 这里是为了减少一个op值，重复使用代码
  x_16 = (flag_32 & (x >> 16)) ^ ((x_32 & (x & (~bit_32))));
  x_32如果全0，说明前16位，有1，那就把x右移16位，覆盖掉后面，继续对这16位进行二分法。这里不用考虑右移补1，因为都是正数最高位都是0。并且总数加16。
  如果全1，说明前16位都是0，要从后16位开始二分法，不用移位，x_16要等于x的后16位。总数加0。
  sum = sum + (flag_32 & 16);：

int howManyBits(int x) {
  int x_32, x_16, x_8, x_4, x_2;  //分别表示x的不同比特
  int bit_8 = 0xff << 8;
  int bit_32 = (bit_8 + 0xff) << 16;   
  int bit_16 = bit_8;
  int flag_32,flag_16,flag_8,flag_4,flag_2;  //表示 ~x_32  重使用一次 减少 ops数量
  int sum = 0;
  int flag_nage = !!(x >> 31);     //  x是负数   值为1
  //通过负0和Tmin 都是自己   ^之后为0  排除x是0的情况    当x是Tmin 是值为1
  //int flag_Tmin = !(x ^ (~x + 1)) & x; 
  int flag_Tmin = !(x << 1) & x;   //Tmin 左移一位 去掉符号位后是全0   比上面的方法减少op
  int extend_f_T = ~flag_Tmin + 1;      //扩展flag_Tmin
  int extend_f_n = ~flag_nage + 1;      //扩展flag_nage
  sum = sum + (flag_Tmin & 32);
  x = (extend_f_T & 0) ^ ((~extend_f_T) & x);  // flag_Tmin 是1时  x赋值0   是0是  x不变

  x = (extend_f_n & (~x)) ^ ((~extend_f_n) & x);  // flag_nage 是1时  x赋值~x   是0是  x不变

  bit_8 = 0xf0; 
  x_32 = x & bit_32;
  x_32 = !x_32;
  x_32 = ~x_32 + 1;
  flag_32 = ~x_32;
  x_16 = (flag_32 & (x >> 16)) ^ ((x_32 & (x & (~bit_32))));
  sum = sum + (flag_32 & 16);

  x = x_16;   //改变x
  x_16 = x & bit_16;
  x_16 = !x_16;
  x_16 = ~x_16 + 1;
  flag_16 = ~x_16;
  x_8 = (flag_16 & (x >> 8)) ^ ((x_16 & (x & 0xff)));
  sum = sum + (flag_16 & 8);

  x = x_8;   //改变x
  x_8 = x & bit_8;
  x_8 = !x_8;
  x_8 = ~x_8 + 1;
  flag_8 = ~x_8;
  x_4 = (flag_8 & (x >> 4)) ^ ((x_8 & (x & (0xf))));   //~bit_8  改为0xf  省一个op
  sum = sum + (flag_8 & 4);

  x = x_4;   //改变x
  x_4 = x & 12;
  x_4 = !x_4;
  x_4 = ~x_4 + 1;
  flag_4 = ~x_4;
  x_2 = (flag_4 & (x >> 2)) ^ ((x_4 & (x & 3)));
  sum = sum + (flag_4 & 2);

  x = x_2;
  x_2 = x_2 >> 1;
  x_2 = !x_2;
  x_2 = ~x_2 + 1;
  flag_2 = ~x_2;
  x = (flag_2 & (x >> 1)) ^ ((x_2 & (x & 1)));
  sum = sum + (flag_2 & 1);

  sum = sum + (x & 1);  //如果x是0  或者处理之后的Tmin  剩余位全是0    不加最后一个比特位   其他情况加上1

  sum = sum + (!flag_Tmin & 1);   //非Tmin  加上符号位    0符号位就是0  一个bit表示

  return sum;
}

floatScale2

题目要求：无符号数保存的float值，返回乘2
允许操作：所有的int，无符号操作符，if，while
操作数量：30
分值：4

思路：

0返回0
exp全1：为无穷直接返回
exp全0： 非规格化值：小数部分没有隐藏位

f不是全0 直接加左移一位最后补上符号。非规格化到规格化的过渡
f是全0 不做处理返回原值，就是第一种情况
exp 不全1全0 直接加1 相当于乘2

unsigned floatScale2(unsigned uf) {
  unsigned bit_exp;
  unsigned bit_f;  //小数部分
  unsigned flag_s;  //符号位
  if(uf == 0){
    return 0;
  }

  bit_f = uf & (0x007fffff);
  bit_exp = uf & (0x7f800000);   //取出指数部分
  flag_s = uf >> 31;
  if(bit_exp == 0x7f800000){
    return uf;
  }
  bit_exp = bit_exp >> 23;       //exp的值
  if(bit_exp != 0){
    bit_exp = bit_exp + 1;
    bit_exp = bit_exp << 23;
    uf = uf & ~(0x7f800000);
    uf = uf ^ bit_exp;
  }
  if(bit_exp == 0 && bit_f != 0){
      uf = uf << 1;
      if(flag_s == 1){
        uf = uf | (flag_s << 31);  //补上符号位
      }
  }

  return uf;
}

floatFloat2Int

题目要求：float转int值
允许操作：所有的int，无符号操作符，if，while
操作数量：30
分值：4

思路：确定指数的范围

exp < 127 指数小于0时，是小数，返回0。
exp > 158 指数大于31 越界
exp 全0 返回0
exp 全1 返回0x80000000u
exp 其他情况下对f部分补上隐藏位1 再右移exp-127位，最后补上符号位

int floatFloat2Int(unsigned uf) {
  unsigned bit_exp;
  unsigned bit_f;  //小数部分
  unsigned flag_s;  //符号位
  unsigned E;      //指数
  int F2Int;
  bit_f = uf & (0x007fffff);   //取出小数部分
  bit_f = bit_f | (0x00800000);  //补上前面隐藏1
  bit_exp = uf & (0x7f800000);   //取出指数部分
  bit_exp = bit_exp >> 23;
  flag_s = uf >> 31;
  //printf("s %u %x  exp  %u %x   f  %u  %x\n", flag_s, flag_s, bit_exp, bit_exp, bit_f, bit_f);
  if(bit_exp == 0xff || bit_exp > 158){  //无穷   或者NaN   指数越界  
    return 0x80000000u;
  }
  if(bit_exp < 127 || bit_exp  == 0){  //指数是负数   非规格数
    return 0;
  }   
  E = bit_exp - 127;
  bit_f = bit_f >> (23 - E);  //右移
  //printf("E %u %x  bit_f   %u %x \n", E, E, bit_f, bit_f);
  F2Int = bit_f;   
  if(flag_s == 1){
    F2Int = -F2Int;
  }
  return F2Int;
}

floatPower2

题目要求：返回float值 2的x次方，x为32位int
允许操作：所有的int，无符号操作符，if，while
操作数量：30
分值：4

思路：确定指数的范围 x为-127到128之间。

时间超时 10s内跑不完所有测试数据可能是电脑问题

unsigned floatPower2(int x) {
  unsigned bit_exp;
  unsigned bit_float;  //float值的bit位
  unsigned INF = 0x7f800000;
  if(x < -127){  //值太小
    return 0;
  }   
  if(x > 128){  //太大  返回+INF
    return INF;
  }
  //printf("x    %d\n", x);
  bit_exp = x + 127;
  bit_exp = bit_exp << 23;
  //printf("bit_float  %u  %x\n", bit_float, bit_float);
  return bit_exp;
}

系列