CSAPP 实验1 datalab

作者： 作者的头像   代码改变头发 ,  2021-08-21 23:45:57 ,  所有人可见 ,  阅读 807

7


4

CSAPP笔记&实验

实验步骤

下载地址 点击Self-Study Handout下载.

编辑 : bits.c文件按限制完成函数功能.
测试 : 三种测试方式

  • dlc 测试有非法(限制外)符号 ./dlc bits.c
  • btest 测试结果是否正确 make btest ./btest (在每次修改bits.c后需要再make一遍)
  • driver.pl 测试最终结果 ./driver.pl

帮助 : READEME中有相关命令详细介绍. 此外提供fshow/ishow函数, 输入10进制参数, 函数输出
对应补码/浮点数编码.

实验内容
Integer实验要求

修改return语句
只能使用 :

  • 0到255(0xFF)的整型常量
  • 函数形参和本地变量
  • & ^ | + << >>

假设你的机器 :

  • 使用32位补码的整型变量
  • 使用算术右移
BitXor
//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) {
  return 2;
}

实现^运算, 考虑$x$ ^ $y$结果中第i位为$1$的两种可能, $x_i = 1 且 y_i = 0$ 或 $x_i = 0 且 y_i = 1$ .
$x_i = 1 且 y_i = 0$ : 用$x$ & ~$y$得到; $x_i = 0 且 y_i = 1$ : ~$x$&$y$.
所以$x$ ^ $y$ = ($x$ & ~$y$) | (~$x$&$y$) . 新的问题 : |运算如何用~和&实现 ?

这里用到一点数理逻辑的知识, 德摩根定律.
1.png
这里的¬为C中逻辑运算非!. 我们把或运算两边作为¬P和¬Q 即可求解.

int bitXor(int x, int y)
{
    int np = x & (~y);
    int nq = (~x) & y;
    return ~( (~np) & (~nq) ); //~np -> p 
}
tmin
//1
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 2;

}

返回tmin, 这里默认是32位补码整数, tmin的二进制形式为最高有效位为1(负权), 其余位为0(正权).
所以直接用移位运算即可.

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) {
  return 2;
}

判断x是否是tmax 这里实际用到tmin的特点, 只有$tmax + 1 = tmin$. 而除了$0$之外只有$tmin = -tmin$, 这是因为补码表示的不对称造成的. 所以排除$0$外判断$(x+1)$是否与$-(x+1)$数位相同即可.

数位相同 : 用到 ^ 的特点, 只有全部相同才为0.

int isTmax(int x) {
    int y = x + 1, ny = ~y + 1; 
    return !!y & !(y^ny);//!!y排除0 
}

上述思路比较复杂, 我们可以直接得到tmax, 判断是否与$x$相等.

int isTmax(int x) {
    int tmax = ~(1 << 31);
    return !( x ^ tmax );
}

不幸的是题目限制不能使用移位.

addOddBits
//2
/* 
 * 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) {

  return 2;
}

思路 : 判断$x$的奇数位是否全为1. 可以用掩码思想先用一个奇数位为1偶数位为0的数$(0xAA)$&$x$得到
$x$的所有奇数位, 将得到的结果判断是否与掩码相同.

int allOddBits(int x) {
    int mask = (0xAA) | (0xAA << 8) | (0xAA << 16) | (0xAA << 24);
    int y = x & mask;
    return !(y ^ mask);
}
negate
//2
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return 2;
}

补码$x$的负数 = $x$按位取反 $+$ 1. 考虑4位补码. $1111 + 0001 = 0$; $x + ny = 0 = 1111 + 0001$
–> $nx = 1111 - x + 1$, 其中$1111 - x$相当于对$x$按位取反.

int negate(int x) {
  return ~x + 1; 
}
isAsciiDigit
//3
/* 
 * 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) {
  return !( (x>>4) ^ 0x3 ) & !( ( ((x&0xf) + 6 ) >> 4 ) & 1 );
}

判断$x$是否在['0','9']. 首先判断4~7位是否是0x3, 取底四位数值0~9, 这里加入偏移量6后值
为6~15, 位级表示为0xxxx; 而更大的数字第4位为1.

int isAsciiDigit(int x) {
  return !( (x>>4) ^ 0x3 ) & !( ( ((x&0xf) + 6 ) >> 4 ) & 1 );
}
conditional
//3
/* 
 * 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) {
  return 2;;
}

考虑$!x$后$x = 0/1$, $!x - 1 = 0xffffffff/0$. $(!x - 1)$ & $r$ = $r/0$.
我们可以考虑让$y/z$对应的为$0xffffffff/$一个为$0$, 在用|运算综合结果.
题目限制不能使用-, $-1 = + (-1) = +$~$0$

int conditional(int x, int y, int z) {
  return (( (!x) - 1) & y ) | ( ((!!x) - 1 ) & z );
}

或考虑 $x = 0/1$, $~(!!x) + 1 = 0/0xffffffff$

int conditional(int x, int y, int z) {
  int val = ~(!!x) + 1;
  return (val & y) | (~val & z);
}
isLessOrEqual
//3
/* 
 * 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) {
  return 2;
}

分情况讨论

  1. 符号位相同, 判断 $y - x$ 的符号位是否为0(正)
  2. 符号位不同, 若$x$符号位为1($x$正$y$负)则返回0

分类返回用到了上一题的思路.

int isLessOrEqual(int x, int y) {
  int val = ( x >> 31 ) ^ (y >> 31); //val > 0 则表示符号不同
  int sx = (x >> 31) & 1, s = ( ( y + (~x) + 1 ) >> 31 ) & 1;//sx x的符号位
  val = ~(!!val) + 1; // : ? 的思路
  return ( val & sx ) | (~val & (!s) );
}
logicalNeg
int logicalNeg(int x) {
  return 2;
}
/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */

0有很多特点 : $-0 == 0 ($~$0 + 1) == 0$; 此外只有$-tmin == tmin$.
对于$x$和$-x$, 至少有一个为负数, 也就是符号位为1. 算数左移31位后得到$0xffffffff$.
再把结果$+1$即可得到我们需要的结果.

int logicalNeg(int x) {
  int nx = (~x) + 1; 
  return ((x | nx) >> 31) + 1;
}
howManyBits
/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  return 0;
}

题意 :

  • 对于正数如$12 = 0x1010$, 其最高位1在第4位, 且补码需要一位作为符号位, 所以对于正数需要找到最高位1的位置再加上一位符号位.

  • 对于负数, 我们由补码符号扩展值不变的性质可以反推把从符号位向低位的连续一段1只保留最低的1,
    如$-1 = 0xfffffffb = 1011$. 之后将数字按位取反后同样可以认为是找到最高位1的位置再加上1.

问题变为找最高位在什么位置, 这里神奇的可以用到分治思想. 每次在高/低的一半判断是否有1.($16->8->4->2->1$).
每次判断若高位有1, 则令$x$右移只取高位, 否则不需要右移.

int howManyBits(int x) {
  int b16, b8, b4, b2, b1, b0;

  x = x ^ (x >> 31); //利用算数右移和^的性质

  b16 = (!!(x >> 16)) << 4; //判断高16是否有1, 有1则置为16
  x >>= b16; //有1则取高16位/ 否则x不变即之后操作底位

  b8 = (!!(x >> 8)) << 3; //同理 使用二分思想
  x >>= b8;

  b4 = (!!(x >> 4)) << 2;
  x >>= b4;

  b2 = (!!(x >> 2)) << 1;
  x >>= b2;

  b1 = (!!(x >> 1));
  x >> b1;

  b0 = x;

  return b16 + b8 + b4 + b2 + b1 + + b0 + 1;
}
Float实验要求
For the problems that require you to implement 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 can use any arithmetic,
logical, or comparison operations on int or unsigned data.
floatScale2
//float
/* 
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf) {
  return 2;
}

求浮点数乘2的结果, 对规格化数阶码加1即可, 但需要考虑特殊情况

  • Inf/ NaN
  • 非规格数

首先用掩码提取阶码段和尾数段.

  int exp_mask = 0x7F800000, frac_mask = 0x007FFFFF;
  int exp = uf & exp_mask, frac = uf & frac_mask;

判断是否为Inf/NaN

if( exp == exp_mask )
  {
        return uf;
  }

判断是否是非规格化数字. 从浮点数从非规格化数字到规格化数字的光滑转换保证可以用$<<1$实现乘以2.

  else if( !exp )
  {
      frac <<= 1;//左移一位
  }

规格化情况.$exp++$

  else
  {
      exp += 0x800000; 
  }

最后把三段综合

return ( uf & 0x80000000 ) | exp | frac;

完整代码

unsigned floatScale2(unsigned uf) {
  int exp_mask = 0x7F800000, frac_mask = 0x007FFFFF;
  int exp = uf & exp_mask, frac = uf & frac_mask;

  if( exp == exp_mask )
  {//NaN/Inf exp全为1
        return uf;
  }
  else if( !exp )
  {//0或者非规格化数字
      frac <<= 1;//左移一位
  }
  else
  {//规格化数字 阶码+1
      exp += 0x800000; 
  }
  return ( uf & 0x80000000 ) | exp | frac;
}
floatFloat2Int
/* 
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
    return 2;
}

将浮点数(位级)转为整型, 分类讨论

  • 浮点数超过整型表达最大值

  • 浮点数小于1

  • 浮点数能用整型表示

首先取出各个字段.

  int exp_mask = 0x7F800000, frac_mask = 0x007FFFFF;
  int exp = ( uf & exp_mask ) >> 23;
  int frac = uf & frac_mask;
  int sign = !!(uf >> 31);
  int bias = (1 << 7) - 1;

判断是否超出int表示范围

  if( exp - bias >= 31 ) // 1 << 31 - 1为Tmax 大于其范围即为Tmin或者无法表示
  {//超过最大范围或者恰好为Tmin
      return (1 << 31);//Tmin
  }

判断是否小于1

  else if( exp < bias )
  {//小于1 
      return 0;
  }

int可以表示. 

  else
  {
      int ret = ((frac >> 23) + 1) << (exp - bias); //frac >> 23 移动小数点. <<实现2^(exp-bias)
      if( sign )    ret = ~ret + 1;//负号
      return ret;
  }

完整代码

int floatFloat2Int(unsigned uf) {
  int exp_mask = 0x7F800000, frac_mask = 0x007FFFFF;
  int exp = ( uf & exp_mask ) >> 23;
  int frac = uf & frac_mask;
  int sign = !!(uf >> 31);
  int bias = (1 << 7) - 1;

  if( exp - bias >= 31 )
  {//超过最大范围或者恰好为Tmin
      return (1 << 31);
  }
  else if( exp < bias )
  {//小于1 
      return 0;
  }
  else
  {
      int ret = ((frac >> 23) + 1) << (exp - bias);
      if( sign )    ret = ~ret + 1;//负号
      return ret;
  }
} 

/* 
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *   (2.0 raised to the power x) for any 32-bit integer x.
 *
 *   The unsigned value that is returned should have the identical bit
 *   representation as the single-precision floating-point number 2.0^x.
 *   If the result is too small to be represented as a denorm, return
 *   0. If too large, return +INF.
 * 
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
 *   Max ops: 30 
 *   Rating: 4
 */
unsigned floatPower2(int x) {
    return 2;
}

求$2^x$的浮点数位级表示. 分类讨论

  • 超过浮点数最大表示范围

  • 超过浮点数最小表示范围

  • 需要用非规格化形式表示

  • 规格化形式

考虑规格化下阶码表示范围, $V = (-1)^s * M * 2^E $ = $V = (-1)^s * (1+f) * 2^{exp-bias} $
$exp$为8为无符号整数, $1 <= exp <= 2^8 - 1$. 所以$x > expmax -bias$时, 返回+INF.

非规格化用来表示接近0的数, $V = (-1)^s * (f) * 2^{1 - bias}$, $f$最小可以表示$2^{-23}$.
所以可以表示的最小值为$min = 1 - bias - 23$, 若$x$小于$min$返回0.

若$min<= x <1 - bias$, 需要用非规格化表示. 此时$f * 2^{1-bias} = 2^x$, $f = 2^{x + bias - 1}$,
可以用1右移|$x + bias - 1$|实现.

否则可以用规格化实现, $2^{exp-bias} = 2^x$, $exp = x + bias$

unsigned floatPower2(int x) {
  int exp_mask = 0x7F800000;
  int bias = (1 << 7) - 1;
  int exp_max = ( 1 << 8 ) - 1;

  if( x > exp_max - bias )
  {//超过最大范围
      return exp_mask; //+INF
  }
  else if( x  < 1 - bias - 23 )
  {
      return 0;
  }
  else if( x < 1 - bias )
  {//f * 2^(1-bias) = 2^x -->  = 2^ ( x + bias - 1 )
      int shift = x + bias - 1; shift = (~shift) + 1;
      return ( 1 << 23 ) >> shift;
  }
  else
  {// 1 * 2^(exp-bias) = 2^x --> exp = x + bias
      int exp = x + bias;
      return (exp << 23);
  }
}

参考地址1
参考地址2

5 评论

用户头像
SeanCheng   2022-06-16 21:18         踩      回复

为啥我的driver.pl测试出来correctness是0，但是btest和dlc测试出来的都是正确的，你有这个情况吗

用户头像
代码改变头发   2022-06-16 21:23         踩      回复

我没遇到唉

用户头像
Coincidence233   2021-08-22 17:21         踩      回复

%%%

用户头像
CharlesLC   2021-08-22 10:12         踩      回复

%%%

用户头像
ohhowo   2021-08-22 01:45         踩      回复

%%%