CSAPP Data Lab

Data Lab 的内容是仅采用有限制的位运算符实现一些函数。

bitXor

实现按位异或。

\(x\oplus y = (x\wedge \neg y)\vee(\neg x\wedge y)=\neg(\neg(x\wedge \neg y)\wedge\neg(\neg x\wedge y))\)

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

tmin

计算\(T_{min}\)。

其位级表示为0x80000000，即1 << 31。

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

isTmax

判断\(x\)是否是\(T_{max}\)。

\(T_{max}\)和-1 均满足\(\neg x = x + 1\)，判断\(x\)和\(y\)相等可以用!(x ^ y)，判断不为-1 可以按位取反之后取两次非（不取两次非的话可能会取到\(>1\)的值）。

int isTmax(int x)
{
    return !(~x ^ (x + 1)) & !!~x;
}

allOddBits

判断\(x\)的奇数位上是否都为 1。

将\(x\)的每个字节都或0x55，如果奇数位上都为 1 的话会得到0xFFFFFFFF也就是-1，之后判断是否为-1。

int allOddBits(int x)
{
    int y = 0x55;
    int z = (y << 24) | (y << 16) | (y << 8) | y | x;
    return !~z;
}

negate

计算\(x\)的相反数。

取反+1，书上有写。

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

isAsciiDigit

判断\(x\)是否在0x30到0x39之间。

\(x\)右移四位，必须和 3 相等，之后\(x\)的（低位起）第 4 位为 0，或者第 4 位为 1 并且第 2、3 位为 0。

int isAsciiDigit(int x)
{
    int y = x & 0xF;
    int z = x >> 4;
    return !(z ^ 3) & (~(y >> 3) | !((y >> 1) & 3));
}

conditional

实现x ? y : z。

首先通过\(x\)计算\(a\)，如果\(x\)不为 0 则\(a\)为0xFFFFFFFF，否则\(a\)为 0。观察得到a = !x - 1。之后利用0xFFFFFFFF & x == x和0 & x == 0即可。

int conditional(int x, int y, int z)
{
    int a = !x + ~1 + 1;
    return (~a & z) + (a & y);
}

isLessOrEqual

判断x <= y。

一般来说计算y - x，判断符号位为 0 即可，对于溢出的情况，比较\(x\)和\(y\)的符号位，如果\(x\)为负并且\(y\)非负，则答案必为 1，如果\(x\)非负并且\(y\)为负，则答案必为 0。

int isLessOrEqual(int x, int y)
{
    int a = (x >> 31) & !(y >> 31);
    int b = !(x >> 31) & (y >> 31);
    int z = y + ~x + 1;
    return a | ~b & !(z >> 31);
}

logicalNeg

实现!x。

~0 == -1，即检查~x的每一位是否都为 1。

int logicalNeg(int x)
{
    int a = ~x;
    int b = (a >> 16) & a;
    int c = (b >> 8) & b;
    int d = (c >> 4) & c;
    int e = (d >> 2) & d;
    return (e >> 1) & e & 1;
}

howManyBits

以补码方式表示\(x\)的最小位数。

注意非负数需要以符号位 0 开头，负数的位数是取反后的位数加上一个符号位。

首先根据利用之前的条件判断计算\(y\)，如果\(x\)是非负数，y = x，否则y = ~x。

答案初始为 1（符号位），之后不考虑符号位看表示\(y\)需要多少位即可。

对于答案的每一位，看它是 1 还是 0，比如如果答案的第 5 位为 1，则\(y\)的长度大于 16，即y >> 16不为 0，下一步迭代\(y\)的高 16 位，反之迭代\(y\)的低 16 位。

int howManyBits(int x)
{
    int a = 1;
    int k = ~1 + 1;
    int t = !((x >> 31) & 1) + k;
    int y = (t & ~x) + (~t & x);
    t = !(y >> 16) + k;
    a += t & 16;
    y = (t & (y >> 16)) + (~t & y & ((0xFF << 8) | 0xFF));
    t = !(y >> 8) + k;
    a += t & 8;
    y = (t & (y >> 8)) + (~t & y & 0xFF);
    t = !(y >> 4) + k;
    a += t & 4;
    y = (t & (y >> 4)) + (~t & y & 0xF);
    t = !(y >> 2) + k;
    a += t & 2;
    y = (t & (y >> 2)) + (~t & y & 3);
    t = !(y >> 1) + k;
    a += t & 1;
    y = (t & (y >> 1)) + (~t & y & 1);
    a += y;
    return a;
}

floatScale2

计算2 * f。

根据规格化、非规格化、特殊情况三种来判断，注意非规格化转化到规格化和规格化溢出的情况。

unsigned floatScale2(unsigned uf)
{
    int s = uf & 0x80000000;
    int exp = (uf >> 23) & 0xFF;
    int frac = uf & 0x7FFFFF;
    if (exp == 0xFF)
        return uf;
    if (!exp)
    {
        if (frac >> 22)
            return s | (1 << 23) | ((frac << 1) & 0x7FFFFF);
        return s | ((frac << 1) & 0x7FFFFF);
    }
    if (exp == 0xFF - 1)
        return s | (0xFF << 23);
    return s | ((exp + 1) << 23) | frac;
}

floatFloat2Int

浮点数转整数。

非规格化的数返回 0，特殊情况返回\(T_{min}\)；规格化的指数\(E<0\)的情况返回 0，\(E>31\)的情况返回\(T_{min}\)，其余的情况正常计算。

int floatFloat2Int(unsigned uf)
{
    int s = uf >> 31;
    int exp = (uf >> 23) & 0xFF;
    int frac = uf & 0x7FFFFF;
    if (exp == 0xFF)
        return 0x80000000u;
    s = s ? -1 : 1;
    if (!exp)
        return 0;
    if (exp >= 127)
    {
        if (exp <= 157)
            return s * (1 << (exp - 127)) * ((frac >> 23) + 1);
        return 0x80000000u;
    }
    else
        return 0;
}

floatPower2

计算\(2.0^x\)。

最小非规格化数为\(2^{-23}\times2^{-126}\)，最小规格化数为\(1\times2^{-126}\)，最大规格化数为\((2-\varepsilon)\times2^{127}\)。

unsigned floatPower2(int x)
{
    if (x < -149)
        return 0;
    else if (x < -126)
        return 1 << (x + 149);
    else if (x < 128)
        return (x + 127) << 23;
    else
        return 0x7f800000;
}

总结

难度比预想大一些，尤其是整数部分的最后几道题，有很多小 trick，但是感觉收获不大，可能用处比较局限。