DataLab

最近在看CMU15-213的课程(2015),读CSAPP,实践最重要,故此记录做Lab的笔记。
Lab链接

由于服务器使用的CentOS7系统,Make时报错了,故需要先装好依赖

sudo yum install glibc-devel.i686 libgcc.i686 libstdc++-devel.i686

题目及解法

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

异或XOR的结果保存了两个数间的不同位。
那么 :
A & B 可以把相同的1保存下来。
~A & ~B 可以把相同的0保存下来。
(A & B) | (~A & ~B) = 保存了两个数相同的位。
最后再反一次:~( (A & B) | (~A & ~B) ) = 保存了不同位。
根据公式

  1. ~( A | B ) = ~A & ~B
  2. ~( A & B) = ~A | ~B

转换一下得到
A ^ B = ~( (A & B) | (~A & ~B) ) = (~A | ~B) & (A | B)=~(A & B) & ~(~A & ~B)

tmin

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

Tmin即最高位为1,其他全为0,Lab限制在32位,把1左移31位即可

isTmax

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 2
 */
int isTmax(int x) {
  return !(~((x + 1) + x) | !(x + 1));
}

利用|TMin| = TMax + 1
若x为Tmax,则x+1=Tmin,Tmin+x=-1,取反后取非则得0,!(x+1)为0(防止0xFFFFFFFF的情况)

allOddBits

/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
  int odd = 0xAAAAAAAA;
  return !((x&odd)^odd);
}

判断奇数位置的位是否全为1,构造一个奇数位置全为1的数,x与上该数得到非奇数位全为0的数,再与该数异或看是否相等

negate

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

-x = ~x + 1

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) {
  /* (x - 0x30 >= 0) && (0x39 - x) >=0 */
  int TMIN = 1 << 31;
  return !((x + ~0x30 + 1) & TMIN) & !((0x39 + ~x + 1) & TMIN);
}

由上一题,-x=~x+1,我们可以用加法运算完成减法运算;然后与上Tmin来判断是否是负数

conditional

/* 
 * 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 f = ~(!x) + 1;
  int of = ~f;
  return ((y & of) | (z & f));
}

构造类布尔表达式,当x为真,f为0,of为-1

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 signX = (x >> 31) & 1;
  int signY = (y >> 31) & 1;
  int signXSubY = ((y + ~x + 1) >> 31) & 1;
  return (signX & ~signY) | (!(signX ^ signY) & !signXSubY);
}

转化为判断y-x >= 0
确定x、y和y-x的正负,0正1负,再加以判断即可。

  • y正,x负直接返回1
  • 再判断y、x是否异号,若为异号,则直接返回0;否则作同号处理,对相减后的符号位进行取非即可

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 sign = (x >> 31) & 1;
  int TMAX = ~(1 << 31);
  return (sign ^ 1) & ((((x + TMAX) >> 31) & 1) ^ 1);
}

先判断正负,若为负数,直接返回0。否则加上Tmax,看是否溢出,溢出则为正数,返回0,否则为0,返回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) {
   int temp=x^(x>>31);//确保x为正数;
    int isZero=!temp; //是否为0
    //非0掩码 0xffffffff
    int notZeroMask=(!(!temp)<<31)>>31;
    int bit_16,bit_8,bit_4,bit_2,bit_1;
    //二分法查找
    bit_16=!(!(temp>>16))<<4;  //高16位是否有值,有则右移相应位,否则考虑低16位
    temp=temp>>bit_16; 
    bit_8=!(!(temp>>8))<<3; 
    temp=temp>>bit_8;  
    bit_4=!(!(temp>>4))<<2;
    temp=temp>>bit_4;
    bit_2=!(!(temp>>2))<<1;
    temp=temp>>bit_2;
    bit_1=!(!(temp>>1));
    temp=bit_16+bit_8+bit_4+bit_2+bit_1+2;//非0数至少需要一个符号位和一个数值位,即2位
    return isZero|(temp&notZeroMask);
}

float_twice

/* 
 * float_twice - 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 float_twice(unsigned uf) {
  int exp = (uf&0x7f800000)>>23;
  int sign = uf&(1<<31);
  if(exp==0) return uf<<1|sign;
  if(exp==255) return uf;
  exp++;
  if(exp==255) return 0x7f800000|sign;
  return (exp<<23)|(uf&0x807fffff);
}

获取指数部分,符号部分。先排除exp为0和255的情况,无穷大和NaN直接返回uf,无穷小和0只需要将原数乘二再加上符号位就行了(不会越界)。剩下的情况,如果指数+1之后为指数为255则返回原符号无穷大,否则返回指数+1之后的原符号数。

float_i2f

/* 
 * float_i2f - Return bit-level equivalent of expression (float) x
 *   Result is returned as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point values.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned float_i2f(int x) {
    int sign=x>>31&1;  //符号位
    int i;
    int exponent; 
    int fraction; 
    int delta;
    int fraction_mask;
    if(x==0)
        return x;
    else if(x==0x80000000)
        exponent=158;  //1.0 x 2^31,E=31. e=E+127
    else{
        if (sign)//将x化为正数
            x = -x;
        i = 30;
        while ( !(x >> i) )//查看x有多少位
            i--;
        exponent = i + 127;
        x = x << (31 - i);//清除高位的0,将有效部分移到高位
        fraction_mask = 0x7fffff;
        fraction = fraction_mask & (x >> 8);//右移8位与上掩码,得到小数部分
        x = x & 0xff;   //获取移走的低8位,即需舍入的部分
        delta = x > 128 || ((x == 128) && (fraction & 1));//查看低8位是否大于一半,按偶数舍入
        fraction += delta;
        if(fraction >> 23) {//查看舍入后是否溢出
            fraction &= fraction_mask;
            exponent += 1;
        }
    }
    return (sign<<31)|(exponent<<23)|fraction;
}

float_f2i

/* 
 * float_f2i - 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 float_f2i(unsigned uf) {
  int sign = uf>>31;
  int exp = (uf >> 23) & 0xFF;
  int frac = uf & 0x007FFFFF;
  int E = exp-127;

  if (exp == 255 || E>30){
    //exp为255,则NaN;E>30则超出int表示的范围.返回规定的溢出值0x80000000u
    return 0x80000000u;
  } else if (!exp || E<0){
    return 0;
  }

  //添加隐藏的1,规格化
  frac = frac | 1 << 23;
  
  if (E > 23) {
    frac = frac << (E - 23);
  } else {
    frac = frac >> (23 - E);
  }

  if (sign) {
    frac = ~(frac) + 1;
  }

  return frac;
  
}

关于本次实验的思考

这是CSAPP的第一次实验,接下来还有8个Lab等着我,希望我能够坚持下来吧。做本次实验的有以下几点感受:

howManyBits我觉得是最难的,没有什么思路,参考的别人的做法,自己理解了一番。虽然实验过程很坎坷,但是所有代码都搞懂了,以后有机会再二刷吧。本次实验的基础收获当然是关于信息的位级表示相关的内容了,对一些位级运算符更加熟悉了一些。总之一定要多思考、多练。

Q.E.D.


励志成为年薪百块工程师