CS:APP-Data Lab

前言

本实验分为两部分，第一部分要求我们使用给定的操作符完成相应的功能，第二部分是完成IEEE浮点数运算的仿真。

bitXor

描述：实现抑或运算

可用操作：~ &

最大操作量：14

真值表：

x	y	x⊕y
0	0	0
0	1	1
1	0	1
1	1	0
德·摩根定律：a∨b=~(~a∧~b)

x⊕y	= (x&~y)|(~x&y)
	 = ~(~(x&~y)&~(~x&y))

int bitXor(int x, int y) {
  return ~(~(x & ~y) & ~(~x & y));
}

tmin

描述：返回最小的二进制补码整数

可用操作：! ~ & ^ | + << >>

最大操作量：4

int tmin(void) {
	return 0x1 << 31;
}

isTmax

描述：判断是否为二进制最大补码数

可用操作：! ~ & ^ | +

最大操作量：10

实际上最大的补码数是0x7fffffff，但是无法直接写0x7fffffff

我们还注意到上数求反后是最小的补码数，而且补码性质：最大补码数绝对值比最小补码数绝对值小1，因此我们可以根据这个条件判断，我们先将该数字求反，再根据绝对值判断，当然这个过程中也要排除-1的存在

判断x是不是y，可以通过抑或进行：!(x^y)，因为抑或的性质是相同为0，相异为1,而取非是只有结果是0的时候才输出1，非0情况输出0

int isTmax(int x) {
  int y = ~x;
    // 如果 x 是 -1，那么 !(y ^ (x + 1)) 也是 1，因此要排除
  return !(y ^ (x + 1))  & !!(y);
}

allOddBits

描述：指定数字的所有的奇数位是否为1.

可用操作：! ~ & ^ | + << >>

最大操作量：12

我们可以先获取奇数位置上的数字，同时我们不关心偶数位置上面的数字，因此我们先将其与0xaaaaaaaa按位与，如果得到的结果是0xaaaaaaaa那说明是满足条件的，重要的步骤是如何构造0xaa了

int allOddBits(int x) {
    int AAAAAAAA = (0xaa << 24) + (0xaa << 16) + (0xaa << 8) + 0xaa;
    return !((x & AAAAAAAA) ^ AAAAAAAA);
}

negate

描述：求指定数字的负数.

可用操作符：! ~ & ^ | + << >>

最大操作数目：5

回顾一下一个数字的补码怎么表示？对于正数，补码就是其本身，负数的补码是求反加一，因此我们可以把这个取相反数看作求补码即可。

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

isAsciDigit

描述：判断指定数字是否大于等于0x30而小于等于0x39。

可用操作符：! ~ & ^ | + << >>

最大操作数目：15

首先这个数字必须满足前面28位是0x0000003

因此我们先构造出 0xfffffff0,再和待测数字按位与，得到的记为A，A如果与0x00000030相等则第一个条件满足（通过异或）

第二条件是最低的4位是0000~1001,因此：

• 要么倒数第4位是0
• 要么中间两个数字是0

int isAsciiDigit(int x) {
  	int FFFFFFF0 = (0xff << 24) + (0xff << 16) + (0xff << 8) + 0xf0;
	return !((x & FFFFFFF0) ^ 0x30) & ( !(x  & 0x8) | !(x  & 0x6) );
}

conditional

类似于x ? y : z

可用操作符：! ~ & ^ | + << >>

最大操作数目：16

不能用if语句，我们可以类似if语句 的逻辑，根据x的值返回，实际上我们可以同时将y和z作为运算，但是为了能够只返回其中之一，我们需要将某一个屏蔽，至于屏蔽哪个，则根据x的值来

int conditional(int x, int y, int z){
    // 如果 x 是0，则 flag = 00...00
    // 如果 x 非0，则 flag = 11...11
    int notZeroFlag = ~(!(!x)) + 1;
    return (notZeroFlag & y) | (~notZeroFlag & z);
}

isLessOrEqual

判断是否x<=y

可用操作符：! ~ & ^ | + << >>

最大操作数目：24

如果x=y，那么可以直接返回1；

最好的办法是先进行相减，但是在本题中，减法被禁用了。

回顾一下，计算机中，减法实际上是通过补码相加完成的，因此x-y可以使用x+(-y)进行表示。

完成减法后，我们可以根据减法结果进行判断，如果结果的最高位是0，则说明是结果正数，即x>y，应该返回0。当然 通过该方法的前提是不能够溢出，对于减法，异号相减才会有可能溢出，同号相减是不可能溢出的，因此我们可以先判断是否异号，如果异号，则根据哪个是正数哪个是负数来判断。

int isLessOrEqual(int x, int y) {
    int equal = !(x ^ y);
    int res = x + (~y + 1);
    int f1 = (x & (0x80 << 24)) >> 31;
    int f2 = (y & (0x80 << 24)) >> 31;
    int equalFlag = !(f1 ^ f2);

    int resNegFlag = (res & (0x80 << 24)) >> 31;
    return equal | (!equalFlag & (f1 | !f2)) | (equalFlag & resNegFlag);
}

logicalNeg

实现逻辑非“!”

如果待测数字是0，则输出1，否则输出0.

可用操作符：~ & ^ | + << >>

最大操作数目：12

我们要知道只有 0 和 最小负数（0x80000000）的相反数等于本身，并且除了这两个数字，任何数字和自己的相反数按位与或，必然是全1，而0和最小的负数在于符号位不同，因此我们可以借助该性质。

int logicalNeg(int x) {
		int flag = x | (~x + 1);
		// 如果x不是0，也不是最小负数，那么flag是全1，往右移31后还是全1（有符号移位），因此加1后是0
    	// 如果x是最小负数，即10000....,那么往右移31后还是全1（有符号移位），因此加1后是0
    	// 如果x是0，往右移31后还是全0，因此加1后是1
    	return (flag >> 31) + 1;
}

howManyBits

描述：判断x需要多少为补码表示

示例：

howManyBits(12) = 5
howManyBits(298) = 10
howManyBits(-5) = 4
howManyBits(0)  = 1
howManyBits(-1) = 1
howManyBits(0x80000000) = 32

可用操作：! ~ & ^ | + << >>

操作符上限：90

实际上题目说的不太清楚，对于除了全0和全1的数字，我们返回其二进制表示中除去前导零后剩余的位数再加1（符号位），对于负数，我们可以将其取反，当成正数来处理，例如，12d=1100b，返回5，298d=100101010b,返回10，对于0，我们以"0"表示，对于全1：111...111，我们直接使用"1"表示，对于1，我们使用“01”表示

我们先快速判断右边（即低位）有多少有效位，我们可以通过寻找最左边的1来获取右边的有效位，如果没有任何限制，我们可以从左到右循环判断，但是如此一来总的操作数肯定会超限 ，因为极端情况下左边是连续很多个0。

实际上我们可以使用二分的方法，我们每次判断高的半部分是否有1，如果有，则右半部分都是有效位，然后缩小区间，继续判断。

int howManyBits(int x){
    int negFlag,bit16,bit8,bit4,bit2,bit1,bit0;
    // 如果 x 是正数，则 negFlag = 00...00
    // 如果 x 是负数，则 negFlag = 11...11
    negFlag = (x & (0x80 << 24) )>> 31;
    x = (~negFlag & x) | (negFlag & (~x));
    // 如果高的16位（最右边是最低）中有1，则低16位都是有效位，因此 bit16 = 16
    // 否则，如果没有，则 bit16 = 0
    bit16 = (!(!(x >> 16)) << 4);
    // 如果高16位中有1，低16位则丢弃，因为我们关心的是高16位中1的位置在哪里
    // 否则，x不变（我们继续判断低16位中的高8位）
    x = x >> bit16;

    bit8 = (!(!(x >> 8)) << 3);
    x = x >> bit8;

    bit4 = (!(!(x >> 4)) << 2);
    x = x >> bit4;

    bit2 = (!(!(x >> 2)) << 1);
    x = x >> bit2;

    bit1 = (!(!(x >> 1)) << 0);
    x = x >> bit1;

    bit0 = !(!(x));
    return bit16 + bit8 + bit4 + bit2 + bit1 + bit0 + 1;
}

floatScale2

描述:将浮点数翻倍

可用操作：包括任何整数或者无符号操作，以及"||"、"&&"，if语句，while语句。

操作符上限：30

浮点数可以表示成： $$ v=(-1)^s2^eM $$ Ieee浮点数中，有4中类型的浮点数：

• 规格化数：阶码非全1且非全 0
• 非规格化数：阶码全0
• 无穷大：阶码全1、尾数全0
• NaN：阶码全1、尾数非全0

对于无穷大，乘以2还是无穷大，对于NaN，乘以2还是NaN。

对于非规格化数，由于阶码部分是固定的（全 0），我们直接对其移位即可完成乘2的运算，当然这个过程中有可能使得它变为规格化数，但是不影响。

对于规格化数,一般情况下阶码加一即可，但是如果加一后如果阶码变成了全1时候，要修改尾数，使得整个值为无穷大

unsigned floatScale2(unsigned uf){
    // 单精度浮点数 |1|  8 |    23       |
    // 阶码，尾数
    int exp, m, newExp;
    exp = uf & 0x7f800000;
    m = uf & 0x007fffff;
    // 无穷大  和 NaN
    if (!(exp ^ (0x7f800000))){
        return uf;
    }
    // 非规格化数
    if(!(exp ^ 0)){
        // 要保留原先符号
        return (uf & 0x80000000) | ((uf << 1) & 0x7fffffff);
    }
    // 规格化数,一般情况下阶码加一即可，
    // 但是如果加一后如果阶码变成了全1时候，要修改尾数，使得整个值为无穷大
    newExp = exp + 0x00800000;
    if (!(newExp ^ (0x7f800000))){
        return (uf & 0x80000000) | 0x7f800000;
    }


    return (uf & 0x80000000) | (newExp + m);
}

floatFloat2Int

描述:将浮点数强制转为int

可用操作：包括任何整数或者无符号操作，以及"||"、"&&"，if语句，while语句。

操作符上限：30

对于超出int范围的，我们可用直接返回0x80000000；

对于非规格化数，它们都是小于1的，因此直接返回0即可。

对于规格化数，我们要注意，尾数实际上隐含了整数部分的1。

为了将规格化数转为整数，我们可以使用“缩小阶码，往右移动小数点”的方式

int floatFloat2Int(unsigned uf){
    int exp, m, actuallyExp, intV;
    exp = uf & 0x7f800000;
    m = uf & 0x007fffff;
    // 无穷大  和 NaN
    if (!(exp ^ (0x7f800000))){
        return 0x80000000;
    }
    // 非规格化数
    if (!(exp ^ 0)){
        return 0;
    }
    // 规格化数，由于规格化数实际上是2^{e}*1.M
    // 因此强制转化时候，我们只需要将小数点往右边移动一定位置就行
    // 至于移动多少，取绝与阶码代表的含义，
    // IEEE单精度规格化数的实际阶码代表是 e-127
    actuallyExp = (exp >> 23) - 127;

    // 如果 actuallyExp 是一个负数，则说明是小于1的数字，直接返回0即可
    if (actuallyExp & 0x80000000)
        return 0;
    // 如果有舍入，即 actuallyExp  小于24
    // (实际上等于23时候并不是需要舍入，只不过是为了计算方便)
    if ((actuallyExp - 24) & 0x80000000){
        intV = (1 << actuallyExp) + (m >> (23 - actuallyExp));
        // 判断正负
        if ((uf & 0x80000000)){
            return ~intV + 1;
        }else{
            return intV;
        }
    }else{
        // 如果actuallyExp 大于等于31，则溢出，因为int只能表示31位整数
        // 而规则化数隐含了小数点前的1，因此后面最多能放30个数字
        if (!((actuallyExp - 31) & 0x80000000)){
            return 0x80000000;
        }
        intV = (1 << actuallyExp) + (m << (actuallyExp - 23));
        // 判断正负
        if ((uf & 0x80000000)){
            return ~intV + 1;
        }else{
            return intV;
        }
    }
}

floatPower2

描述：计算2^x，返回浮点数

可用操作：包括任何整数或者无符号操作，以及"||"、"&&"，if语句，while语句。

操作符上限：30

最大浮点数是：1.9999998808 X 2^(127)，因此如果x大于等于128，则直接返回无穷大即可.

当浮点数非常接近0的时候（即x小于等于-128），其表现形式是非规格化数，因此按照题目要求，我们可直接返回0 .

在其他情况下，我们需要将阶码加上偏置值 127 ，就可以得到2^x次幂了，尾数我们不用管，直接置零即可。

unsigned floatPower2(int x) {
	int ex;
	if(x >= 128)return 0x7f800000;
    // 如果小于-127（即小于等于-128），返回0
    if(x <= -128)return 0;
    ex =  x + 127;
    // 规格化数
    return ex << 23;


}

总结

• 离散数学真是个神奇的东西，很多公式之间可以相互转换
• 浮点数有点东西！以精度换取范围