Lab地址 http://csapp.cs.cmu.edu/3e/students.html

DataLab

1 - bitXor

 /*
 * 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 (~x)&y;
  return (~((~x)&(~y)))&~(x&y)
}

该题应用德摩根律

A \oplus B = \overline{\overset{ˉ}{A} B \cup A \overset{ˉ}{B}} = \overline{(A \cup \overset{ˉ}{B}) \cap (\overset{ˉ}{A} \cup B)} = ... = \overline{\overset{ˉ}{A} \overset{ˉ}{B} \cup (A B)} = \overline{(\overset{ˉ}{A} \overset{ˉ}{B})} \cap \overline{(A B)}

2 - istMax

/*
 * 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 !((~(x+1))^x) & !!(x+1);
  //return !!((x+1)&(-128));
}

Tmax的值为0x7FFFFFFF(0111…111)，加一后变为0x80000000(1000…000),此时0x80000000取反后就为0x7FFFFFFF，因此可以用异或判断相等。但有一个特殊情况0xFFFFFFFF(全1)，也符合加一后取反和原数相等，故通过!!(x+1)排除这种情况。

3 - allOddBits

/* 
 * 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 AAAA = 0xAA + (0xAA<<8);
  int AAAAAA = 0xAA + (AAAA<<8);
  int AAAAAAAA = 0xAA + (AAAAAA<<8);
  return !((x&AAAAAAAA)^AAAAAAAA);
  //return !((x&0xAAAAAAAA)^0xAAAAAAAA);
}

由于题目不允许使用超过0xFF的常数，故使用移位操作构造出0xAAAAAAAA

4 - isAsciiDigit

/* 
 * 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 a = !((x >> 4) ^ 3);
  int b = !!(((x & 0xF) + (~0xA)+1) >> 31);
 
  return a&b;
  //return !((((~x)+1+0x30)&(0x80000000))+((x+(~0x39)+1)&(0x80000000)));
}

题目要求判断范围在0x30 ⇐ x ⇐ 0x39的数。观察发现 0x30 0x39 0011 0000 0011 1001 在这个范围内的数，右移四位后应是0011，且不大于1001，于是可以减去0xA(1010)为负来判断小于1010。

5 - isLessOrEqual

/* 
 * 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 a = !(x ^ y);
    int signX = (x >> 31) & 1;
    int signY = (y >> 31) & 1;
    //X is a positive number and Y is a negative number,return 0.
    int b = !((!signX) & (signY));
    //X is a negative number and Y is a positive number,return 1.
    int c = (signX) & (!signY);
    //y - x > 0?
    int d = !((y+(~x)+1) >> 31);
   return (a|b)&(c|d);
  //return !((y+(~x)+1)&(0x80000000)) ;
}

分四种情况：第一种：x==y，直接返回1 第二种：x是正数，y是负数，直接返回0 第三种：x是负数，y是正数，直接返回1 第四种：x,y同号，且x

6 - logicalNeg

/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int logicalNeg(int x) {
  int negX = (~x) + 1;
  int sign = (negX | x) >> 31;
  return sign+1;
  //return 2;
}

实现非：非只区分零和非零，他们直接最大的区别就是如果-x==x则x==0而x!=0时没有这个性质利用这个性质可以有 (negX | x) >> 31 如果x为非0，则(negX | x) >> 31的结果为全1，加1后返回结果为0 如果x为0，则(negX | x) >> 31的结果为0，加1后返回结果为1

7 - 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) {
  int isZero = !x;
  int signX = x >> 31;
  int notZeroMask = ((!!x) << 31) >> 31;
  x = (signX & (~x)) | ((~signX) & x);
  int bit_16, bit_8, bit_4,bit_2, bit_1, bit_0;
 
  bit_16 = (!((!!(x>>16)) ^ (0x1))) << 4;
  x >>= bit_16;
 
  bit_8 = (!((!!(x>>8)) ^ (0x1))) << 3;
  x >>= bit_8;
 
  bit_4 = (!((!!(x>>4)) ^ (0x1))) << 2;
  x >>= bit_4;
 
  bit_2 = (!((!!(x>>2)) ^ (0x1))) << 1;
  x >>= bit_2;
 
  bit_1 = (!((!!(x>>1)) ^ (0x1)));
  x >>= bit_1;
 
  bit_0 = x;
  int res = bit_0 + bit_1 + bit_2 + bit_4 + bit_8 + bit_16 + 1;
 
  return isZero | (notZeroMask & res);
  //return 0;
}

观察一下可以发现，判断一个数需要的最高位数，就是负数的最高位0所在的位或正数最高位1所在的位再加上1位符号位。首先排除一下特殊情况，0，只要输入为0，那么直接返回1就行了。然后的方法是使用类似二分法的方法来查找最高位所在位数。

x = (signX & (~x)) | ((~signX) & x);

上面这一行的意思是，当x是负数的时候，x取反，当x是正数的时候，x原样保持，这样做的目的是把，找正数最高位1和找负数最高位0都转换为找最高位1。

  bit_16 = (!((!!(x>>16)) ^ (0x1))) << 4;
  x >>= bit_16;

上面的做法是：当x的高16位有1的时候，直接忽略低16位的数，因为高16位有数字意味着它一定需要超过16位的位数才能表示，因此低16位不需要关心。

当x在高16位有1的时候，bit_16这个变量值为16，否则bit_16为0，意味着上面代码的第二行不需要移动。

同理，可以通过二分的方法，可以找出，这个数在哪一个最高bit范围内有1，并且只保留在那个范围内bit数，然后将这些bit情况变量加起来，就是表示该数最少需要的bit数，由于是补码，因此还需要再加1位符号位。

8 - 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) {
  unsigned sign = (uf >> 31) & (0x1);
  unsigned exponent = (uf >> 23) & (0xFF);
  unsigned fraction = uf&0x7FFFFF;
  //NaN or inf
  if(exponent == 0xFF)
  {
      return uf;
  }
  //denormalize
  if(exponent == 0)
  {
    fraction <<= 1;
    return (sign << 31) | fraction;
  }
  //normalize
  exponent++;
  return (sign << 31) | (exponent << 23) | fraction;
  //return 2;
}

根据以下浮点数表示法可以分几种情况

规格化数
非规格化数
无穷大
NaN 由于浮点数都是二进制数，对于非规格化浮点数，它表示的数字是0.xxxxx因此乘2只需要把尾数(fraction)左移1位就行。而对于规格化数，则可以把指数exponent递增1即可将表示的数字乘2。

9 - 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) {
  unsigned sign = (uf >> 31) & (0x1);
  unsigned exponent = (uf >> 23) & (0xFF);
  unsigned fraction = uf&0x7FFFFF;
 
  //NaN or inf
  if(exponent == 0xFF)
  {
      return 0x80000000;
  }
  //zero or denormalize
  if(exponent == 0)
  {
    return 0;
  }
  //normalize
  int e = exponent - 127;
  fraction = fraction | (1 << 23); //normalize M is 1.xxxx and fill 1 in bit 23
  if(e > 31)
  {
    return 0x80000000;
  }
  else if(e < 0)
  {
    return 0;
  }
  if(e >= 23)
  {
    fraction <<= (e - 23); //zero fill
  }
  else
  {
    fraction >>= (23 - e); //cut off
  }
  if(sign)
  {
    return ~fraction + 1; 
  }
  else
  {
    return fraction;
  }
  //return 2;
}

根据IEEE754的多种情况进行考虑：

值为NaN 或 inf时，按照要求返回0x80000000
值为0或为非规格化数，即值为0.xxxxx时直接返回0 当数表示为规格化数时：

fraction = fraction | (1 << 23);

规格化数表示的值为M = 1.xxxxx其中有一个隐式的1，因此将这个1填在index为23的bit上。

接下来判断e阶码的大小: 当e > 31时，因补码有一位符号位，此时浮点数表示的值已经超过了int32的大小，故直接返回0x80000000 当e < 0时，表示的值小于1，直接返回0 当e >= 23且e < 31时，意味着需要在fraction后面填充0，因此需要左移当e < 23且e > 0时，意味着尾数部分有一部分不能用整数表示，因此需要右移截断

10 - floatPower2

/* 
 * 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) {
  if(x < -149)
  {
    return 0;
  }
  else if(x < -126)
  {
    int shift = 23 + (x + 126);
    return 1 << shift;
  }
  //normalize
  else if(x <= 127)
  {
    int exponent = x + 127;
    return exponent << 23;
  }
  else
  {
    return 0xFF << 23;
  }
    //return 2;
}

题目要求是用FP32表示2^x，由于

V = (-1)^s * M * E E的范围是-126~127，再加上fraction含有的23位，因此浮点数最小可表示的数字是2^-149，x←149直接返回0

当x > -140且x < -126时，E保持-126最小值即e为0，根据x的大小，生成fraction，相当于fraction的最高位1，从第23位向右移-(x+126)位当x ⇐ 127时，此时是FP32规格化表示，M含有一个隐含的1，因此只需要改变E，让E的大小等于x即可。由于E = e - 127有 e = E + 127 = x +127 当出现其他情况即x > 127时，FP32无法表示这么大的数，按照题目要求，直接返回+INF

📔Harson's Notes

探索

CSAPP