突发奇想，重做下CSAPP的lab，顺便把以前没做完的补上，希望能坚持下来

Intro

  • datalab主要是使用位运算来实现函数，考验对底层数据类型的掌握
  • 修改bit.c文件以彰显你的位运算技术
  • 32bit

Solution

bitXor

  • 用位与和位非实现位异或
  • 德摩根律走起
1
2
3
int bitXor(int x, int y) {
  return ~(~(~x & y) & ~(x & ~ y));
}

tmin

  • 要求返回最小的补码值0x10000000
1
2
3
int tmin(void) {
  return 1 << 31;
}

isTmax

  • 判断是否是补码最大值
  • 由tmax的特征可得，特判0xFFFFFFFF
1
2
3
int isTmax(int x) {
  return !(((x + 1) ^ x) ^ ~0x0) & !!(~x);
}

allOddBits

  • 要求判断所有奇数位是否都为1
  • 先取奇数位
  • 再判断是否与0xAAAAAAAA相同
1
2
3
int allOddBits(int x) {
  return !((x & 0xAAAAAAAA) ^ (0xAAAAAAAA));
}

negate

  • 求一个数的负数
  • ~x + 1取反加一，常见的转换了
1
2
3
int negate(int x) {
  return (~x + 1);
}

isAsciiDigit

  • 判断是否是Ascii码的0-9，0x30 <= x <= 0x39
  • 分三个条件
  • 前26位为0
  • 形如0x3*
  • 最后四位减去10，符号位为1
1
2
3
4
5
6
7
8
9
int isAsciiDigit(int x) {
  int cond1 = !(x >> 6);

  int cond2 = !((x & 0x30) ^ (0x30));

  int cond3 = !!(((x & 0xF) + (~0xA + 1))>>31);

  return cond1 & cond2 & cond3;
}

conditional

  • 实现?运算符
  • 1取反加一为0xFFFFFFFF，0取反加一再取反为0x0，通过掩码实现选择
1
2
3
4
int conditional(int x, int y, int z) {
  x = !!x;
  return (~x + 1) & y | ~(~x + 1) & z;
}

isLessOrEqual

1
2
3
4
5
6
7
8
9
10
11
12
* 实现<=
* 主要思想是x-y的符号位
* 要防止整型溢出
int isLessOrEqual(int x, int y) {
  int sub = x + (~y + 1);
  int xf = !(x >> 31);
  int yf = !(y >> 31);
  int sf = !(sub >> 31);
  int flag1 = (!xf & yf);    //x- y+ x
  int flag2 = !(xf & !yf);
  return flag2 & (!sf | !(x ^ y) | flag1);
}

logicalNeg

  • 实现逻辑非!
1
2
3
4
int logicalNeg(int x) {
  int sign = x | (~x + 1);
  return (sign >> 31) + 1;
}

howManyBits

  • 通过二的倍数不断逼近，得到所需位数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int howManyBits(int x) {
  int b16,b8,b4,b2,b1,b0;
  int sign = x >> 31;
  x = (sign & ~x)|(~sign & x);
  b16 = !!(x>>16)<<4;
  x = x >> b16;
  b8 = !!(x>>8)<<3;
  x = x >> b8;
  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;
}

floatScale2

  • 实现IEEE浮点数*2
  • 对非规格化，
  • 对NaN返回本身
  • 对计算后expr超过255的返回正负无穷
  • 否则expr++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
unsigned floatScale2(unsigned uf) {
  unsigned fraction = uf & 0x007FFFFF;
  unsigned exponent = (uf >> 23) & 0xFF;
  unsigned sign = uf & (0x1 << 31);

  if (exponent == 0) {
    // 非规格化
    return uf << 1 | sign;
  }
  if (exponent == 255) {
    // NaN
    return uf;
  }
  exponent = exponent + 1;  
  if (exponent == 255) {
    return 0x7f800000 | sign;
  }
  return sign | (exponent << 23) | fraction;
}

floatFloat2Int

  • 实现浮点数转int
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int floatFloat2Int(unsigned uf) {
  int fraction = (uf & 0x007fffff) | 0x00800000;
  int exponent = ((uf >> 23) & 0xFF) - 127;
  int sign = uf >> 31;
  if (exponent > 31) {
    return 0x80000000;
  }
  if (exponent < 0) {
    return 0x0;
  }
  if (exponent > 23) {
    fraction = fraction << (exponent - 23);
  } else {
    fraction = fraction >> (23 - exponent);
  }
  if(!((fraction >> 31) ^ sign)) return fraction;
  else if(fraction >> 31) return 0x80000000;
  else return ~fraction + 1;
}

floatPower2

  • 实现2.0^x的IEEE浮点数
1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned floatPower2(int x) {
  if (x < -149) {
    return 0;
  } else if (x < -126) {
    int shift = 23 + (x + 126);
    return 1 << shift;
  } else if (x <= 127) {
    int expr = x + 127;
    return expr << 23;
  } else {
    return (0xFF) <<  23; 
  } 
}