CSAPP LAB:data lab

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

( ~ a&~b)_i为1当且仅当a_i为0且b_i为0，若a_i为0则x_i和y_i不可能同时为1，若b_i为0则x_i和y_i不可能同时为0，这两个条件等价于x_i不等于y_i，即为异或的逻辑。

2、实现tmin函数

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */

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

不用解释吧...

3、实现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^(x+1)))&(!!(x+1));
}

~x^(x+1) == 0 iff x == Tmax or x == -1, (x+1) ==0 if x == -1.

4、实现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 mask = (0xAA) | (0xAA << 8);
  mask = mask | (mask << 16);
  return !((x & mask) ^ mask);
}

mask所有奇数位为1，偶数位为0（最左边是第零位），则(x&mask)^mask第i位（奇数位）当且仅当xi==1时为0，且其偶数位全为0，则实现了功能：x奇数位全为1时返回值为!0，即1。

4、实现negate函数

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

反码加一不解释

5、实现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) {
  return !((x+~(0x30)+1)>>31) & !!((x+~(0x3a)+1)>>31);
}

减去两边界判断符号位即可

6、实现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 mask = 0x1;
  int x_symbol = (x>>31)&mask;
  int y_symbol = (y>>31)&mask;
  int isDiff = x_symbol ^ y_symbol;
  int sub_symbol = ((x + (~y) + 1) >> 31) & mask;
  return (x_symbol & isDiff) | (!isDiff & sub_symbol) | (!(x^y));
}

将情况分类：1、x y同号，则x-y直接判断符号位即可，因为x-y不可能溢出 2、x y异号，则判断x是否是负数即可 3、两者相等，直接用异或实现即可

7、实现logicNeg函数

/* 
 * 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) {
  return ((x|(~x + 1))>>31)+1;
}

有且仅有0和其相反数（负0）进行或操作得符号位为正。 实际上最小数的相反数是溢出的，但由于其本身是负数，所以或操作得到的仍然是负数。

8、实现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 b16, b8, b4, b2, b1, b0;
  int sign = x>>31;
  x = (sign&~x)|(~sign&x);//如果x为正则不变，否则按位取反（这样好找最高位为1的，原来是最高位为0的，这样也将符号位去掉了）

  // 不断缩小范围
  b16 = (!!(x>>16))<<4;//高十六位是否有1
  x = x>>b16;//如果有（至少需要16位），则将原数右移16位
  b8 = (!!(x>>8))<<3;//剩余位高8位是否有1
  x = x>>b8;//如果有（至少需要16+8=24位），则右移8位
  b4 = (!!(x>>4))<<2;//同理
  x = x>>b4;
  b2 = (!!(x>>2))<<1;
  x = x>>b2;
  b1 = (!!(x>>1));
  x = x>>b1;
  b0 = x;

  return b16+b8+b4+b2+b1+b0+1;//+1表示加上符号位
}

9、实现float_twice函数

//float
/* 
 * 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) {
  unsigned s, exp, frac;
    s = uf & 0x80000000;//s is the sign bit
    exp = (uf >> 23) & 0x000000ff;//exp is the exponent domain
    frac = uf & 0x007fffff;//get the lowest 23 bits of uf
    if(exp == 255)//NaN or INF
        return uf;
    if(exp == 0)//denormalized floating point number
    {
        if(frac & 0x00400000)//if the first bit of frac is 1
            exp++;
        frac = (frac << 1) & 0x007fffff;
    }
    else
    {
        exp++;
        if(exp == 255)//If 2*uf is INF
            frac = 0;
    }
    return s | (exp << 23) | frac;
}

10、实现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, exp, frac, bitc, tailb;

  if (x == 0) return 0;
  else if (x == 0x80000000) return 0xCF000000;

  sign = (x >> 31) & 1;
  if (sign) x = -x;

  // count bits to the right of MSB
  bitc = 1;
  while ((x >> bitc) != 0)
    bitc++;
  bitc--;

  exp = bitc + 127;

  x = x << (31 - bitc); // clear all those zeros to the left of MSB
  frac = (x >> 8) & 0x7FFFFF;

  // round to even (nearest) 
  if (bitc > 23) {
    tailb = x & 0xFF; // byte to round

    if ((tailb > 128) || ((tailb == 128) && (frac & 1))) {
      frac += 1;
      if (frac >> 23) {
        exp += 1;
        frac = 0;
      } 
    }
  }

  return (sign << 31) | (exp << 23) | frac;
}

11、实现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 exp = (uf >> 23) & 0xFF;
    int frac = uf & 0x007FFFFF;
    int sign = uf & 0x80000000;
    int bias = exp - 127;

    if (exp == 255 || bias > 30)
    {
        // exponent is 255 (NaN), or number is too large for an int
        return 0x80000000u;
    }
    else if (!exp || bias < 0)
    {
        // number is very small, round down to 0
        return 0;
    }

    // append a 1 to the front to normalize
    frac = frac | 1 << 23;

    // float based on the bias
    if (bias > 23)
    {
        frac = frac << (bias - 23);
    }
    else
    {
        frac = frac >> (23 - bias);
    }

    if (sign)
    {
        // original number was negative, make the new number negative
        frac = ~(frac) + 1;
    }

    return frac;
}