Cruyun's Blog

Talk is cheap, show you my code

Data Lab

• 标签: CSAPP

1. 任务内容

通过本次 lab 熟悉整数及浮点数的位表示方式，解开一些 puzzle。

puzzle 主要分为三种类型：位操作、整型运算和浮点数运算。

名称 描述 难度 指令数目
bitAnd(x,y) 只用和 ~ 实现 x & y 1 8
getByte(x,n) 从数 x 中提取第 n 个字节 2 6
logicalShift(x,n) 实现逻辑右移 3 20
bitCount(x) 计算二进制数 x 中 1 的个数 4 40
bang(x) 不使用!而计算!x 4 12
tmin() 返回所能表示的最小整数 1 4
fitsBits(x,n) 如果x可以表示为n位二进制补码形式,则返回1 2 15
divpwr2(x,n) 计算x/(2^n) 2 15
negate(x) 计算 -x 2 5
isPositive(x) x > 0 返回1,x <= 0返回0 3 8
isLessOrEqual(x,y) x <= y 返回 1 否则返回0 3 24
ilog2(x) 返回不超过以2为底x对数的最小整数 4 90
float_neg(uf) 返回和浮点数参数-f相等的二进制数，返回参数本身当参数是NaN时 2 10
float_i2f(x) 实现(float)x，返回x对应浮点数的二进制表示形式 4 30
float_twice(uf) 返回以unsinged表示的浮点数二倍的二进制形式 4 30

2. 上手指南

一共 13 个需要补充的函数，所有的工作都只需修改 bits.c 文件。

任务指示说明

  1. 整型的范围是0~255(0xff)
  2. 只能包含参数和局部变量，不能使用全局变量
  3. 单目运算符：! ~
  4. 双目运算符：& ^ | + << >>

不允许的操作

  1. 使用任何条件控制语句
  2. 定义或使用宏
  3. 定义其他的函数
  4. 调用函数
  5. 使用其他的操作符
  6. 使用类型转换
  7. 使用除 int 之外的类型（针对整型）
  8. 使用除 int, unsigned 之外的类型（针对浮点数）

可以认为机器：

  1. 使用 2’s complent，32位
  2. 执行算术右移（左端补k个有效位）
  3. 移动超过字长的位数会出问题

测试代码

  • 运行 make btest 编译函数
  • 使用 dlc compiler (./dlc) 自动检测你的代码是否符合规定
  • 运行 ./btest 检测函数是否编写成功
  • 使用 ./ishow n 查看n的十六进制，有符号整型和无符号整型形式
  • 使用 ./fshow n 查看n的浮点数表示形式

3. 题目及解法

bitAnd

只用和 ~ 实现 x & y

1
2
3
int bitAnd(int x, int y) {
  return ~((~x) | (~y));
}

摩尔定律 x & y = ~(~(x & y))

getByte

从数 x 中提取第 n 个字节

1
2
3
4
5
int getByte(int x, int n) {
   n = n << 3; //n * 8
   x = (x >> n) & 0xff; // 右移n位
   return x;
}

logicalShift

实现逻辑右移

1
2
3
4
5
int logicalShift(int x, int n) {
  int mask;
  mask  = ~((1 << 31) >> n << 1);
  return (x >> n) & mask; //x右移n位，前n位置0
}

逻辑右移要在原最高位前 n 位置零

bitCount

计算二进制数 x 中 1 的个数

方法一： 采用分治法，把每一位都当成独立的数，并求和。参考链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int bitCount(int x) {
  int tmp, mask1, mask2, mask3, mask4, mask5, sum;
  // mask1: 0x55555555
  tmp = 0x55 | (0x55 << 8);
  mask1 = tmp | (tmp << 16);
  // mask2: 0x33333333
  tmp = 0x33 | (0x33 << 8);
  mask2 = tmp | (tmp << 16);
  // mask3: 0x0f0f0f0f
  tmp = 0x0f | (0x0f << 8);
  mask3 = tmp | (tmp << 16);
  // mask4: 0x00ff00ff
  mask4 = 0xFF | (0xFF << 16);
  // mask5: 0x0000ffff
  tmp = 0xFF | (0xFF << 8);
  mask5 = tmp | (0 << 16);
  sum = (x & mask1) + ((x >> 1) & mask1);
  sum = (sum & mask2) + ((sum >> 2) & mask2);
  sum = (sum & mask3) + ((sum >> 4) & mask3);
  sum = (sum & mask4) + ((sum >> 8) & mask4);
  sum = (sum & mask5) + ((sum >> 16) & mask5);
  return sum;
}
  1. 每1位视为一个数，相邻求和，结果用2位保存。
  2. 每2位视为一个数，相邻求和，结果用4位保存。
  3. 每4位视为一个数，相邻求和，结果用8位保存。
  4. 每8位视为一个数，相邻求和，结果用16位保存。
  5. 右移16位：每16位视为一个数，相邻求和，结果用32位保存。即为最终结果。

为什么要右移呢？以每4位视为一数为例，1001被视为两个数10,01，若要将二者求和，则需要分别将二者从原数中取出，然后相加。掩码0011可以直接取出01，若要取出10，则需要先将10右移到低位。

1
2
3
4
5
So if I have number 395 in binary 0000000110001011 (0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1)
After the first step I have:      0000000101000110 (0+0 0+0 0+0 0+1 1+0 0+0 1+0 1+1) = 00 00 00 01 01 00 01 10
In the second step I have:        0000000100010011 ( 00+00   00+01   01+00   01+10 ) = 0000 0001 0001 0011
In the fourth step I have:        0000000100000100 (   0000+0001       0001+0011   ) = 00000001 00000100
In the last step I have:          0000000000000101 (       00000001+00000100       )

方法二：也是分治法的思想，首先将32位数分为8组，对于每四位数，通过三次移位运算统计每组数中1的个数，然后将前16位与后16位相加，将1的个数浓缩在16位中，再以同样的方法将1的个数整理到8位中，得到最后结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int bitCount(int x) {
  int sum = 0;
  // i = 0x11111111
  int i = 0x11 | (0x11 << 8);
  i = i | (i << 16);
  
  //对于每四位，通过不停的移位运算将前三位的1加到第四位上
  sum += x & i;
  sum += (x >> 1) & i;
  sum += (x >> 2) & i;
  sum += (x >> 3) & i;
  //令i = 0xffff;
  i = 0xff | (0xff<<8);
  //将前16位与后16位相加
  sum = (sum >> 16) + (i & sum);
  //令i = 0x0f0f
  //整理每8位之和
  i = 0x0f | (0x0f<<8);
  sum = ((sum >> 4) & i) + (sum & i);
  //将前8位与后8位相加
  i = 0xff;
  sum = (sum >> 8) + (i & sum);
  
  return sum;
}

bang

不使用!而计算!x 

1
2
3
4
5
int bang(int x) {
  int i = ~x + 1; 
  int j = (i | x) >> 31; //符号相同则为0，不同为1
  return j + 1;
}

零的特殊之处，零和零的相反数首位都是零，-0 = +0 = 0，-x只有在x=0时符号位才不会改变。故只需利用x | (-x) = x | (~x + 1)的符号位即可

tmin

返回所能表示的最小整数

1
2
3
4
int tmin(void) {
  return 0x80 << 24; // 0x80000000
  // return 1 << 31;
}

fitsBits

如果x可以表示为n位二进制补码形式,则返回1

1
2
3
4
5
int fitsBits(int x, int n) {
  int i = 32 + (~n + 1);
  int a = (x << i) >> i;
  return !(x ^ a);
}

左移32-n位，右移32-n位，若不变则 return 1

divpwr2

计算x/(2^n)

1
2
3
4
int divpwr2(int x, int n) {
  int bias = (1 << n) + ~0;
  return (x + ((x >> 31) & bias)) >> n;
}

学习CSAPP第三版 2.3.7内容可知：

无论x正负，结果都是舍入到0。因此正数向下舍入，负数向上舍入。直接右移n位会导致不论正负数都是向下舍入。

当 x 为正数时，直接 x >> n 即可。当 x 为负数时，直接右移会同样向下舍入（前提是补码与无符号数的乘法表示形式相同），所以要增加一个偏移量，然后再右移，使其向上舍入。

negate

计算 -x

1
2
3
int negate(int x) {
  return ~x + 1;
}

按位取反加一得到相反数。
关于2的补码可以看这里

isPositive

x > 0 返回1,x <= 0返回0

1
2
3
4
5
int isPositive(int x) {
  int m = (x >> 31) & 1; // 取符号位
  int i = !!x; // 判断是否为 0
  return i ^ m;
}

isLessOrEqual

x <= y 返回 1 否则返回0

return 1 : x< 0,y > 0 or x - y <= 0

1
2
3
4
5
6
7
8
int isLessOrEqual(int x, int y) {
  int m = (~x + 1) + y; //y-x
  int p = !!(x >> 31); //x的符号位
  int q = !!(y >> 31); //y的符号位
  int i = !(m >> 31); //y-x>=0时i==1
  int j = ! (p ^ q); // 判断是否同号
  return (i & j) | (p & !q);
}

假如直接用x > y => x - y > 0 => x + (~y + 1) > 0这个性质，在-x = x（x = 0x80000000)时会被截断，因为计算机并不是纯数学，加法与可能会溢出。

ilog2

返回不超过以2为底x对数的最小整数。找最高位的1出现的位置，也就是求最高有效位的右边有多少位。

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int ilog2(int x) {
  int mark;
  // 先判断高16位是否有1，出现1则确定最终结果数量级必然大于16
  mark = (!!(x >> 16)) << 4;
  // 判断高8位，一次类推
  mark +=  ((!!(x >> (mark + 8))) << 3);
  mark += ((!!(x >> (mark + 4))) << 2);
  mark += ((!!(x >> (mark + 2))) << 1);
  mark += ((!!(x >> (mark + 1))) << 0);
  mark += (!!mark) + (~0) + (!(1 ^ x)); //考虑x=0
  return mark;
}

解法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int ilog2(int x) {
  int tmp, mask1, mask2, mask3, mask4, mask5, v;
  x = x | (x >> 1);
  x = x | (x >> 2);
  x = x | (x >> 4);
  x = x | (x >> 8);
  x = x | (x >> 16);
  // bitCount  
  tmp = 0x55 | (0x55 << 8);
  mask1 = tmp | (tmp << 16); // 0x55555555
  tmp = 0x33 | (0x33 << 8);
  mask2 = tmp | (tmp << 16); // 0x33333333
  tmp = 0x0F | (0x0F << 8);
  mask3 = tmp | (tmp << 16); // 0x0F0F0F0F
  mask4 = 0xFF | (0xFF << 16); // 0x00FF00FF
  tmp = 0xFF | (0xFF << 8);
  mask5 = tmp | (0 << 16); // 0x0000FFFF
  v = (x & mask1) + ((x >> 1) & mask1);
  v = (v & mask2) + ((v >> 2) & mask2);
  v = (v & mask3) + ((v >> 4) & mask3);
  v = (v & mask4) + ((v >> 8) & mask4);
  v = (v & mask5) + ((v >> 16) & mask5);
  return v + ~0; // x - 1
}

先把有效位右边的所有位都置1，然后计算1的个数。

怎么把所有有效位都置为1呢？把最高有效位不停地移到右边呗。先右移1位，得到11，然后右移2位，得到1111，依此类推。例如 0010 1011 => 0011 1111

float_neg

返回和浮点数参数-f相等的二进制数，返回参数本身当参数是NaN时

1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned float_neg(unsigned uf) {
  unsigned result;
  unsigned m;
	// 最高位取反
  result = uf ^ 0x80000000;
  // 最高位清 0
  m = uf & 0x7fffffff;
  if (m > 0x7f800000) {
    result = uf;
  }
  return result;
}

NaN 时返回 NaN,否则改变符号位

nan.png

float_i2f

实现(float)x，返回x对应的浮点数的32位754标准的二进制存储格式。

此题考查对于IEEE二进制浮点数算术标准（IEEE 754）的掌握

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
unsigned float_i2f(int x) {
	// s 符号位，exp 最高位的位置即指数，franc 记录尾数
  unsigned s = 0, exp = 31, frac = 0, d = 0;
  if (x == 0) return 0;
  
  // 判断正负
  if (x & 0x80000000) {
    s = 0x80000000;
    x = -x;
  }
  while (1) {
    if (x & 0x80000000) break;
      exp -= 1;    //exp记录最高位的位置
      x <<= 1;
  }
  if ((x & 0x000001ff) == 0x180) d = 1;   //最后舍掉的8位若最高位为1且低七位仍有数，要进位
  else if ((x & 0xff) > 0x80) d = 1;
  frac = ((x & 0x7fffffffu) >> 8) + d;   //franc记录尾数
  return s + ((exp + 127) << 23) + frac;
}

float_twice

返回以unsinged表示的浮点数的二倍的二进制形式 

1
2
3
4
5
6
7
unsigned float_twice(unsigned uf) {
  if((uf & 0x7F800000) == 0)   // 若是指数为0情况，非规格化
    return (uf << 1) | (0x80000000 & uf);//特殊情况0x80000000
  else if((uf & 0x7fffffff) >= 0x7f800000)   //若数为NaN
    return uf;
  return uf + 0x00800000;
}

指数位全为0的为非规格化数，指数为1 - Bias，底数为0.f，f表示小数字段。因此加倍时直接左移。规格化的数加倍时指数+1。