0x01 实验前的环境部署和操作

安装gcc-multilib插件

由于实验自带的检验和打分等程序是32位程序，而我的虚拟机是Ubuntu64位的，因此安装这个插件来兼容64位系统。

1
sudo apt-get install gcc-multilib

实验步骤简述

我这里用vscode远程连接本地Ubuntu虚拟机，打开datalab-handout文件夹的bits.c文件，根据里面的要求补全函数。

（参考网站：vscode远程连接本地虚拟机；出现无法连接的问题时）

实验结果检验

在linux终端中输入以下命令

1
2
make 编译
./btest 测试

0x02 补全bits.c里的函数思路

01 bitXor

根据异或公式，(~x & y) | (x & ~y)，由于这里不允许使用或|，于是使用摩根定律替换

1
2
3
4
5
6
7
8
9
10
11
//1
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  return ~(~(~x & y) & ~(x & ~y));
}

02 tmin

返回补码数的最小值，就是1开头后面全是0的数

1
2
3
4
5
6
7
8
9
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return (1<<31);
}

03 isTmax

检测是不是int补码数最大值，即0111后面全是1，我发现，只有-1和INT_MAX加1后再与本身异或运算，才有可能是位级表示下全1的数

1
0111 ^ 1000 = 1111 Or 1111 ^ 0000 = 1111

全1的数很好判断，只有取反再测是不是0。这时候只要排除-1的情况就好了，只要x加1后非0，这个数就不是-1。

1
2
3
4
5
6
7
8
9
10
/*
 * 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+1) & !(~((x+1) ^ x));
}

04 allOddBits

如果某个数所有的奇数位是1就返回1，比如0xAA：1010 1010

用0xAA AA AA AA取输入数x的掩码，然后再判断是否与0xAAAAAAAA相等

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * 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 temp = 0xAA;
  temp |= temp << 8;
  temp |= temp << 16;
  return !((x & temp) ^ temp);
}

05 negate

返回一个负数

按照补码运算性质马上就能得出答案，按位取反再加1（最大补码负数的取负还是本身）

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

06 isAsciiDigit

如果是ASCII码下的数字符号就返回1，在0x30到0x39之间

先排除大于0xff的情况，与一个高24位全是1的掩码，之后除了0x3x，再判断低四位，有0xxx，和100x两种情况，分别讨论即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * 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 test_number = (1<<31)>>23;
  return !(x & test_number) & (!((x & 0xf8) ^ 0x30) | !((x & 0xfe) ^ 0x38));
}

07 conditional

x ? y : z 三元运算符，x为真取y，假取z

若x为真，根据x的值来生成一个全1的掩码，跟y与得到y本身；全1的非，即全0，跟z与得到0，最后两者再或运算

得到y，若x为假，同上理得到z。

1
2
3
4
5
6
7
8
9
10
11
/* 
 * 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) {
  int Bool = ((!!x) << 31) >> 31;
  return (Bool & y) | (~Bool & z);
}

08 isLessOrEqual

实现小于或等于号

判断y - x 是否大于或等于0，减法用加逆元来实现（实测发现虽然INT_MIN的逆元是本身，但是能正常运算）。

1
2
3
4
5
6
7
8
9
10
11
/* 
 * 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 test_number = 1 << 31;
  return !(((y + (~x + 1)) >> 31) & test_number) ;
}

09 logicalNeg

不用 ! 来实现 !

0得到1，非0得到0

非0的数的逆元（否定）会翻转符号位，而0不会，于是非0数的否定与本身或运算得到符号位为1的数。

然后再算术右移，若非0则得到-1，为0则得到0，再加1就实现成功。

1
2
3
4
5
6
7
8
9
10
11
/* 
 * 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 + 1) | x) >> 31) + 1; 
}

0A howManyBits

判断某个数，最少可以用多少位级表示，由于x和~x的位级所需位是一样的，所有负数都通过翻转成正数来处理（正数不变）。以下操作可以实现

1
x = x >> 31 ^ x;

之后开始查找第一个1的位置，表示第一个1的位置所需的位级再加上1（符号位），就能返回正确答案。

查找位置的方法用二分查找，每次取中间位置，看看高位是否存在1，若存在再右移x来查找高位，否则不位移来查找低位，记录被右移掉的位数，最后要加到结果中。经过5轮的二分，就能查找到第一个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
/* 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) {
  x = x >> 31 ^ x;
  
  int b16, b8, b4, b2, b1;

  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;

  return b16 + b8 + b4 + b2 + b1 + x + 1;
}

0B float_twice

把一个浮点数乘以2，返回对应的值。

NaN返回本身：exp = 0xff,frac != 0

非规格化：exp = 0, frac <<= 1，与规格化的过渡是平滑的，直接frac左移一位即可

规格化乘以2后溢出：{exp = 0xff，frac = 0} Or {exp = 0xff-1}，return ∞（返回无穷）

规格化未溢出：exp += 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
31
//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 sign = uf & (1 << 31);
  unsigned exp = (uf ^ sign) >> 23;
  unsigned frac = uf & 0x7fffff;

  if(!exp){
    return (uf << 1) | sign;
  }
  else if(!(exp ^ 0xff) && frac){
    return uf;
  }
  else if((!(exp ^ 0xff) && !frac) || !(exp ^ 0xfe)){
    exp = 0xff;
    return sign | (exp << 23);
  }
  else{
    return (uf ^ (exp << 23)) | (exp + 1) << 23;
  }
}

0C float_i2f

（偶数舍入方法：先加上舍弃位的半值，利用四舍五入，小于半值的加上半值也不会进位，移位后自然舍弃，大于半值的加上半值会产生进位，完全符合我们的需求。对于刚好半值，加上半值会进位，但是它比较特殊，加完后舍弃的值是全0，如果最低有效位是1，说明原来是0，不该进位，所以再减1去掉进位。）

（这个有点难，我最后参考了网上的做法）

先把int正数取正（无符号），再算出uf的位数，把其转化为frac表示，然后记录exp，最后合并。

然后后九位要根据向偶数舍入来舍入（如果int部分超过24）。

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
35
36
37
38
39
40
41
unsigned float_i2f(int x){
  unsigned uf, exp;
  unsigned sign = x & (1 << 31);
  unsigned i = 30, t;//i存储的是最高位的向量下标

  if(x==0){
    uf = 0;
  }
  else if(x == 0x80000000){
    uf = 0xcf000000;
  }
  else{
    if(sign){
      uf = ~x + 1;
    }
    else{
      uf = x;
    }
    
    while(!(uf & (1 << i))){
      i--;
    }
    uf = uf - (1 << i);//去掉最高位的1

    if(i < 24){//如果不大于24位，不需要舍入操作
      uf = uf << (23 - i);
    }
    else{
      t = i - 23;
      uf += (1 << (t - 1));   //加即将丢弃的值的一半，四舍五入
      if(uf & ((1 << (t + 1)) - 1)){   //判断奇偶，如果是1后跟着0，说明不该进位。
        uf -= 1;
      }
      uf = uf >> t;
    }
    exp = (127 + i) << 23;
    //这里用加法而不是或运算是可能因为尾数舍入进位
    uf += exp | sign;
  }
  return uf;
}

0D float_f2i

应该是默认向0舍入。

当float数小于1时，直接返回0

当float数大于1，但不溢出int所能表示的范围时（exp 在127到157之间）

先补全小数点前的1，再根据E = exp -1 调整阶数。

当float超过int所能表示的范围，或者是NaN时，按照题意返回 0x8000 0000

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
35
36
37
38
39
40
/* 
 * 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) {
  unsigned sign = uf & (1 << 31);
  unsigned exp = (uf ^ sign) >> 23;
  unsigned frac = uf & 0x7fffff;
  unsigned E;

  if(exp == 0 || (exp >= 1 && exp <= 126)){
    return 0;
  }
  else if(exp >= 127 && exp <= 157){
    E = exp - 127;
    frac |= 0x800000;
    if(E <= 23){
      frac >>= (23 - E);
    }
    if(E > 23){
      frac <<= (E - 23);
    }
  }
  else if(exp >= 158 && exp <= 255){
    return 0x80000000;
  }

  if(sign){
    return ~frac + 1;
  }
  return frac;
}