更适合北大宝宝体质的 Data Lab 踩坑记

# 解压
tar -xvf datalab-handout.tar
# 进入工作目录
cd datalab-handout
# 编译
make

/usr/include/limits.h:26:10: fatal error: bits/libc-header-start.h: No such file or directory
   26 | #include <bits/libc-header-start.h>
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.
make: *** [Makefile:11: btest] Error 1

# Ubuntu
sudo apt-get install gcc-multilib

# 编译并运行
make && ./btest
# 对某个函数进行单元测试
make && ./btest -f bitXnor
# 对某个函数进行单元测试，且指定测试用例，以 -1 指定第一个参数，依次类推
make && ./btest -f bitXnor -1 7 -2 0xf

# 检查是否符合编码规范
./dlc bits.c

# 对某个函数进行单元测试
./bddcheck/check.pl -f bitXnor
# 检查所有函数
./bddcheck/check.pl
# 检查所有函数，且输出总结信息
./bddcheck/check.pl -g

./driver.pl

make

# 显示 -1 的二进制形式
./ishow -1
# Hex = 0xffffffff,       Signed = -1,    Unsigned = 4294967295

# 以 0x 开头，十六进制表示转整数
./ishow 0xffffffff
# Hex = 0xffffffff,       Signed = -1,    Unsigned = 4294967295

# 带小数点，浮点数转表示
./fshow 12.0
# Floating point value 12
# Bit Representation 0x41400000, sign = 0, exponent = 0x82, fraction = 0x400000
# Normalized.  +1.5000000000 X 2^(3)

# 不带小数点，表示转浮点数
./fshow 12
# Floating point value 1.681558157e-44
# Bit Representation 0x0000000c, sign = 0, exponent = 0x00, fraction = 0x00000c
# Denormalized.  +0.0000014305 X 2^(-126)

# 不带小数点，以 0x 开头，十六进制表示转浮点数
./fshow 0x41400000
# Floating point value 12
# Bit Representation 0x41400000, sign = 0, exponent = 0x82, fraction = 0x400000
# Normalized.  +1.5000000000 X 2^(3)

int bitXnor(int x, int y) {
   return ~(x | y) | ~(~x | ~y);
}

int bitConditional(int x, int y, int z) {
   // 对每一位，如果 x_i 为 1，那么选择 y_i，否则选择 z_i
   return (x & y) | (~x & z);
}

// n << 3 表示 n * 8
int n_byte_mask = 0xff << (n << 3);
int n_byte = x & n_byte_mask;

int byteSwap(int x, int n, int m) {
   // 首先保存原始x，然后在对应的byte上按位与消去，再按位或上交换后的byte
   int origin = x, clip_mask, swap_mask;
   n <<= 3, m <<= 3;
   // 0xff << n 表示将第 n 个字节保留，其他字节清零
   // 取反后，表示将第 n 个字节清零，其他字节保留
   clip_mask = ~((0xff << n) | (0xff << m));
   x &= clip_mask;
   // 先通过右移 n*8 位，将第 n 个字节移动到第 0 个字节，与 0xff 进行与运算，得到第 n 个字节，再左移 m*8 位，即实现将第 n 个字节移动到第 m 个字节
   swap_mask = (0xff & (origin >> n)) << m | (0xff & (origin >> m)) << n;
   // 完形填空
   x |= swap_mask;
   return x;
}

int logicalShift(int x, int n) {
   // 对Tmin（最高位为1）执行同样的右移操作，然后左移一位取反即得所需掩码
   int mask = ~(1 << 31 >> n << 1);
   return x >> n & mask;
}

int cleanConsecutive1(int x) {
   // 左右移动一位成为mask，左侧mask要额外考虑算数右移对最高位的影响
   int right_mask = x << 1;
   int left_mask = x >> 1 & ~(1 << 31);
   x &= ~(right_mask | left_mask);
   return x;
}

int cleanConsecutive1(int x) {
   int t = x & (x << 1);
   return x & ~(t | t >> 1);
   // 或
   // return x ^ (t | t >> 1);
}

int leftBitCount(int x) {
   int ans = 0;
   if (x 最高 16 位均为 1){
      ans += 16;
      x = x << 16;
   }
   if (x 最高 8 位均为 1){
      ans += 8;
      x = x << 8;
   }
   if (x 最高 4 位均为 1){
      ans += 4;
      x = x << 4;
   }
   if (x 最高 2 位均为 1){
      ans += 2;
      x = x << 2;
   }
   if (x 最高 1 位均为 1){
      ans += 1;
      x = x << 1;
   }
   // 对于 32 位全为 1 的情况特判
   if (x == -1){
      ans += 1;
   }
}

int tmin = 1 << 31;
int is_high_16_all_1 = !(~(x & (tmin >> 15)) >> 16)

int leftBitCount(int x) {
   // 采用二分法，注意到返回的ans结果一定可以分解为2的幂次(Power of Two)之和。
   // 所以，每次判断x的高2^n次是否全为1，然后累积相加即可。每次计算完了之后左移相应的位数。
   int tmin = 1 << 31;
   int ans = 0, pt_16, pt_8, pt_4, pt_2, pt_1, is_neg_1;
   pt_16 = (!(~(x & (tmin >> 15)) >> 16)) << 4;
   ans += pt_16;
   x <<= pt_16;
   pt_8 = (!(~(x & (tmin >> 7)) >> 24)) << 3;
   ans += pt_8;
   x <<= pt_8;
   pt_4 = (!(~(x & (tmin >> 3)) >> 28)) << 2;
   ans += pt_4;
   x <<= pt_4;
   pt_2 = (!(~(x & (tmin >> 1)) >> 30)) << 1;
   ans += pt_2;
   x <<= pt_2;
   pt_1 = (!(~(x & tmin) >> 31));
   ans += pt_1;
   x <<= pt_1;
   is_neg_1 = x >> 31 & 1;
   ans += is_neg_1;
   return ans;
}

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

int counter1To5(int x) {
   // 使用异或判断x是否为5，然后根据结果加1或者减4
   int is_equal = !((~x & 5) | (~5 & x));
   return x + !is_equal + ((is_equal << 31 >> 29));
}

int sameSign(int x, int y) {
   // 逻辑右移31位，然后异或，最后取反
   return !((x >> 31) ^ (y >> 31));
   // 或者
   // return !((x ^ y)>>31);
}

int sameSign(int x, int y) {
   // 分别计算x和y的符号位，然后异或判断是否相同
   int sign = 1 << 31;
   int x_sign = x & sign;
   int y_sign = y & sign;
   return !(x_sign ^ y_sign);
}

int mul2 = x << 1; // 或者 x + x
int mul3 = mul2 + x;

int is_overflow = (x ^ mul2) >> 31;
is_overflow |= (mul2 ^ mul3) >> 31;

int x_sign_mask = x >> 31;
int tmin = 1 << 31;
int max_num = x_sign_mask & tmin | ~x_sign_mask & ~tmin;
// 或者
int max_num = ~(x_sign_mask ^ tmin);

int satMul3(int x) {
   // 利用异或判断符号位是否相同（即是否溢出），并生成溢出标志is_overflow(0xffffffff or 0x0)
   // 然后使用位级条件运算，判断是否需要计算溢出后的值。溢出后的值利用Tmin异或得到。
   int is_overflow, mul_2, mul_3, tmin, x_sign_mask;
   mul_2 = x << 1;
   mul_3 = mul_2 + x;
   is_overflow = (x ^ mul_2) >> 31;
   is_overflow |= (mul_2 ^ mul_3) >> 31;
   tmin = 1 << 31;
   x_sign_mask = x >> 31;
   return (~is_overflow & mul_3) | (is_overflow & ~(x_sign_mask ^ tmin));
}

int satMul3(int x) {
   int is_overflow, mul_2, mul_3, tmin, tmax, x_sign_mask;
   mul_2 = x << 1;
   mul_3 = mul_2 + x;
   is_overflow = (x ^ mul_2) >> 31;
   is_overflow |= (mul_2 ^ mul_3) >> 31;
   tmin = 1 << 31;
   tmax = ~tmin;
   x_sign_mask = x >> 31;
   return (~is_overflow & mul_3) | (is_overflow & ((x_sign_mask & tmin) | (~x_sign_mask & tmax)));
}

int isGreater(int x, int y) {
   // 若x,y符号不同，则必有x不为负且y为负
   // 若x,y符号相同，则必有x-y-1不为负（规避x=y的情况）
   int x_sign = x >> 31;
   int y_sign = y >> 31;
   int if_not_sign_equal = !!(!x_sign & y_sign);
   // 如果x-y>=0，则x+~y的符号位为0
   int x_minus_y = x + ~y;
   int if_sign_equal = !(x_sign ^ y_sign) & !(x_minus_y >> 31);
   return if_not_sign_equal | if_sign_equal;
}

int subOK(int x, int y) {
    // 因为x=y+(x-y)，所以x-y溢出等价于 y 和 (x-y)符号均与x符号不同
    // （考虑课本上那张图，大正数相加得负数，大负数相加得正数）
    return !(((x ^ y) & (x ^ (x + ~y + 1))) >> 31) & 1;
}

int trueFiveEighths(int x) {
    // 对于低3位（不能整除8的部分）特殊处理，因为他们会造成小数部分的误差，需要向零舍入
    // 利用书上给的向零舍入只需+2^3-1=7的办法，以x的符号位算数右移形成对于是否加7的mask即可
    int integer = x >> 3, fraction = x & 7;
    return integer + (integer << 2) + (fraction + (fraction << 2) + (x >> 31 & 7) >> 3);
}

unsigned float_half(unsigned uf) {
   // 设置掩码提取各个部分的值，要额外注意浮点数运算存在舍入。
   int sign_mask = 0x80000000, exp_mask = 0x7f800000, frac_mask = 0x7fffff;
   int sign = uf & (sign_mask), exp = uf & exp_mask, frac = uf & frac_mask, round = !((uf & 3) ^ 3);
   if (!exp)
      return sign | ((frac >> 1) + round);
   if (exp == exp_mask) // Inf或者NaN
      return uf;
   if ((exp >> 23) == 1) // 如果Exp=1，那么右移一位后指数位变为0，同时弥补了非规格化数尾数不加 1 的问题，但是还需要额外判断是否需要舍入
      return sign | (((exp | frac) >> 1) + round);
   // 其他情况，直接在exp上减1即可
   return sign | (((exp >> 23) - 1) << 23 & exp_mask) | frac;
}

unsigned float_i2f(int x) {
   unsigned sign = x >> 31 & 1, exp, frac, round;
   int x_exp, frac_mask;
   if (!x) // x=0，会在求x最高非零位时出错，所以特判
      return 0;
   if (!(x ^ (1 << 31))) // x=TMin，会在下一步对x取反过程中出错，所以特判
      return 0xcf << 24;
   if (sign)
      x = -x;
   // x_exp 代表 x 的最高非零位的位置，也即 x 的精度位的最高位的位置
   x_exp = 31;
   while (!(x >> x_exp))
      x_exp--;
   exp = x_exp + 0x7f; // exp+bias
   x <<= (31 - x_exp); // 得到小数部分
   frac_mask = 0x7fffff;
   // 右移 8 位，使得尾数位对齐
   frac = (x >> 8) & frac_mask;
   round = x & 0xff; // 得到要被舍入的小数部分
   frac += ((round > 0x80) || ((round == 0x80) && (frac & 1))); // 等价于判断是否大于128，或者等于128且最低位为1，即向偶数舍入
   // 对于舍入后进位的情况，因为最高位从23变为24，所以要且上一个掩码，而且增加一位阶码
   if (frac >> 23) {
      frac &= frac_mask;
      exp += 1;
   }
   return sign << 31 | exp << 23 | frac;
}

int float64_f2i(unsigned uf1, unsigned uf2) {
    unsigned sign = (uf2 >> 31);
    int exp_mask = 0x7ff;
    int exp = ((uf2 >> 20) & exp_mask) - 1023;
    unsigned frac = ((uf2 & 0xfffff) << 11) | (((uf1 >> 21) & exp_mask)) | (0x80000000); // uf2的低20位+uf1的高11位
    if (exp < 0)
        return 0;
    if (exp >= 31)
        return 0x80000000;
    frac = (frac >> (31 - exp)) & ~(0x80000000 >> (31 - exp) << 1); // 避免算数右移导致的前导 1
    if (sign)
        return -frac;
    return frac;
}

unsigned float_negpwr2(int x) {
    // 不对x先做到阶码位的转换，因为可能会造成溢出，而是直接判断x的范围，然后返回对应的值
    // -x < -149=1-127-23，即最小的非规格化数
    if (x > 149)
        return 0;
    // -x >= 128=255-127，即最大的阶码
    if (x <= -128)
        return 0x7f800000;
    // -x > -127，即规格化数，此时小数全为0，阶码为-x+127
    if (x < 127)
        return (-x + 127) << 23;
    // -x 介于 -127 和 -149 之间，即非规格化数，阶码位全为0
    return 1 << (149 - x);
}

make && ./driver.pl

Correctness Results     Perf Results
Points  Rating  Errors  Points  Ops     Puzzle
1       1       0       2       7       bitXnor
1       1       0       2       4       bitConditional
2       2       0       2       15      byteSwap
3       3       0       2       6       logicalShift
4       4       0       2       8       cleanConsecutive1
4       4       0       2       42      leftBitCount
2       2       0       2       11      counter1To5
2       2       0       2       5       sameSign
3       3       0       2       15      satMul3
3       3       0       2       14      isGreater
3       3       0       2       9       subOK
4       4       0       2       11      trueFiveEighths
4       4       0       2       23      float_half
4       4       0       2       30      float_i2f
4       4       0       2       20      float64_f2i
4       4       0       2       9       float_negpwr2

Score = 80/80 [48/48 Corr + 32/32 Perf] (229 total operators)