csapp lab日常 1.datalab

好像几百年没更博了。。。

最近在学cmu的csapp，没有学号不能在cmu上交
不过可以下官方的自学lab

datalab断断续续搞了两三天QAQ
就不贴官方要求了

1.bitAnd

用 ~,| 实现按位与

int bitAnd(int x, int y) {
    return ~((~x)|(~y));
}

2.getByte

获得第n个byte

int getByte(int x, int n) {
    return (x>>(n<<3))&0xff;
}

3.logicalShift

逻辑右移n位
把最高的n-1位置0

int logicalShift(int x, int n) {
    int v1 = 1<<31;
    int v2 = ~((v1>>n)<<1);
    return (x>>n)&v2;
}

4.bitCount

计算所有位中1的个数，限制40个ops
开始确实没想到可以用类似分治一次搞多位。
就是每次把连续$$2^k$$个bit的和计算出来放在原来的位置
这个东西可以所有位一起搞

int bitCount(int x) {

    int t0 = 0x55|(0x55<<8);
    int v0 = t0|(t0<<16);
    int x0 = (x&v0)+((x>>1)&v0);

    int t1 = 0x33|(0x33<<8);
    int v1 = t1|(t1<<16);
    int x1 = (x0&v1)+((x0>>2)&v1);

    int t2 = 0xf|(0xf<<8);
    int v2 = t2|(t2<<16);
    int x2 = (x1&v2)+((x1>>4)&v2);

    int v3 = 0xff|(0xff<<16);
    int x3 = (x2&v3)+((x2>>8)&v3);

    int v4 = 0xff|(0xff<<8);
    int x4 = (x3&v4)+((x3>>16)&v4);

    return x4;
}

5.bang

不用!实现！
把所有位或到第一位就好了，每次折半

int bang(int x) {
    x |= x >> 16;
    x |= x >> 8;
    x |= x >> 4;
    x |= x >> 2;
    x |= x >> 1;
    return (~x)&1;
}

6.tmin

最小的two's complement number -2147483648

int tmin(void) {
    return 1 << 31;
}

7.fitsBits

数x是否可以被表示成n个bit的数
就是判断最高32-n+1位是否相同
因为要实现logicalshift写的极丑，还特判了n=32

int fitsBits(int x, int n) {
    int v1 = 1<<31;
    int v2 = ~((v1>>n)<<1);
    x ^= x >> 31;
    return (n>>5&1)|(!((x << 1 >> n)&v2));
}

8.divpwr2

$$x/2^k$$向0取整
负数的话判断一下前n位有没有东西，如果有就+1

int divpwr2(int x, int n) {
    int v1 = x>>31&1;
    int v2 = !!((x>>n<<n)^x);
    return (x>>n)+(v1&v2);
}

9.negate

返回-x

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

10.isPositive

返回x是否大于0
判0或负数

int isPositive(int x) {
    return !((!(x&~(1<<31)))|(x>>31));
}

11.isLessOrEqual

比较x是否小于等于y
首先比较符号是否相同
符号不同返回x为负
符号相同返回y-x非负

int isLessOrEqual(int x, int y) {
    int v2 = (x>>31)&1;
    int v1 = v2^((y>>31)&1);
    int v3 = y+((~x)+1);
    int v4 = !((v3>>31)&1);
    return (v1&v2)|((!v1)&v4);
}

12.ilog2

返回最高位位置（log下取整）
优雅的二分

int ilog2(int x) {
    int ret = 0;
    int t1 = 0;

    t1 = !(x>>16);
    ret = (!t1)<<4;
    x = x>>(16^(t1<<4));

    t1 = !(x>>8);
    ret |= (!t1)<<3;
    x = x>>(8^(t1<<3));

    t1 = !(x>>4);
    ret |= (!t1)<<2;
    x = x>>(4^(t1<<2));

    t1 = !(x>>2);
    ret |= (!t1)<<1;
    x = x>>(2^(t1<<1));

    return ret|(x>>1);
}

13.float_neg

为啥到这函数名就变下划线了啊啊啊啊
传入一个unsigned表示一个float格式的数，返回-x
判一下nan，把符号位反过来

unsigned float_neg(unsigned uf) {
    unsigned v = uf;
    unsigned frac = 0;
    unsigned exp = 0;
    unsigned s = 0;
    unsigned nf = 0;

    frac = v&0x7fffff;
    v>>=23;
    exp = v&0xff;
    v>>=8;
    s = v;
    nf = uf^0x80000000;
    if(exp == 0xff && frac)
        return uf;
    return nf;
}

14.float_i2f

把int转成float
首先特判掉0和-2147483648（雾）
然后记一下符号位，转成正数
然后如果不到23位就补到23位，如果超了的话emmm，round to nearest even了解一下~~~

unsigned float_i2f(int x) {
    unsigned exp = 0;
    unsigned frac = 0;
    unsigned s = 0;
    unsigned tx = x;
    unsigned num = 0;
    unsigned pre = 0;
    if(!tx) return 0u;
    if(tx == 0x80000000) return 0xcf000000;
    if(tx&0x80000000)
        s = 0x80000000, tx = -tx;
    exp = 150;
    while(tx < 0x800000)
        tx <<= 1,exp--;
    while(tx >= 0x1000000)
    {
        pre = tx & 1;
        num += pre;
        tx >>= 1; exp++;
    }
    if( pre && (num + (tx&1) >= 2))
    {
        tx++;
        if(tx >= 0x1000000)
            tx >>= 1, exp++;
    } 
    frac = tx^0x800000;
    return frac | (exp<<23) | s;
}

15.float_twice

传入一个unsigned表示一个float格式的数，返回2x
判掉nan和inf
再判一下2x会不会到inf
再判一下是不是normalized的
再判一下会不会到normalized

unsigned float_twice(unsigned uf) {
    unsigned v = uf;
    unsigned exp = 0;
    unsigned frac = 0;
    unsigned s = 0;
    unsigned exp1 = 0;
    unsigned frac1 = 0;
    unsigned s1 = 0;

    frac = v&0x7fffff;
    v>>=23;
    exp = v&0xff;
    v>>=8;
    s = v;

    exp1 = exp;
    frac1 = frac;
    s1 = s;

    if(exp == 0xff)
        return uf;

    if(exp == 0xfe)
        exp1 = 0xff, frac1 = 0;
    else if(exp == 0)
    {
        if((frac >> 23) & 1)
        {
            frac1 ^= 1<<23;
            exp1 = 1;
        }
        frac1 <<= 1;
    }
    else exp1++;

    return frac1 | (exp1<<23) | (s1<<31);
}