CSAPP Note lab1

/*
 * bitAnd - x&y using only ~ and |
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |
 *   Max ops: 8
 *   Rating: 1
 */
// 摩根定律
int bitAnd(int x, int y) { return ~(~x | ~y); }

/*
 * getByte - Extract byte n from word x
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: getByte(0x12345678,1) = 0x56
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int getByte(int x, int n) {
  int mask = 0xff;
  int res = (x >> (n << 3)); //一个字节×8位=左移3
  res = res & mask;
  return res;
}

/*
 * logicalShift - shift x to the right by n, using a logical shift
 *   Can assume that 0 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
// 逻辑右移
// 逻辑右移，右侧补0，见p40
int logicalShift(int x, int n) {
  int mask = ~(((1 << 31) >> n) << 1);
  return mask & (x >> n);
}

/*
 * bitCount - returns count of number of 1's in word
 *   Examples: bitCount(5) = 2, bitCount(7) = 3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 40
 *   Rating: 4
 */
// 这条不懂，具体参考
// https://stackoverflow.com/questions/3815165/how-to-implement-bitcount-using-only-bitwise-operators
int bitCount(int n) {
  n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
  n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
  n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
  return n;
}

/*
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
 */
// 看x是否为0即可
int bang(int x) { return (~((x | (~x + 1)) >> 31)) & 1; }
/*
 * tmin - return minimum two's complement integer
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
// 补码中最小的值为0x100000000
int tmin(void) { return 1 << 31; }
/*
 * fitsBits - return 1 if x can be represented as an
 *  n-bit, two's complement integer.
 *   1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
// 这条一点都不懂：——（
int fitsBits(int x, int n) {
  int shiftNumber = ~n + 33; // 33?
  return !(x ^ ((x << shiftNumber) >> shiftNumber));
}
/*
 * divpwr2 - Compute x/(2^n), for 0 <= n <= 30
 *  Round toward zero
 *   Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
// 参考这篇https://www.tuicool.com/articles/aEjyQnQ
int divpwr2(int x, int n) {
  // all zeros or all ones
  int signx = x >> 31;
  // int mask=(1<<n)+(-1);
  int mask = (1 << n) + (~0);
  int bias = signx & mask;
  return (x + bias) >> n;
}
/*
 * negate - return -x
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) { return ~x + 1; }
/*
 * isPositive - return 1 if x > 0, return 0 otherwise
 *   Example: isPositive(-1) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 3
 */
// 看sign位是否为1和注意零
int isPositive(int x) { return !((x >> 31) | (!x)); }
/*
 * 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;
  int signy = y >> 31;
  int signSame = ((x + (~y)) >> 31) & (!(signx ^ signy));
  int signDiffer = signx & (!signy);
  return signDiffer | signSame;
}
/*
 * ilog2 - return floor(log base 2 of x), where x > 0
 *   Example: ilog2(16) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 90
 *   Rating: 4
 */
// 求最高有效位右边有多少位.
// 首先把最高有效位后面的位全改成1，然后求1的个数bitCount
int ilog2(int x) { // most significant bit
  x = x | (x >> 1);
  x = x | (x >> 2);
  x = x | (x >> 4);
  x = x | (x >> 8);
  x = x | (x >> 16); // eg. 0010 1011 => 0011 1111
  // MSB is x & (~(x >> 1))
  // bitCount
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
  x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
  x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
  return x + ~0; // x - 1
}
/*
 * float_neg - Return bit-level equivalent of expression -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 representations of
 *   single-precision floating point values.
 *   When argument is NaN, return argument.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 10
 *   Rating: 2
 */
unsigned float_neg(unsigned uf) {
  // NaN 和 非规范化的
  if (((uf << 1) >> 24) == 0xFF && ((uf << 9) != 0))
    return uf;
  return (1 << 31) ^ uf;
}
/*
 * 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;
}
/*
 * 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
 */
// 指数位全为0的为非规格化数，
// 指数为1-Bias，底数为0.f，f表示小数字段。因此加倍时直接左移。

// 规格化的数加倍时指数+1。
unsigned float_twice(unsigned uf) {
  if ((uf & 0x7F800000) == 0) { // denormalized
    uf = ((uf & 0x007FFFFF) << 1) | (0x80000000 & uf);
  } else if ((uf & 0x7F800000) != 0x7F800000) { // normalized
    uf = uf + 0x00800000;
  } // NAN
  return uf;
}