My journals

Menu of journals
About me
Websites

 

 

 


datalab说明文档

        datalab说明文档

1. int bitAnd(int x, int y)   在没有&操作的情况下实现两个数得按位与操作,根据公式 x & y = ~(~x | ~y) 易得结 果。例如:0x8000FFFF & 0x77777777 = ~(0x7FFF0000 | 0x88888888) = ~0xFFFF8888 = 0x00007777

2. int getByte(int x, int n)   在x的二进制表示从后往前中抽出第n个字节的数,由于一个字节对应8个比特,而16进 制表示中每一位数字表示的是4个比特,所以一个字节对应的是16进制中的相邻两位。如第0个 字节,就是16进制的后两位;第1个字节就是16进制的倒数第三位和倒数第四位。为了抽出16 进制中的两位数字,只需要将对应数字右移至末尾,再与0xFF作&操作。而为了将对应数字移至 末尾,我们需要右移n个字节,即8*n个bit位,也就是 n << 3 。       例如:x = 0x77778FFFF, n = 1时,n << 3 = n*8 = 8, x >> 8 = 0x0077778FF, 0x0077778FF & 0xFF = 0xFF 。

3. int logicalShift(int x, int n)      逻辑右移,由于逻辑右移在符号位为0时与算术右移无差别,而在符号位为1时右移 时补 足的位仍然是0, 所以需要根据符号位进行判断。大致思路是,首先提取出x的符号位,保持符号 位的位置不变,其他位置为0。然后对x进行算术右移,需要进行操作的是算术右移时补足的位, 右移n位,补足的位数是n – 1位, 再使表示符号位的数右移n – 1位,(为了避免n = 0 时产生 特殊情况,右移n – 1位的实现方法为右移n位再左移1位),两个数再取异或。对0取异或为本 身,对1取异或为取反,所以如果补足的符号位是1时,符号位右移n – 1时补足的位仍然为1, 这样取异或时,可以使补足的1变为0;如果补足位为0时,与0取异或仍然是本身。对于非补足 位,与0异或仍然是本身。   例如:x = 0x8000FFFF,n = 4时,((x >> 31) << 31) = 0x80000000,(x >> 3) = 0xF8000FFF, (0x80000000 >> 4) << 1 = 0xF0000000, 0xF8000FFF & 0xF0000000 = 0x08000FFF 。

4. int bitCount(int x) 计算二进制表示时1的个数。为了在40个操作数之内完成,所以不能采用移一位算一位的方 法。所以需要设计一些方法使原来的方法得到简化。而我这里设计了0x11111111这样一个数,可 以使得四个比特位能够同时比较,也就是用0x11111111与x进行与操作,然后将x右移一位,再 与0x11111111进行与操作,总共右移三次,然后将得到的数字相加,这样每四位的1的个数就存 在结果的十六进制表示时的八个数字上,接下来只需要将这8个数字相加就能得到结果。因为16 进制表示时每位上的数字不会超过4,所以我们可以先让这个结果右移16位和原来得结果相加, 这样得到的新结果的后4位上的数字之和为整个x二进制1的个数。同理,每个位数上的数字不 会超过8。但是同样的方法不能够再使用了,因为如果再将新结果右移8位相加后,每个位数上 的数字表示的是原二进制16个位数上的1的个数,这个个数是会超过15的,这样的话一个位置 的16进制的数字是没有办法表示16的。所以这里我们需要换一种方式来相加,我们设计了数字 0x00000F0F,新结果与这个数字进行与操作,新结果再右移4位再和0x00000F0F与操作,两者 的与结果相加,这样两个byte表示的数字之和就是x二进制的1个数,此时一个byte表示的数字 是可以大于等于16的,最后的只需要将两个byte相加再和0x3F(因为1的个数不会超过32,保证 二进制第六位及一下都是1,所以设计的是0x3F)进行与操作就能得到最后的答案。后两个byte位 的相加也很简单,只需要将数字右移一个byte然后和原数相加那么得到最后一个的byte就是最后 答案,由于1的个数不会超过32个,所以放心的使用byte来存储吧!   例如:x = 0x8000FFFF,0x8000FFFF&0x11111111 = 0x00001111,再将0x8000FFFF依次移位 再与0x11111111进行与操作,得到结果分别为,0x00001111,0x00001111,0x10001111,相加之 后的结果为 0x10004444,右移16位之后和本身相加为,0x10005444,和0xF0F与操作之后是 0x404,右移4位之后和0xF0F与操作的结果为0x504,相加之后的结果为0x908,在右移8位之 后与本身相加 0x11,再和0x3F与操作之后为0x11,十进制结果为17 。

5. int bang(int x)   判断x是否为0,0返回1,否则返回0。我使用的大致判定规则是一个数的相反数的符号和 自己的符号是否是一样的,得到相反数的方法就是取反加一,而得到符号的方法更简单,就是右 移31位,除了0x80000000这个特殊的数之外其余的数都能用这个规则判定。为了也能判定这个 特殊的数,我们只需要稍微改进一下判定规则即可。我们注意到0的符号位是1而这个特殊的数 的符号位为1所以我们得到某个数的符号位和其相反数的符号位之后,进行或操作,这样这个数 和其相反数保证必须同时为0,最后取反,那么最后一位的值必然是我们的结果,最后和0x1进 行与操作去掉没有用的其他位的数字,就能得到最后需要的结果。

6.   例如:x = 0x80000000,x >> 31 = 0x1,~x + 1 = 0x80000000,(~x + 1) >> 31 = 0x1,0x1|0x1 = 0x1,~(0x1) = 0xFFFFFFFE,0xFFFFFFFE&0x1 = 0x0,返回0 。

7. int tmin(void)   返回32位int中的最小值。很明显,最小值的表示方式是0x80000000,只需要将0x80左 移24位就能得到int中的最小值。 (0x80) << 24 = 0x80000000,此结果即为32位int的最小值。

8. int fitsBits(int x, int n)   计算x是否能被b位二进制表示,判断机制十分简单,无论x的正负,为了判断x是否能被n 位二进制表示,我们将x左移32-n位然后再右移32-n位,得到的结果与x作比较,如果一致的话, 说明在x的32位二进制表示之中前32-n位是没有用的,换句话说就是x能够被n位二进制数表示。 根据这样的原理,我们只需要判断两个数是否相同就能判断x是否能被n位二进制表示。因为32n是方便表示的,相当于32加上n的相反数,而n的相反数即为(~n+1)。党我们判断两个梳是否 相同时就可以使用异或的操作,如果相同则结果全为0,如果不同则结果中至少含有一个1。这时 我们可以使用!操作判断是否为0。但是在操作过程中,函数n=32时有报错,我想可能时移位操 作时有些小bug,于是在程序的结果中添加了n=32的判断,如果n=32,x是一定能被表示的。所 以这里只需要判断temp是不是0,得到结果再和之前的异或取反结果取或操作就能解决这个小 bug了。   例如:x=32,n=6,我们可以得到32-n = 0x21 + (~n) = 0x21 + 0xFFFFFFF9 = 0x1A, 而(x << 26) >> 26 = 0x0,而0x0^0x20=0x20,!0x20 = 0x0, !0x1A = 0x0,0x0|0x0 = 0,32不能被6位表 示。

9. int divpwr2(int x, int n)   计算x/(2^n),其实处理这个运算并不算麻烦,右移n位能得到结果。但是比较麻烦的事情是 这里需要向0取整,x为正数(x >> n)的结果和向0取整是一致的,但是负数时(x >> n)的结果会比 向0取整的数少1,这时我们需要判断x是否为负数如果x为负数,那么x右移n位之前需要补 上(2^n- 1),这样能在右移n位之后保证得到的数是向0取整的。判定x是否为负数很简单,只需 要把x右移31位得到数要么是0x0要么就是0xFFFFFFFF,把这个数和(2^n- 1)作与操作,就可以 得到x再右移之前需要相加的数了,因为如果x是正数,那么相加的数为0,如果x是负数那么相 加的数为 2^n- 1。   例如:x = -33,n = 5,x >> 31 = 0xFFFFFFFF,(1 << 5 + 0xFFFFFFFF) = 0x0000001F, 0xFFFFFFFF& 0x0000001F = 0x0000001F,x + 0x0000001F = 0xFFFFFF1F + 0x0000001F = 0xFFFFFF30,0xFFFFFF30 >> 5 = 0xFFFFFFFF = -1。

10.int negate(int x) 取x的相反数,由于x与x的相反数之和为0,根据这样的性质,我们可以想象x先与~x求和 得到的结果必然是0xFFFFFFFF,再这个基础上再加上1就能得到0x0这样一个理想的结果,所以 x的相反数是~x+1。   例如:x = 0xFFFFF00F,x十进制上面表示的是-4081这个数字,~x + 1 = 0x00000FF0 + 1 = 0x00000FF1,而0x00000FF1表示的数字刚好是4081 。

11.int isPositive(int x)   判断x是否为正数,方法十分简单只要判断x的符号位是否为0即可,!(x >> 31)就能知道x 的符号位是0还是1,但是我们遇到一个问题,就是在判断0的时候出现了bug,因为0的符号位 也是0,但是0并不是正数。我们需要额外判断x是否为0,判断x为0就更加简单,!x的操作就 能完成。现在只需要把逻辑理清楚就能写出表达式,当且仅当x不为0且x的符号位为0的时候x 为正数,那么(!(!x))&(!(x >> 31))的表达式自然就出来了。   例如:x = 0x8FFFFFFF,!!x = 1,!(x >> 31) = 0,所以0x1&0x0 = 0,这个x不是正数。

12.int isLessOrEqual(int x, int y)   判断x是否小于等于y,我们可以分两种情况进行讨论,一种是符号位相同的结果一种是符号 位不同的结果,两个结果取或操作就能得到我们最终的比较结果。符号不同时,判断x与y的大 小关系是容易的,符号位不同时当且仅当x符号位为1而y符号位为0的时候x小于等于y,那么 提取出符号位x >> 31,类似的有y >> 31,那么根据刚才叙述的逻辑,符号不同时的判断表达式 为(x >> 31)&(!(y >> 31)) 。而符号相同时,判断的条件是什么呢?我们可以直接使用y – x = y + ~x + 1这样的式子来判断结果的符号位,如果符号位是1,y < x,如果符号位是0,则y >= x,符号 位是0时是我们想要的结果。所以符号相同时,当且仅当y + (~x) + 1的结果符号位是0时x小于 等于y 。但是在计算y和x的差时,必须保证相同符号,不然符号不同的话,一个负数减去一个 正数在32位二进制中可能得到的是一个负数,所以事先需要判断是否为相同符号,根据之前取出 的x >> 31和y >> 31可以有异或操作来判断符号位是否一致。符号位一致的情况是,当且仅当(x >> 31) 和(y >> 31)的两个结果相同,且y + ~x + 1的结果的符号位为 0 时有x 小于等于y,那么就 有如下表达式((!(signY^signX))&(!signY_X)),其中signX = x >> 31,signY = y >> 31,signY_X = (y + (~x + 1)) >> 31 。最后两个情况的结果再取或操作。   例如:x = 0x0000001F,y = 0x0000000F,signX = x >> 31 = 0x0,signY = y >> 31 = 0x0,signY_X = (y + (~x) + 1) >> 31 = (0x0000000F + 0xFFFFFFE0 + 1) >> 31 = 0xFFFFFFF0 >> 31 = 0xFFFFFFFF,signX & (!signY) = 0x0 & 0xFFFFFFFF = 0x0,((!(signY^signX))&(!signY_X)) = ((! (signY^signX))&(!0xFFFFFFFF)) = ((!(signY^signX))&0x0) = 0x0,0x0 | 0x0 = 0,!!0 = 0 。

13.int ilog2(int x)   求以2为底数的x的对数,向下取整,由于x必须大于0,所以这道题其实就是求正数x在 二进制表示时数值为1的最高位bit位位数再减去1,由于一共有32个bit位,如果一位一位的 比较,势必会超过90个操作数,所以我们必须用其他更为简便的查找方法。我们这里采用的是 二分查找方法,先判断1的最高位数在前16位还是后16位,判断方法非常简单,将x数右移 16位,如果最高位数在后16位,那么右移16位之后得到的数字必然不是0,而如果最高位数在 前16位,右移16位后x将全部变成0 。接下来要解决怎么把这样得信息传递到下次判断之中, 因为是二分查找,所以下次查找是查找8位,可是怎么知道是在前16位查还是在后16位查。首 先,得知最高位数后16位数,那么结果是必然大于等于16,类似的,如果是在后8位,一定会 大于等于8,我们现在用一个变量来存储这样一个必然大于等于的值,因为是二分查找,有边界 条件,不断找到找到这样一个值之后,就能得到一个精确的结果。这样一个临时变量也就是我们 需要返回的结果。如果我们能判断最高位数在前16或者后16,我们可以用这样一个0或1判断 结果右移4位,就会得到16,而之后的结果就在这个16的基础上相加。那么问题来了,怎么让 下次8位判断知道在前16后16位查找呢?其实有了临时变量后十分简单,直接可以让x右移这 个临时变量的值就行,接下来就可以重复类似判断前16和后16的操作。因为知道了x最高1位 数大致位置,就可以通过右移,去掉一些无用的位数,就能更方便的进行运算。不过一定记住, 这个临时变量一定是累加的,中途的右移操作也是依托于这个变量,而且这个变量会记录最终的 结果。可以通过例子更加明白二分查找的过程。   例如:x = 0x00110201,temp = (!!(x >> 16)) >> 4 = (!!(0x00000011)) << 4 = 1 << 4 = 0x10000 = 16,temp = temp + ((!!(x >> (16 + 8))) << 3) = temp + ((!!0x0) << 3) = temp = 16,temp = temp + ((!!(x >> (16 + 4))) << 2) = temp + ((!!0x01) << 2) = temp + 4 = 20,temp = temp + ((!!(x >> (20 + 2))) << 1) = temp + ((!!0x0) << 1) = temp = 20, temp = temp + ((!!(x >> (20 + 1)))) = temp + (!!0x00) = 20,最高为1的位数21,最后结果 为20 。

14.unsigned float_neg(unsigned uf) 浮点数求相反数,浮点数取反其实非常简单,只要把将符号位取反就行,而不影响其他位的 数值即可,那么只需要和0x80000000取异或操作就能够实现,因为和1取异或是取反而和0取异 或则是取本身。但是题目里面有额外的要求,当参数是NaN的时候,应该返回原参数,不做符号 位的改变。所谓的NaN也就是,表示exp的八个bit位都是1并且表示frac的bit位不全为0的情 况下,我们说这样的浮点数表示的是NaN,允许if操作的话,我们其实只需要比较不考虑符号位 的情况下,浮点数解析成int的值是否大于(0xFF << 23)我们就能知道这个数是不是NaN,因为除 开符号位,如果这个数大于(0xFF << 23)的话,那么对应的exp的八个bit位必然全部为1,而且 frac部分必然是大于0的。所以我们只需要判断非符号位与(0xFF << 23) 的大小,然后根据情况返 回结果。如果大于这个数,那么返回本身,否则的话,符号位取反,就是需要返回的结果。   例如:uf = 0x10001111,(uf&(~(0x80 << 24)) = 0x10001111 & 07FFFFFFF = 0x0001111 < 0x7F80000 。返回uf^(0x80 << 24) = 0x10001111 ^ 0x80000000 = 0x00001111 。

15.unsigned float_i2f(int x)   int类型转float类型,我们可以理解int是没有exp部分的,而frac部分int有31位,而 float只有23位,所以很有可能会丢失精度,这时必须要有心理准备的,如果有精度丢失,我们 需要根据针对浮点数的”四舍五入”,来进行进位。我们要有准备应对这个情况,但是这只是属于 细节,真正重要的是怎么尽量减少丢失的精度。为了方便,我们只讨论int为正数的情况,因为 如果int为负数的话,我们可以转化为正数后,得到float结果后,再将符号位变为1。我们只需 要在转化int之前把符号位提取出来最后再加上去就行。   首先,我们该如何减少精度的丢失,这里其实很简单,我们忽略掉int二进制表示时(从左往 右数,第一个出现的1之前的0,这样在浮点数表示时,我们就能尽量减少精度丢失)。采用循环 的方法,从左往右遍历直到出现第一个1为止,用一个变量记录(0的个数加一),变量初始值为 1,循环停止之前每经过依次循环就自增1,结束条件就是(x & 0x80000000)为真,否则x就左 移一位需要提醒的事情是,如果输入为0,程序可能进入死循环,那么程序需要在最开始进行判 断,如果x为0就返回0,这样就避免了死循环,根据这个先决条件,我们能够确定最后的浮点 数表示中frac部分至少存在一个1。还要额外提醒一下这个(从左往右数)第一个1的作用,这个 1是不会显示在最后的frac部分的,因为一般情况下浮点数解析时个位数会自动变为1,除非 exp部分全为0,所以实际上frac部分显示的只需要原来的32 - temp2位,这就是为什么这个变 量储存的是(从左往右数)第一个1之前0的个数加一,而不是0的个数。   现在假设我们知道x中第一个1之前0的个数(temp2 - 1),怎么得出最后的float数字呢?我 们现在x已经左移到符号为1的情况,如果右移8位,注意是8位而不是9位,因为第一个1之 后的数字才有用,第一个1是在浮点数解析时会自动补上的,也就是说我们不必在乎这个原始x从 左往右数的第一个1在浮点数二进制中的表示。另外,由于是unsigned类型,右移时符号位会 一直补足0。我们已经得到float中frac部分的大致数字,然后只需要加上exp,符号位,和最后 丢失精度的进位就是最后的结果。   我们知道最高位1之前的0的个数加1为temp2,又由于之前右移8位时留了一个1在从左 往右数的第9位上,所以计算exp部分时可以少算一个1 。那么根据exp部分的计算公式,我们 可以得到exp部分应该表示的数为127+(31 – temp2) = 158 – temp2 。将这个数左移23位到 exp的位置,我们得到转为float之后的exp部分其他部分全为0 。   现在还有一个需要计算,就是当我们舍去某些位时,会导致精度的丢失,而此时我们需要根 据针对浮点数的”四舍五入”,判断flag是否为1 。现在提取出会被舍去的部分,也就是temp0的 (从左往右看)后9位,可以用和0x01ff的与操作,提取出来,如果这一部分是大于256(0x0100) 的,那么应该有进位操作,如果这一部分是等于256且temp0的(从左往右看)倒数第10位上是 数字1的话,也应该有进位,这种情况的判断是和0x03ff与操作,看结果是否与0x0300相等。 根据if判断在这两种情况下都使得flag=1,最后可以将求得的符号部分,exp部分,frac部分, 和最后的进位部分相加就能得到最后的结果。   例如:x= 0xFFFF8888,由于x < 0,那么求得绝对值abs = -x = 0x00007778,符号位 sign = 0x80000000,temp0表示需要右移的数,也就是x,进入循环判断,循环过程略去,循 环跳出时,tmp=0xEEF00000,temp2 = 18,temp0 = 0xDDE00000,根据if判断得到flag = 0 。那么最后的答案将会是 sign + (tmp >> 8) + ((158 – temp2) << 23) = 0x80000000 + 0x00EEF000 + (140 << 23) = 0x80000000 + 0x00EEF000 + (0x0000008C<< 23) = 0x80000000 + 0x00EEF000+0x46000000 = 0x80000000 + 0x46EEF000 = 0xC6EEF000 表示浮点数的0xFFFF8888 。

16.unsigned float_twice(unsigned uf)   求浮点数的两倍 ,需要考虑的情况分为,当exp部分全为0时,因为此时表示的frac部分 加入小数部分时,非小数位会变为0而不是1(0.frac这样的形式),如果这样的数乘以2,我们只 需要把x的后23位左移一位,然后符号位不变即可,因为如果小数第一位为1,那么左移一位, 刚好有一个1能够加入exp部分,此时的frac加入数值的小数部分时,非小数位由于exp不全为 0会自动变为1(1.frac这样的形式),如果小数的第一位为0,那么左移一位正好也是乘以2而不 影响其他部分的位置,实现方法为先提取符号位uf&0x80000000,然后提取出后23位 uf & 0x007FFFFF,然后左移一位之后与之前的符号结果做或操作;当输入为NaN,返回参数本身; 除开这两种情况,exp部分加1(实现方法uf + 0x00800000)就能够返回了。 例如:uf = 0x0070000F,uf & 0x7F800000 = 0,(uf & 0x007FFFFF) << 1 =0x 00E0001E,uf & 0x80000000 = 0,0x00E0001E | 0 = 0x00E0001E,返回0x00E0001E 。

 

 

 

 



HOME