CSAPP实验之Data Lab

上手指南

一共 12 个需要补充的函数,所有的工作都只需修改 bits.c 文件,测试的话有三种方式:btest, dlc, 和 BDD checker。

一些小技巧:

在函数开始时声明所有变量

}应该在第一列

注意运算符号的优先级,使用括号确保顺序的正确

关注 !, 0, TMin 等

任务指引还是比较清晰的,主要有以下一些说明:

整型的范围是 0 到 255(0xFF),不允许用更大

只能包含参数和局部变量

一元操作符 ! ~

二元操作符 & | + << >>

不允许的操作有:

使用任何条件控制语句

定义和使用宏

定义其他的函数

调用函数

使用其他的操作符

使用类型转换

使用除 int 之外的类型(针对整型)

使用除 int, unsigned 之外的类型(针对浮点数)

可以认为机器:

使用 2’s complent,32位

执行算术右移

移动超过字长的位数会出问题

其他需要注意的事情有:

使用 dlc(data lab checker) 来检测代码的合法性(有没有使用不给使用的符号语法等等)

每个函数都有操作数的上限值,注意 = 不算

使用 btest 来测试结果的正确与否

使用 BDD checker 来正规测试你的函数

显示32位int整型的show方法

void show(int x)
{
    /*
    Show 32 Bits Integer By Binary
    */
    for (int i = 0; i < 32; ++i)
    {
        if (i != 0 && i % 4 == 0)
            cout << " ";
        cout << ((x >> 31) & 1);
        x <<= 1;
    }
    cout << endl;
}

该方法用于检验函数是否写的正确以及调试的方便性

thirdBits

题目要求:return word with every third bit (starting from the LSB) set to 1

允许操作:! ~ & ^ | + << >>

操作数限制:8

分值:1

int thirdBits()
{
    /*
    Desired output: 0100 1001 0010 0100 1001 0010 0100 1001 
    step 1:         0000 0000 0000 0000 0000 0000 0100 1001  0x49
    step 2:         0000 0000 0000 0000 1001 0010 0100 1001
    step 3:         0000 0000 1001 0100 1001 0010 0100 1001
    step 4:         0100 1001 0010 0100 1001 0010 0100 1001 
    */
    int a = 0x49;
    int b = (a << 9);
    int c = a + b;
    return (c << 18) + c;
}

isTmin

题目要求:returns 1 if x is the minimum, two’s complement number, and 0 otherwise

允许操作:! ~ & ^ | +

操作数限制:10

分值:1

该题用于检验INT_MIN 该题用到INT_MIN+INT_MIN溢出后为0的技巧 但也要注意0+0也为0

int isTmin(int x)
{
    /*
    Return 1 if x is the minimum, two’s complement number, and 0 otherwise.
    */
    return !(x + x) & !!(x);
}

isNotEqual

题目要求:return 0 if x == y, and 1 otherwise

例如: isNotEqual(5,5) = 0, isNotEqual(4,5) = 1

允许操作:! ~ & ^ | + << >>

操作数限制:6

分值:2

该题用异或即可,不同则不为0,相同则0,随后用到了!!将int值转化为bool值的技巧

int isNotEqual(int x, int y)
{
    /*
    Return 0 if x == y, and 1 otherwise
    */
    return !!(x^y);
}

anyOddBit

题目要求:return 1 if any odd-numbered bit in word set to 1

例如: anyOddBit(0x5) = 0, anyOddBit(0x7) = 1

允许操作:! ~ & ^ | + << >>

操作数限制:12

分值:2

该题的想法是想声明一个值为0xaa的变量随后将其扩展到32位,最后与x做与操作即可得到答案

int anyOddBit(int x)
{
    /*
    Return 1 if any odd-numbered bit in word set to 1
    1010 1010
    */
    int a = 0xAA;
    int b = (a << 8) + a;
    int c = (b << 8) + a;
    int d = (c << 8) + a;
    return !!(x&d);
}

negate

题目要求:return -x

例如:negate(1) = -1.

允许操作:! ~ & ^ | + << >>

操作数限制:5

分值:2

该题利用补码的取反后加一即可达到要求,但是最开始没有想到取反操作而是制造了0xffffffff这个数进行操作

int negate(int x)
{
    /*
    Return negate 
    eg: if x==1 return -1
    Or return ~x+1
    */
    int mask = (1 ^ (1 << 31)) >> 31;
    return (x^mask) + 1;
}

conditional

题目要求:same as x ? y : z

例如:conditional(2,4,5) = 4

允许操作:! ~ & ^ | + << >>

操作数限制:16

分值:3

该题即三目操作符

int Conditional(int x, int y, int z)
{
    /*
    x?y:z
    Better : int mask= ~!x+1;
    */
    int mask = (!!x) << 31;
    mask >>= 31;
    return (mask&y) | ((~mask)&z);
}

subOK

题目要求:Determine if can compute x-y without overflow

例如:

subOK(0x80000000,0x80000000) = 1

subOK(0x80000000,0x70000000) = 0

允许操作:! ~ & ^ | + << >>

操作数限制:20

分值:3

该题判断减法是否溢出,减法是否溢出,第一个取决的便是两个数字的符号,我们可以发现

同号相减是不会溢出的,而异号相减溢出时结果的符号会与被减数的符号相反,所以有下面代码

int subOK(int x, int y)
{
    /*
    Determine if can compute x-y without overflow
    */
    int a = (x >> 31) & 1;
    int b = (y >> 31) & 1;
    int res = x + ~y + 1;
    int c = (res >> 31) & 1;
    return !(a^b) | !(a^c);
}

isGreater

题目要求:if x > y then return 1, else return 0

例如:isGreater(4,5) = 0, isGreater(5,4) = 1

允许操作:! ~ & ^ | + << >>

操作数限制:24

分值:3

该题比较两个数字的大小,首先我们明确正数是比负数大的,而负数比正数小

利用该性质我们可以先由该性质判断,随后利用两数相减为正数时返回1性质写出表达式

我们需要注意的是,该地方是不需要考虑溢出的,因为溢出是异号相减的行为

int isGreater(int x, int y)
{
    /*
    if x > y then return 1, else return 0  
    */
    int a = (x>>31) & 1, b = (y>>31) & 1;
    int res = x + ~y + 1;
    int c = (res>>31) & 1;
    return ((!a&b) | !c)&(!a | b);
}

bitParity

题目要求:returns 1 if x contains an odd number of 0’s

例如:bitParity(5) = 0, bitParity(7) = 1

允许操作:! ~ & ^ | + << >>

操作数限制:20

分值:4

该题要我们数出一个int整形的二进制表达中是否有奇数个0,我们可以利用异或不改变奇偶性来写

int bitParity(int x)
{
    /*
    returns 1 if x contains an odd number of 0’s
    bitParity(5) = 0, bitParity(7) = 1
    */
    x = (x >> 16) ^ x;
    x = (x >> 8) ^ x;
    x = (x >> 4) ^ x;
    x = (x >> 2) ^ x;
    x = (x >> 1) ^ x;
    return (x & 1);
}

howManyBits

题目要求:return the minimum number of bits required to represent x in two’s complement

例如:

howManyBits(12) = 5

howManyBits(298) = 10

howManyBits(-5) = 4

howManyBits(0) = 1

howManyBits(-1) = 1

howManyBits(0x80000000) = 32

允许操作:! ~ & ^ | + << >>

操作数限制:90

分值:4

该题要求我们返回该数字用补码表示时最少能用几位来表示 我们可以用二分法来判断有多少位

然后我们还要对特殊情况0和-1进行区分对待

值得一提的是,我们对负数要取反,但不必加一,因为补码表示中负数范围是比正数大的

而最小的负数取反后刚刚好是最大的正数

int howManyBits(int x)
{
    /*
    return the minimum number of bits required to represent x in two’s complement
    */
    int a = ((!x) << 31) >> 31; //当x为0时,a全为1,否则全为0
    int b = ((!~x) << 31) >> 31;//当x为-1时,b全为1,否则全为0
    int bit_16, bit_8, bit_4, bit_2, bit_1;
    int sum;
    int op = x ^ (x >> 31);
    bit_16 = (!!(op >> 16)) << 4;
    op = op >> bit_16;
    bit_8 = (!!(op >> 8)) << 3;
    op = op >> bit_8;
    bit_4 = (!!(op >> 4)) << 2;
    op = op >> bit_4;
    bit_2 = (!!(op >> 2)) << 1;
    op = op >> bit_2;
    bit_1 = (!!(op >> 1));
    op = op >> bit_1;
    sum = 2 + bit_16 + bit_8 + bit_4 + bit_2 + bit_1;
    return (a & 1) | (b & 1) | (~a & ~b&sum);
}

float_i2f

题目要求:Return bit-level equivalent of expression (float) x. Result is returned as unsigned int, but it is to be interpreted as the bit-level representation of a single-precision floating point values.

允许操作:Any integer/unsigned operations incl. ||, &&. also if, while

操作数限制:30

分值:4

该题只要懂得浮点数的表示即可写出

unsigned float_i2f(int x)
{
    int sign = (x >> 31) & 1;
    int exponent, fraction, fraction_mask = 0x7fffff;
    if (x == 0)
        return 0;
    else if (x == 0x8000000)
        exponent = 158;
    else
    {
        if (sign == 1)
            x = ~x + 1;
        int bit_16, bit_8, bit_4, bit_2, bit_1;
        int sum;
        int op = x ^ (x >> 31);
        bit_16 = (!!(op >> 16)) << 4;
        op = op >> bit_16;
        bit_8 = (!!(op >> 8)) << 3;
        op = op >> bit_8;
        bit_4 = (!!(op >> 4)) << 2;
        op = op >> bit_4;
        bit_2 = (!!(op >> 2)) << 1;
        op = op >> bit_2;
        bit_1 = (!!(op >> 1));
        op = op >> bit_1;
        sum = 1 + bit_16 + bit_8 + bit_4 + bit_2 + bit_1;
        if (sum > 24)
            fraction = x >> (sum - 24);
        else if (sum < 24)
            fraction = x << (24 - sum);
        fraction &= fraction_mask;
        exponent = 127 + sum - 1;
    }
    show(fraction);
    unsigned ux = (sign << 31) + (exponent << 23) + fraction;
    return ux;
}

float_f2i

题目要求:Return bit-level equivalent of expression (int) f for floating point argument f. Argument is passed as unsigned int, but it is to be interpreted as the bit-level representation of a single-precision floating point value. Anything out of range (including NaN and infinity) should return 0x80000000u.

允许操作:Any integer/unsigned operations incl. ||, &&. also if, while

操作数限制:30

分值:4

该题是11题的逆过程,值得注意的是,我们要对小数部分进行切除

int float_f2i(float f)
{
    int*pf = (int*)&f;
    int x = *pf;
    show(x);
    int sign = x >> 31;
    int x_abs = x & 0x7fffffff;
    int exponent = x_abs >> 23;
    if (exponent < 127)
        return 0;
    show(exponent);
    int fraction_mask = 0x7fffff;
    int fraction = x&fraction_mask;
    show(fraction);
    int i = 0;
    while (fraction)
    {
        if (fraction & 1)
            break;
        fraction >>= 1; 
        ++i;
    }
    cout << i << endl;
    show(fraction);
    fraction |= (1 << (23 - i));
    show(fraction);
    int len = exponent - 127 - (23 - i);
    cout << len << endl;
    int res;
    if (len > 0)
        res = fraction << len;
    else
        res = fraction >> -len;
    cout << exponent << endl;
    cout << res << endl;
    if (sign == -1)
        res = ~res + 1;
    return res;
}

结语

第一个数据实验算是结束了,通过该实验,我又加深了对数据的理解,尤其是各种掩码的设计,有了更深的理解