CSAPP-2-datalab

2 data lab

2.1 bitXor

x^y only use ~ and &
异或：不相同时为1，相同为0——- 计算不是同时为0情况和不是同时为1的情况 然后进行与
- 例如 x[0011] y[0101]
- 找出同时为1的情况则 x&y = [0001]
- 找出同时为0的情况则相反 ~x[1100] & ~y[1010] = [1000]
- 找出这两种单独情况然后再取非按位与就是异或门实现

代码实现：

1
2
3

int bitXor(int x, int y) {
    return ~(~x&~y)&~(x&y);
}

2.2 tmin

only use ！~ & ^ | + << >>
返回最小补码整数
题目要求机器在32位机器上运行 int的类型位32位
补码最小值为符号位为1 其余为0 即为最小值，因此可以将0X1[00000000,00000000,00000000,00000001] 左移31位。
代码实现：
1
2
3
int tmin(void) {
return 0x1<<31;
}

2.3 isTmax

当输入的数是最大时返回1，其余返回0.
only use !（非） ~（按位取反） & ^ | +
int 32位最大值符号位为0，其余为1 [01111111,11111111,11111111,11111111] 判断x是否和这个值相等
当Tmax 再增加1时会变成[1000…..] Tmin
Tmin[1000] 恰好是Tmax[0111] 的反 除了x = -1[1111] 和y = 0[0000] 外都不满足这个规则，利用[0000] 和[1000]的不相同让结果直接加上它

代码实现：

int isTmax(int x) {
    int y = x + 1;//如果x是Tmax[0111] 则 y = Tmin[1000] 
    x = x + y;//[1111]
    x = ~x;//[0000]
    return !（x + !y）; //如果y=[0000] ->!y=[0001] x + !y = [0001] 最后在取反返回0
    				   //如果y=[1000] ->!y=[0000] x + !y = [0000] 返回1 对答案无影响
}

2.4 allOddBits

如果所有的奇数位都位1 则返回1 [0-31]
only use ! ~ & ^ | + << >>
利用掩码关键是如何提取出x 的奇数位
- 先构造一个奇数位全为1 的数即0xAAAAAAAA
- 任何数与这个数 &后，偶数位全0，奇数位 1的仍然是1，原来是0的则为0.。
- 在与这个数[0xAAAAAAAA]进行异或，满足要求则数转换为0，不满足则非0。

代码实现：

int allOddBits(int x) {
  	int a = 0xaa + (0xaa << 8);
  	int b = a + (a << 16);
  	return !((x & b) ^ b);
}

2.5 negate

求反
Legal ops: ! ~ & ^ | + << >>
1[0001] -1[1111] 阿贝尔群 取反+1

代码实现：

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

2.6 isAsciiDigit

判断是否是ascii数字 0x30 <= x <=0x39
又上题可得 ~x+1 = - x，因此可以由这个实现减法运算
- 减去上下界。上界[0x39] 下界[0x30] 然后再右移31位判断符号位

代码实现：

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

2.7 conditional

x ? y : z 当x 非0时返回 y ，当x = 0时返回 z
- 利用x=[0000]（表示0，返回z的情况）时或x =[1111]（表示非0，返回y 的情况）
- x =~x + 1作用设置为全0 或全1
- 例如 x一开始 [0000] 和 [0001]
- 经过~x 为 [1111] 和 [1110]
- +1 为 [0000] 和 [1111]

代码实现：

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

2.8 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 >> 31;//取符号位
  int b = y >> 31;
  int c = !(a ^ b);//取非，保证相同为1，不同为0
  int d = !((y + (~x + 1)) >> 31);//取非保证：y >= x 为1 y<x 为0
  return (c&d) | (!c&a);//左边条件：符号相等 则返回相减的符号位，右边条件： 符号不相等 若a<0 返回1 >0返回0
}

2.9 logicalNeg

用位运算实现逻辑非 !
0[0000] 和Tmin[1000] 两个补码特殊
0 的符号位与其补码符号位位或为0。 Tmin位或为1 [1000] [1000]—-利用这一点

代码实现：

/* 
 * 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;//左移31后  对于非0数 产生-1[1111] 0产生[0000] 所以+1
}

2.10 howManyBits

返回最小能表示数字X的补码位数
如果是一个正数，则需要找到它最高的一位（假设是n）是1 的则在加上符号位，结果为n+1
如果是负数，则需要知道其最高一位是0的（例如 -3[1101] 和 -3[101] 表示的是一个值，所以最小需要三位来表示）

代码实现：

/* 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;// 取 符号位 如果是负数 则sign为0xFFFFFFFF，否则为0x00000000
  //如果x为正则不变，为负数按位取反（这样好找最高位为1的，原来是最高位为0的，也将符号位去掉了）  
  x = (sign & ~x) | (~sign & x);

  // 二分法 不断缩小范围
  b16 = !!(x >> 16) << 4;//高16位是否存在1
  x = x >> b16;
  b8 = !!(x >> 8) << 3;//剩余的高8位
  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; //+1 是符号位
}

b16 = !!(x >> 16) << 4;x >> 16 将x 右移16位丢掉低16位保留高16位
- ！！ 常见的技巧，用于将一个数转换为逻辑值用来检查移动后的整数是否为0 ，即检查原来高165为是否存在1 。
- << 4 如果移动后不为0 那么！！的结果为1，左移4位即 1 << 4 将其转为相应计数为 16 [1000]
模拟一下12[00000000,00000000,00000000,00001100]
- sign = 0x00000000 然后x = 12[00000000,00000000,00000000,00001100]
- b16 = 0 ， x = [00000000,00000000,00000000,00001100]
- b8 = 0 ， x = [00000000,00000000,00000000,00001100]
- b4 = 0， x= [00000000,00000000,00000000,00001100]
- b2 =2[10] , x = [00000000,00000000,00000000,00000011]
- b1 = 1[1] , x = [00000000,00000000,00000000,00000001]
- b0 = 1 ,
- return 2+1+1+1 = 5

2.11 floatScale2

求2乘以一个浮点数若uf为NaN 或无穷大则直接返回否则计算uf * 2返回。
特殊情况：无穷小、 0 、无穷大和非数值NaN 此时这些浮点数的指数部分分别存储为 0、 0、 255 、255，因此无穷大和NaN则直接返回就行，无穷小和0只需要在原数乘二然后再加上符号位就可以（因为不会越界）

代码实现：

//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) {
  int sign = uf & (1 << 31);//符号位
  int exp = (uf & 0x7f800000) >> 23; //0x7f800000 浮点数最大值  与uf做于 截取出 exp的数据
  //特殊情况
  if (exp == 0) return uf << 1 | sign;//指数为0  直接返回乘以2 的值 左移一个即乘以2
  if (exp == 255) return uf;//无穷大或NaN 直接返回
  exp++;//指数加一，相当于乘二 相当于左移一位
  if (exp == 255) return 0x7f800000 | sign; //指数加一后为255 
  return (exp << 23) | (uf & 0x807fffff); //否则 返回指数+1后和 原来数其他位的结果 也就是乘以2的结果
}

2.12 floatFloat2Int

实现 (int)uf 将浮点数转为整数
溢出返回0x80000000u
偏置值127 在单精度浮点数中偏置值为2^(k-1)-1，其中单精度指数部分占了 8为所以 2^（8-1）-1=127
在单精度浮点表示中，尾数（即有效数字）部分的位数是 23 位。当对浮点数进行整数转换时，需要考虑到指数部分的影响。如果指数部分大于 23，意味着尾数部分需要左移，以便将小数部分转换为整数。

这是因为指数的值实际上代表了小数点向左或向右移动的位数。如果指数大于 23，表示小数点要向左移动超过尾数部分的位数，因此需要将尾数左移，以保留整数部分。左移的位数是指数值减去 23，因为每左移一位，相当于乘以 2 的一次方。

代码实现：

/* 
 * 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) {
  int sign = uf >> 31;//符号位
  int exp = ((uf & 0x7f800000) >> 23) -127;//-127 偏置值
  int frac = (uf & 0x007fffff) | 0x00800000; //尾数 并且补上隐藏的1 得到完整的整数
  if (!(uf & 0x7fffffff)) return 0;//如果uf=0 则return 0
  if (exp > 31) return 0x80000000; //如果指数大于31 则返回溢出值 因为整数int为32位
  if (exp < 0) return 0;//指数小于0 小数部分无法表示 返回0
    
  if (exp > 23) frac <<= (exp - 23);//exp大于23   需要将小数位左移
  else frac >>= (23 - exp);

  if (!((frac >> 31) ^ sign)) return frac; //符号相同则返回原值
  else if (frac >> 31) return 0x80000000;//如果为负（即原来为正），返回溢出值
  else return ~frac + 1;//如果为正（原来为负），返回相反数
}

2.13 floatPower2

求2.0^x
exp <= 0 指数部分太小而无法用单精度浮点数表示

代码实现：

/* 
 * 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) {
  int exp = x + 127; //把x当作真指数
  if (exp <= 0) return 0; // 0 < 原数<1 返回0
  if (exp >= 255) return 0x7f800000;//溢出
  return exp <<23; //否则x作为正常的数 有效范围 则exp 左移23位  将指数部分放在合适的位数上
}