avatar

目录
Datalab 实验1

我以为这门课的PA项目就已经足够了,没想到吧,中间又穿插着lab实验。

(每次做lab实验都像是在解谜,上一次做的是二进制炸弹,完成的不是很好,有时间重新做一下,再整理成文章发出来)

介绍

实验1主要是在有限制的条件下编写所需要的功能函数,总计12个小函数。

限制条件包括但不限于:

操作限制:不得使用减法等

代码限制:不得使用循环、条件等

数据限制:仅能使用int和unsigned,并且大小限制在0-256之间。

操作数限制:每个函数最多使用特定的操作数个数,超过就不能编译。

……

整个过程

先挑简单的下手……

bitAnd(int a,int b) 1’

用~和|实现&。

c
1
m = ~(~(a)|(~b));

tmax/tmin() 1’

返回最大/最小的二进制补码整数

分别是0x7fffffff和0x8fffffff。

c
1
2
3
4
//最小值可以移位得到
min = 1 << 31;
//最大值就是最小值取反
max = ~(1 << 31);

注意:此次实验右移都是算术右移。

两个一分题解决了,下面来两分的!

negate(int x) 2’

返回负的值,直接取反加一。

最小的负数没法弄,不过参数不应该是这个数,就不管了。

divpwr2(int x,int n) 2’

参考一篇文章:为什么整数中负数的除法和右移不是一回事?

计算x/2^n

==下面全都是错误示例,正确示例请看上面的文章==

我原本想着直接右移就行了,结果答案不正确,这才发现负数的右移结果并不等于它除以2,一直以来我竟然都没有在意过这个细节,今天遇上了。

负数右移,相当于负数+1后再除以2。

对于正数,我们直接右移。

对于负数,我们可以先取反加一,右移,再取反加一。

首先,如何判断正负?

c
1
2
//获取符号位
int s = (x >> 31) & 0x1;

s==1时,取反加一移位再取反加一。

s==0时,移位。

但是,重点是,在条件语句不能使用的情况下,这样的分类能够实现吗?

我觉得很难。

没有条件语句的帮助,我们必须把这两种情况弄成完全一样的步骤,只能在其中的细节上有数值上的不同。

正数是直接右移n位,我们能不能把负数变一变,变成另一个数,这个数右移n位正好是要的结果呢?

c
1
2
3
4
5
6
7
//对于负数
result = ~((~x+1)>>n)+1;
//取反加一,右移n位,再取反加一
//好像“取反”和“右移”是可以交换的???确实是的!
result = ~(~x+1)>>n+1;//负数
result = x>>n;//正数
result = ~(~x+0)>>n+0;//正数

看上面这两行代码,正数和负数的结果就只差了一个1,这个1不就是之前获取的符号位s吗?

所以我们有:

c
1
result = ~(~x + s) >> n + s;

别急!

我以为完美了,没想到一个测试用例n=0,出现了!

好,你厉害!我改还不行吗?

c
1
result = ~(~x + (s&n)) >> n + (s&n);

我又以为没毛病了,又来了一个测试用例:x是最小的负数。

取反加一溢出了!!!

注:补码表示法中,负数比正数多1个

后果就是:

上面我说的一大堆“取反加一”的方法完全失效!

最后乖乖地选择了主流的“偏置法”了……

c
1
result = (x + 2^n - 1) >> n;

byteSwap(int x,int n,int m) 2’

交换第n个和第m个“字节”,注意是字节,一个字节有8位二进制码。

比如交换0x12345678的第一位和第3位,得到0x56341278

下面是我的思路

总体目标是得到下面两个中间值:

0x00340078:把要交换的两项清空。

0x56001200:抠出这两项,并交换位置放置。

第一步:右移,抠出要交换的两小节放在末尾,得到0x12和0x56。

c
1
2
int a = 0xff & (x >> (8*n));
int b = 0xff & (x >> (8*m));

第二步,按照对方的右移位数,再左移回去,并得到0x56001200。

c
1
2
3
a = a << (8*m);
b = b << (8*n);
a = a ^ b;//合并

第三步,在x中把要交换的两项清空,得到0x00340078。

c
1
2
3
4
int c = 0xff << (8*n);
int d = 0xff << (8*m);
c = c ^ d;//合并得到0xff00ff00
c = ~c;//取反更方便后续操作0x00ff00ff

第四步,组合在一起,得到结果。

c
1
result = (x & c) ^ a;

到这里,两分的题目都完成了,大部分时间都在弄那个divpwr2,因为边界条件的问题。而且我很怀疑它可能只有唯一解。

replaceByte(int x,int n,int c) 3’

把x的第n个字节换成c,这就是上面那个交换函数的一部分。不说了,上代码。

c
1
2
3
4
5
int n_8 = n << 3;
int a = 0xff << n_8;
a = ~a;
x = x & a;
x = x ^ (c << n_8);

isLess(int x,int y) 3’

这个很难,折磨了我好长时间,找了各种教程都说的不是很清楚。

我今天非要给它弄懂并讲明白。

第一步就可以分类为同号和异号两种情况。

异号的话直接就是正数大。

c
1
2
3
4
5
6
//获取两个符号
int s1 = 0x1 & (x >> 31);
int s2 = 0x1 & (y >> 31);
result = (s1 ^ s2) & s1;
//s1 ^ s2,两者异或,判断是否相等。
//相等则同号,不等则异号,异号了之后结果与s1相同。

下面看同号,这个最麻烦,要作差,就x-y吧。

不让用减号,那就补码加吧。

c
1
int z = x + ~y + 1;

这里开始出现问题了,由于负数比正数多一个(没错,又是它,总是隔一段时间出来恶心我一下),如果对最小的负数进行取反加一,那么就会溢出,得到错误结果。

我在网上查这道题,没找到一个具体讨论这个恶心的情况的文章。但都通过了?结论就是我因为一些细节没注意到,结果被边界值卡住了。

下面给代码。

c
1
2
3
4
5
6
7
8
9
int isLess(int x,int y)
{
int s1 = 0x1 & (x >> 31);
int s2 = 0x1 & (y >> 31);
int s = s1 ^ s2;//判断二者是否相等
int z = x + ~y + 1;//作差
int r = (s & s1) | ((!s) & (0x1 & (z >> 31)));
return r;
}

所以,虽然0x80000000取反加一后会溢出,但实际上,溢出后还是0x80000000,完全不影响作差的计算,下面说原因。

如果x是0x80000000,y是一个比x大一点的负数,那么作差之后是负数。

如果y是0x80000000,x是一个比y大一点的负数,y取反加一后还是本身,相当于x加上0x80000000,一个负数加上一个负数,结果溢出变成了正数,符号位是0,而x也确实比y大。

综上,取反加一时恶心人的0x80000000根本不影响此题的结果。

那我为什么在这上面耗了大量时间,因为我之前的算法就是错的,同时测试用例都是一些边界值,让我误以为“我算法没问题,就差边界情况没考虑了”。

记住这个教训吧……

rotateleft(int x,int n)

循环左移。

这个貌似也和上面的交换差不多。

举例说明我的思路:

0x12345678,左移8位。

目标是得到一个0x34567800和一个0x00000012。

前者直接由原数左移n位得到。

后者应该:

c
1
2
3
4
5
6
7
int a = (~0) << n;//生成0x11111100
int b = ~a;//变成0x00000011
int c = b << (32 + ~n + 1);//左移到高位
int d = c & x;//把高n位拷贝下来
int e = d >> (32 + ~n + 1);//右移回低位
//注意:c语言对于带符号整数只进行算数右移
int f = e & b;//把可能出现的高的符号位截掉

然后两个数进行 按位或 就行了就可以了。

写到这里我才发现应该使用按位或,而我之前的操作一直把按位异或和按位或搞混了,居然没出现问题。

原因是在这些情况下这两种操作的结果相同,或者说在截断、拼接、拷贝二进制数串时的很多操作的异或、或的效果相同。

以后一定要注意这个细节,更清楚明白到底选哪一种。

三分的题目结束,冲向最后四道题!

bang(int x) 4’

compute !x without using !

想一想,结果返回的只能是1或0,我们猜测在这之前一定有截断操作,即&0x1。

然后想一想,哪一位上的数字能区分0和其他?

不是最后一位,是最高位,因为任何一个数取反加一后最高位都会发生改变,除了0和0x80000000。

0:从0到0

0x80000000:从1到1

其他:从0到1,或从1到0

由此我们可以用“|”操作解决这个问题。

c
1
result = (~((~x + 1) | x) >> 31) & 0x1;

isPower2(int x) 4’

如果是2的幂次,就返回1,否则返回0。

即x的各位数字中1的个数为1或0时,返回1,否则返回0。

2的倍数有个特点,只有一位是1,如何利用这个特点呢?

我没想出来。

网上给出的办法:

x & x-1 == 0

然后接下来就用上面bang的方法了。

另外,还要要求这个数大于0,可以提前判断一下。

所以代码是:

c
1
2
3
4
5
6
int s = 0x1 & (x >> 31);
int a = x + ~1 + 1;
int b = a 7 x;
int r = (~((~b + 1) | b) >> 31) & 0x1;
r = (!s) & r & (!!x);
return r;

float_f2i(unsigned uf) 4’

这个函数是把一个32位无符号数看做单精度浮点数,返回它对应的int的值。

第一步,取出浮点数的三个部分。

c
1
2
3
4
int sign = 0x1 & (uf >> 31);
int exp = 0xff & (uf >> 23);
int frac = (uf & 0x007fffff) ^ 0x00800000;
//补上隐藏位1,隐藏位是0的浮点数都太小了,直接返回0

第二步,判断边界。

c
1
2
3
4
if(exp < 127)
return 0;
else if(exp > 127 + 31)
return 0x80000000u;

第三步,剩下的按照符号位正负分类。

正数直接移动移动(exp-150)位,正则左,负则右。

负数在移动后,还要取反加一变成补码形式。

float_half(unsigned uf) 4’

参数是一个无符号类型的单精度浮点数,要求求出它的实际值的一半并仍然按照无符号类型的单精度浮点数返回。

只要熟悉符号位、阶码、尾数,并了解非规格化与规格化浮点数的定义和区别即可。

第一步,取出浮点数的三个部分。

同上。不放代码了。这次先不补隐藏位。

第二步,分类讨论。

  • exp==0

要变为实际值的一半,直接把尾数右移一位即可,不过要注意一个问题,就是舍入。对浮点数的尾数进行右移操作时,要遵循一个原则,如果最后两位是01,舍去,11,则保留,如果是10就要考虑凑偶数。

即末尾110,移位后要进一位,末尾010,移位后则不进一。

这个细节是在我失败多次后才意识到的,所以做实验前一定要好好看书。

  • exp!=0

规格化数,变为一半,就把阶码减一。

减一之后就要考虑一个问题了,减一之后变成零的话,就不是规格化数了。

如果exp减去1变成零,需要把尾数右归(同时考虑舍入),并且添加隐藏位。

否则,不做其他操作。

结束。

最后

这个实验,12道题,我从早上做到晚上,花费了很长时间,有些问题也确实是绞尽脑汁后去查了网上的答案。

但这不重要,我觉得这个实验的目的值得思考。

和PA的大项目一样,这些实验都是给了你一个完整地框架,然后让你从一些细节开始,一步步完善这个框架,每写完一部分,你对整个框架的理解就会越来越清晰,PA1结束后,你会有一种感觉,“我居然编写了一个ALU!”。

这次的lab实验也是这样,每个函数都在考察一些小细节,每一点你都要注意到,最终一步步完成任务。就像开头说的,lab实验又像是在解密,努力通关,生命无限次。

打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论