datalab

lab1-datalab

由于我大一寒假时写过logicalneg之前的题，这次实验我直接沿用了之前的bits.c,logicalneg前的函数代码里塞了一些没啥必要的注释。在报告里同样会写出思路，不影响报告格式。

INTEGER 部分:

bitXor:

用~和&实现异或 。

1 0        0  
1 1  And   1
1 1 -----> 1
0 1        0

可以逆推出异或的前一步是构造出这样的真值表结果，这种三个1一个0的结果通过~和& 很容易构造出来

0111 可以看成或运算 用德摩根定律也可以转化为~和&

int a = ~(x&y);
int b = ~(~x&~y);
return a&b;

tmin:

tmin就是二进制补码数的最小值，直接把1移到最高位就行了

return 1<<31;

isTmax:

对于Tmax 有个性质是+1会变成Tmin , 他们在位上正好是完全相反的，两者异或可以得到-1，在其他数之中只有-1 也有相同的性质。 只要排除这个情况就行了。 正好-1 + 1又等于0, !(-1+1) 和 !(Tmax +1 ) 是不同的 可以他们整合到最后的判断算式中。

我整合的方法是先计算(x & (x+1) ) ，再计算!(x+1) 只有两者都为0 ，才返回1 用一个加法和一个! 就能实现.

int y=x+1;
int z=(x^y)+1;
return !(z+!y);

allOddBits:

如果所有奇数位都是1就返回1。这里我想到掩码，构造一个奇数位都是1的数t ，让它和 x 与 ，就能单独取出奇数位 然后和t异或 ，只有和t完全一致，才能得到0 ,!之后就能得到1

int t=(0xAA<<24)+(0xAA<<16)+(0xAA<<8)+(0xAA);
return !(t^(x&t));

negate:

返回-x, 很老套的方法？ 直接返回~x +1 就行了

return ~x + 1;

isAsciiDigit:

ascii数字从0x30到0x39， 先观察这些数字的共同特性 , 0x30是0b0110000,0x39 是 0b0111001, 可以发现有很大一部分由0b0110开头 ，并且是他们特有的 ，先判断是不是这样的数据，然后单独处理0x38和0x39。

return !((x>>3)^0x6)|!(x^0x39)|!(x^0x38);

conditional:

实现条件取值。

if(x) 相当于 if (!!x) ， 我的思路是将!x 扩大32位，然后对两者进行掩码，再用|合并，那么就要控制x不为0时 取 全1或全0 ，为0时全0或全1

我利用了-1+1 可以在这两种取值突变的特性实现上述功能。

  int t=!x+~0;
  return (t&y)|(~t&z);
}

isLessOrEqual

我直接用了个非常笨的方法 ，把一个是正数一个负数的情况直接判断出来。如果两个数符号相同 就 判断 x-y-1 是不是正数或者0 正好-y 是 ~y + 1 还省了一个1

int p=(x>>31)&1;
int q=(y>>31)&1;
int t=(p^q)&p;
int b=(!(p^q))&((x+~y)>>31);
return b|t;

logicalNeg:

实现!的功能。我想到了0的一个特殊的特性 -0 = 0; 那么我只要判断 ~x + 1 和原来的数据是否是相等的 ，但是要小心tmin 因为 -tmin仍然是tmin 。 我做这题时用了另外一个判断方法，就是判断是否一正一负。这样可以通过或的特性排除掉tmin全负的情况。

int a = ~x+1;
 int p = (x>>31)&1;
 int q = (a>>31)&1;
 return (p|q)^1;

howManyBits:

先观察规律，发现对于正数和负数都是一样的: 找到第一个变化的位 ，然后再加上1。

利用算数右移可以根据第一位来选择性的取反,这样就统一成一种情况了x = x^(x>>31);

之后的目标就是找到第一个1的位置 ，最开始我的想法是逐个查找，但是30个位的 + >> ! 就已经超过90了，需要更强大的查找算法。于是我想到了二分查找: 用p对分割进行标记，如果分割左侧有1 ，就缩小范围到p左侧 ，否则到p右侧。

例如p等于32时，分割如下:

0x0000 | 0x0000

那么问题就转化成了如何实现在受限情况下更简洁的二分查找。 这让我想到了c语言编译器对if的一种优化 : 转化分支为条件赋值。例如 第一次查找 ，p=32 ,先假设左边没有1 也就是 p = 16; 如果左边有1，再将 p + 32即可，用代码表示就是

p=32;
p = 16+((!!(x>>p))<<5);

同时这么做有个好处 ，假设这一次运行完后p等于48 ,需要先-8 ,就可以用异或实现 ，因为p在16的位置一定是 1, 8 的位置一定是0.

p = (p^24) + ((!!(x>>p))<<4);

需要特殊处理的是最后在2位的区间内查找，此时不应该进行先-1，因为之后并没有再缩小区间的需求了。

p = p+ ((!!(x>>p)));

还有一个特殊情况是全0 ，可以当作在第-1位有一个1,我的上述算法并不能判断出这个情况，因此要单独处理

综上，代码为

 int p ;
 x = x^(x>>31);
 p=32;
 p = 16+((!!(x>>p))<<5);
 p = (p^24) + ((!!(x>>p))<<4);
 p = (p^12 ) + ((!!(x>>p))<<3);
 p = (p^6) + ((!!(x>>p))<<2);
 p = (p^3) + ((!!(x>>p))<<1);
 p = p+ ((!!(x>>p)));
return p+(1^( !(x)));

floatScale2

实现 浮点数*2 。

考虑三种情况 inf， 规格数，0 。

inf时直接返回。

规格数时 令阶码+1

0时 ，根据IEEE规定的特性 假设有0b 0.1111 , 要使其翻倍 ，即变成 0 b 1.1110 ,反映在浮点数中 ，由于规格数 1和 0 ，都是x**-126 , 最终只需要让尾数整体左移

  int T;
  T = uf;
  T = (T<<1)>>24;
  if(T+1){
      if(T){
          return uf+(0x00800000);
      }else{
          return (uf<<1)+(uf&(0x80000000));
      }
  }
return uf;

floatFloat2Int

总体上分三种情况

exp - 127 >= 31,此时过大 返回0x80000000。

exp - 127 <0 此时过小 返回0。

之后还可以细分成两个情况。

exp - 127 < 23 时 这时候应该让尾数右移，因为尾数最低位是2的-23次方。

exp -127 >=23 时，这时候尾数左移。

另外还要考虑符号位 ，最后根据符号位判断是否取负值

int floatFloat2Int(unsigned uf) {
    unsigned int exp =  (uf<<1)>>24;
    unsigned frac = (uf&0x7FFFFF)|(1<<23);
    int T = exp - 127;
    if( T < 0 ) return 0;
    if( T >= 31 ) return 0x80000000;
    if( T < 23 )  frac >>= ( 23 - T);
    else frac <<=(T-23);
    if(uf>>31) return -frac;
    return frac;

C99 开始 规定负数向0截断，这使得在负数情况下 这种直接取反的行为是合理的。

floatPower2

考虑三种情况

过大时直接返回+inf

不过大时 如果>0 只需要依靠阶码，如果<0 ,在<-126 的情况下 还可以用到尾数 ，也就是说最多可以表示到-149

过小时返回0

按照上述几种情况分别实现即可

if (x > 127) return 0x7f800000;
if (x <(- 149)) return 0;
if (-126 <= x) return (x + 127)<<23;
return 0x400000 >> (-126 - x);

另外，在浮点数部分有个规则是禁止任何形式的类型转换，我认为这里应该理解为禁止对位级存储规则进行转换，否则这和给出的另一个规则: 可以使用任何integer/unsigned operations 是矛盾的。

btest在最后一个函数卡了很久 不过strace发现题目设置的是alarm(10) , 并没有超出时间,但不知道为何会卡这么久。