终于入坑了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 |
验证:
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 | #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;
}
|
2.tmin
返回最小的二进制补码
补码最小值,C语言中int类型数据是4字节32位,相当于第32位为1,其余位为0
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 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;
}
|
3.isTmax
如果 x 是二进制补码最大值,则返回 1,否则返回 0
以C语言int类型思考,最大值为:
1 | 0111 1111 1111 1111 1111 1111 1111 1111
|
由于不能进行移位操作,所以简化为取头四位和末四位也不影响:
1 2 3 | max : 0111 1111
min : 1000 0000
|
想到最小值和最大值是挨着的,操作就从它两来思考
- !:逻辑非,用于将一个布尔表达式的值取反
- |:按位或,用于对两个整数的每一位进行或操作,如果两个对应位中至少有一个是1,则结果位为1;否则,结果位为0
使用#include <limits.h>来调用min
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | int isTmax( int x)
{
int min = INT_MIN;
int a = min ^ x;
a = ~ a;
return !a;
}
int main()
{
int num,i;
scanf ( "%d" ,&num);
i = isTmax(num);
printf ( "%d\n" ,i);
}
|
检查发现(这里才注意到可以用指令去验证)
限制了字符,不能直接定义INT_MIN
重新思考:
1 2 3 4 5 6 7 | int isTmax( int x)
{
int a = x + 1;
int b = a | x;
b = ~b;
return !b;
}
|
4.allOddBits
如果所有的奇数位都为1则返回1,最左侧为第31位,最右侧为第0位
同样输入(only 0x0 - 0xff allowed)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | int allOddBits( int x)
{
int a = 0xA;
int b = a | (a << 4);
int c = b | (b << 8);
int d = c | (c << 16);
int e = ((d & x) ^ d);
return !e;
}
int main()
{
int num,i;
scanf ( "%X" ,&num);
i = allOddBits(num);
printf ( "%d\n" ,i);
}
|
5.negate
返回相反数
emm,不就是求补码,秒了
1 2 3 4 | int negate( int x)
{
return (~x) + 1;
}
|
6.isAsciiDigit
判断ascii码是否在0到9之间
若x - 0x39为负数的话,说明小于等于0x39内;若0x30 - x为负数的话,说明大于等于0x30
然后都满足则返回1
想到上面求negate相反数,把求-x转化为求 ~x + 1
1 2 3 4 5 | int isAsciiDigit( int x) {
int a = ~((0x30 + ~x + 1) >> 31);
int b = ~((x + ~0x39 + 1) >> 31);
return a & b;
}
|
7.conditional
等价于 x ? y : z
解释:
1 2 3 4 5 6 7 | int conditional( int x, int y, int z)
{
x = !!x;
if (x)
return y;
return z;
}
|
结果检查发现不能用if
重新想:
1 2 3 4 5 6 7 8 9 | int conditional( int x, int y, int z)
{
int a, b, c;
x = !!x;
a = ~x + 1;
b = a & y;
c = ~a & z;
return b | c;
}
|
8.isLessOrEqual
又是解决比较大小,参考isAsciiDigit
1 2 3 4 5 | int isLessOrEqual( int x, int y)
{
int a = ~((y + ~x + 1) >> 31);
return a;
}
|
9.logicalNeg
不用 ! 解决 !x1
1 2 3 4 5 6 | 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
据此做文章:
1 2 3 4 5 6 | int logicalNeg( int x)
{
int a = ~x + 1;
a = a << 31;
return ~a;
}
|
10.howManyBits
表示x的二进制补码的最小位数
逐渐缩小范围来判断'1'
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | int howManyBits( int x)
{
int sign = x >> 31;
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位
1 2 3 4 5 6 7 8 9 10 11 12 | 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;
if (!(e ^ 0xff))
return uf;
e = (((uf >> 23) + 1) << 24 >> 1);
return s + e + m;
}
|
12.floatFloat2Int
将浮点型转换为位级等价整数
NaN和无穷大返回0x80000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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;
if (e > 158)
return 0x80000000;
if (e < 127)
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为指数,就与阶码相关
1 2 3 4 5 6 7 8 9 | unsigned floatPower2( int x)
{
int e = x + 127;
if (e <= 0)
return 0;
if (e >= 255)
return 0x7F000000;
return e << 23;
}
|
Data lab end!!!