[原创]Data lab

发表于: 2024-8-30 20:23 1822

[原创]Data lab

Sh4d0w

2024-8-30 20:23

1822

终于入坑了CSAPP的lab

官方直通车：CS：APP3e、布莱恩特和奥哈拉隆 (cmu.edu)

学习网站：实验 1：Data Lab | 深入理解计算机系统（CSAPP） (gitbook.io)

A thousand-mile journey begins with the first step.(千里之行始于足下)

Let's start！

lab内容

用一个非常有限的C语言子集实现简单的逻辑和算术运算函数

函数名	功能实现	要求
bitXor(x,y)	x ^ y	最大操作数14，只能用 ~ 和 & 运算符，返回结果
tmin()	最小的整数补码	最大操作数4，！~ & ^ \| + << >>
isTmax(x)	如果 x 是二进制补码最大值，则返回 1，否则返回 0	最大操作数10，只能用！~ & ^ \| +
allOddBits(x)	x 的奇数位都为 1 时为真，最左侧为第31位，最右侧为第0位	最大操作数12，！~ & ^ \| + << >>
negate(x)	使用操作符返回 -x	最大操作数5，! ~ & ^ \| + << >>
isAsciDigit(x)	0x30⩽x⩽0x39 时为真	最大操作符15，! ~ & ^ \| + << >>
conditional	等同于 x ? y : z	最大操作符16，! ~ & ^ \| << >>
isLessOrEqual(x, y)	x⩽y时为真，否则为假	最大操作符24，! ~ & ^ \| << >>
logicalNeg(x))	计算 !x	最大操作数12，不用 ! 运算符
howManyBits(x)	表示x的二进制补码的最小位数	最大操作符90，! ~ & ^ \| + << >>
floatScale2(uf)	计算 2 * uf，若 uf 为特殊值值时，直接返回 uf	最大操作符30，Integer/unsigned 相关运算；\|\|，&&，if 和 while 等判断语句
floatFloat2Int(uf)	将浮点数 uf 转换成整数	最大操作符30，Integer/unsigned 相关运算；\|\|，&&，if 和 while 等判断语句
floatPower2(x)	使用浮点数表示 2^x^。无法表示时：过小返回 0，过大返回 +INF	最大操作符30，Integer/unsigned 相关运算；\|\|，&&，if 和 while 等判断语句

lab过程

1.bitXor

用按位与 & 和按位取反 ~ 实现按位异或 ^

先解释一波：

&：当两个操作数的对应位都是1时，结果位为1，否则为0
~：相当于求该整数的补码
^：当两个操作数对应位不同时，结果位为1，否则为0

先用的二进制数据去凑，正数凑出来满足~ ( ~ x & ~ y)

但是用负数验证又不对，想了一下使用真值表法进行操作

x	y	~x	~y	x & y	~x & ~y	~ (x & y)	~ (~x & ~y)	~ (x & y) & ~ (~x & ~y)	目标结果x ^ y
0	0	1	1	0	1	1	0	0	0
0	1	1	0	0	0	1	1	1	1
1	0	0	1	0	0	1	1	1	1
1	1	0	0	1	0	0	0	0	0

验证：

#include <stdio.h>
 
int bitXor(int x, int y)
{
    return ~(~x & ~y) & ~(x & y);
}
 
int main()
{
    int a;
    int b;
    printf("input two number:\n");
    scanf("%d %d", &a,&b);
 
    printf("%d\n", a ^ b);
    int c = bitXor(a, b);
    printf("%d\n", c);
    return 0;
}
// input two number:
// 11 12
// 7
// 7
 
// input two number:
// -7 -1
// 6
// 6
 
// input two number:
// -2 11
// -11
// -11

2.tmin

返回最小的二进制补码

补码最小值，C语言中int类型数据是4字节32位，相当于第32位为1，其余位为0

int tmin(void)
{
    int min = 1;
    min = min << 31;
    return min;
}
 
void print_binary(int num)
{
    for (int i = 31; i >= 0; i--)
    {
        int bit = (num >> i) & 1;
        if ((i + 1) % 4 == 0)
            printf(" ");
        printf("%d", bit);
    }
    printf("\n");
}
 
int main()
{
    int min = tmin();
    printf("%d\n",min);
    print_binary(min);
    return 0;
}
 
// -2147483648
// 1000 0000 0000 0000 0000 0000 0000 0000

3.isTmax

如果 x 是二进制补码最大值，则返回 1，否则返回 0

以C语言int类型思考，最大值为：

1	`0111` `1111` `1111` `1111` `1111` `1111` `1111` `1111`

由于不能进行移位操作，所以简化为取头四位和末四位也不影响：

max:0111 1111
 
min:1000 0000

想到最小值和最大值是挨着的，操作就从它两来思考

!：逻辑非，用于将一个布尔表达式的值取反
|：按位或，用于对两个整数的每一位进行或操作，如果两个对应位中至少有一个是1，则结果位为1；否则，结果位为0

使用#include <limits.h>来调用min

int isTmax(int x) // 假设为max 0111 1111
{
    int min = INT_MIN;// 1000 0000
    int a = min ^ x; // 1111 1111
    a = ~ a; // 0000 0000
    return !a; // 1
}
 
int main()
{
    int num,i;
    scanf("%d",&num);
    i = isTmax(num);
    printf("%d\n",i);
}
// 2147483647
// 1
 
// -1
// 0
 
// 1000
// 0

检查发现(这里才注意到可以用指令去验证)

限制了字符，不能直接定义INT_MIN

重新思考：

int isTmax(int x) // 假设为max 0111 1111
{
    int a = x + 1; // 1000 0000
    int b = a | x; // 1111 1111
    b = ~b; // 0000 0000
    return !b;
}

4.allOddBits

如果所有的奇数位都为1则返回1，最左侧为第31位，最右侧为第0位

同样输入(only 0x0 - 0xff allowed)

int allOddBits(int x)
{
    int a = 0xA; // 1010
    int b = a | (a << 4); // 1010 x 2
    int c = b | (b << 8); // 1010 x 4
    int d = c | (c << 16); // 1010 x 8
    int e = ((d & x) ^ d); // 若是，则e为0
    return !e;
}
int main()
{
    int num,i;
    scanf("%X",&num);
    i = allOddBits(num);
    printf("%d\n",i);
}
// 0xAAAAAAAA
// 1
 
// 0xaaa
// 0

5.negate

返回相反数

emm，不就是求补码，秒了

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

6.isAsciiDigit

判断ascii码是否在0到9之间

若x - 0x39为负数的话，说明小于等于0x39内；若0x30 - x为负数的话，说明大于等于0x30

然后都满足则返回1

想到上面求negate相反数，把求-x转化为求 ~x + 1

int isAsciiDigit(int x) {
    int a = ~((0x30 + ~x + 1) >> 31);
    int b = ~((x + ~0x39 + 1) >> 31);
    return a & b;
}

7.conditional

等价于 x ? y : z

解释：

若x为真，则返回y，否则返回z

int conditional(int x, int y, int z)
{
    x = !!x; // 把x限制为0或1
    if(x)
        return y;
    return z;
}

结果检查发现不能用if

重新想：

int conditional(int x, int y, int z)
{
  int a, b, c;
  x = !!x;    // 把x限制为0或1
  a = ~x + 1; // a为全0或者全1
  b = a & y; // 若x为真，b = y, 否则为0
  c = ~a & z; // 若x不为真，c = z，否则为0
  return b | c;
}

8.isLessOrEqual

又是解决比较大小，参考isAsciiDigit

int isLessOrEqual(int x, int y)
{
    int a = ~((y + ~x + 1) >> 31);
    return a;
}

9.logicalNeg

不用 ! 解决 !x1

X=0
~X + 1 0000 0000
X=1
~X + 1 1111 1111
x=-1
~x + 1 0000 0001

可以发现，~x + 1后的数据，非0的第0位是1，0的第0位是0

据此做文章：

int logicalNeg(int x)
{
    int a = ~x + 1;
    a = a << 31;
    return ~a;
}

10.howManyBits

表示x的二进制补码的最小位数

逐渐缩小范围来判断'1'

int howManyBits(int x)
{
    int sign = x >> 31;               // x为负数则是-1，否则0
    int a = (x ^ sign) + (~sign + 1); // 把负数绝对值
    int a16, a8, a4, a2, a1, min_bits;
 
    a16 = !!(a >> 16) << 4;
    a >>= a16;
    a8 = !!(a >> 8) << 3;
    a >>= a8;
    a4 = !!(a >> 4) << 2;
    a >>= a4;
    a2 = !!(a >> 2) << 1;
    a >>= a2;
    a1 = !!(a >> 1);
 
    min_bits = a16 + a8 + a4 + a2 + a1 + 1;
 
    return min_bits;
}

11.floatScale2

32bit的float变量(IEEE 754标准)

参考文章：float浮点数的二进制存储方式图解（IEEE-754标准）_float的二进制格式-CSDN博客

例如：5.25 => 0101.01 => 1.0101 * 2^2^

符号位：正数为0，负数为1
指数位(又叫阶码)：就像例如中的指数2，再加上127，然后转为二进制
尾数部分：例如中的小数部分，后面补0占满23位

有特殊的1：例如：5.20 => 0101. 0011 0011 0011...(无限循环) => 1.01 0011 0011 0011…… * 2^2^

这种情况下，尾数部分无限循环，只取23位(这就是float的精度体现)

有特殊的2：上述例子都是规格化float，还存在非规格化float

两者的区别在于阶码的值以及尾数的表示方式。规格化数的阶码非零且隐含1，而非规格化数的阶码为零且无隐含1
规格化浮点数 用于表示绝大多数浮点数，具有较高的精度

非规格化浮点数 用于表示非常小的数，精度较低，但能表示的范围更广

有特殊的3：无穷大，符号位：正无穷大为0，负无穷大为1；阶码：全部为1，即11111111；尾数：全部为0

有特殊的4：NaN(非数值)，用于表示未定义或无法表示的数值，如无效操作的结果。符号位无意义，阶码全为1，尾数至少有一个1

do

将传来的参数当成float的位级表示，返回浮点数乘2的位级表示，如果是NAN(非数值)和极大值(阶码全部为1)则返回本身

对于常规化float，乘2只需要将阶码+1，其它位保持不变

对于非常规化float，乘2需要左移1位

unsigned floatScale2(unsigned uf)
{
    unsigned int s = ((uf >> 31) << 31);      // 获得符号位
    unsigned int e = ((uf >> 23) << 24 >> 1); // 获得阶码
    unsigned int m = ((uf << 9) >> 9);        // 获得尾数
    if (e == 0)
        return (uf << 1) | s;          // 非规格化数左移1位变为两倍，再恢复其符号位
    if (!(e ^ 0xff))
        return uf;                     // 无穷大和NaN直接返回
    e = (((uf >> 23) + 1) << 24 >> 1); // 获得阶码+1
    return s + e + m;
}

12.floatFloat2Int

将浮点型转换为位级等价整数

NaN和无穷大返回0x80000000

int floatFloat2Int(unsigned uf)
{
    unsigned int s = ((uf >> 31) << 31);      // 获得符号位
    unsigned int e = ((uf >> 23) << 24 >> 1); // 获得阶码
    unsigned int m = ((uf << 9) >> 9);        // 获得尾数
    m += 0x800000;                            // 加上隐含的1
    if (e > 158)                              // 超限，包括NaN和无穷大
        return 0x80000000;
    if (e < 127) // 这个float数据整数部分为0
        return 0;
    if (e >= 150) // 较大的浮点数
        m = (m << (e - 150));
    else // 较小的浮点数
        m = (m >> (150 - e));
    if (s)
        return -m;
    else
        return m;
}

解释一下为什么是150分别较大较小数据：

尾数有23位，即它能表示的最小单位是 2^-23^
如果 e - 127 = 23，这意味着浮点数的整数部分会刚好扩展到第 23 + 1 位（1 是隐含位）。也就是说，所有位都用来表示整数部分
如果e >= 150的话，尾部所有位都用来表示了整数，只需要左移(e - 150)即可表示位级等价整数
如果e < 150，尾部不是所有位都用来表示整数，表示整数的部分靠左，右移(150 - e)即可

13.floatPower2

得到 2.0^x 的准确浮点数位级表示

无法表示时：过小返回 0，过大返回 +INF(正无穷大)

想到x为指数，就与阶码相关

unsigned floatPower2(int x)
{
    int e = x + 127; // 得到阶码
    if (e <= 0) // 结果太小
        return 0;
    if (e >= 255) // 结果太大，超出了float 2^x的范围
        return 0x7F000000;
    return e << 23; 
}