Data Lab

前言

CSAPP 这本书买了好几年，最近抽出一些时间开始重头读这本书，发现这些基础知识比较重要，边看书边跟着视频课程过了一遍，有些东西还是比较模糊。本文开始做 CSAPP Lab 实验，加强巩固书的内容。

说明

这个实验主要考察整数和单精度浮点数的表示以及位运算，加强深对对计算机数据表示的理解。

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

1. 整型的范围是 0 到 255(0xFF)，不允许用更大
2. 只能包含参数和局部变量
3. 一元操作符 ! ~
4. 二元操作符 & | + << >>
5. 浮点数可以使用控制语句

题目

bitXor

/*
 * bitXor - x^y using only ~ and &
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
    return ~(~(~x & y) & ~(x & ~y));
}

异或就是二级制不相等才为1，同时为 0 或者同时为 1，结果为 0 ，比如：

十进制   二进制
  4      100
  5      101 
         001 // 异或结果

其中(~x & y) 表示 x 中的 0 和 y 中的 1，(x & ~y)表示 x 中的 1和 y 中的 0，然后通过德·摩根定律~(a & b) = ~a | ~b。

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

tmin

/*
 * tmin - return minimum two's complement integer
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
    return 1 << 31;
}

这个题目比较简单，int 有符号采用的是补码表示如图，最小为10000000 00000000 00000000 00000000 我们只需要把 1 往左移动 31 位就行。

   

isTmax

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) {
    return !(x + 1 + x + 1) & !!(~x);
}

我们发现最大值两倍加二为0，但是要排除 -1（补码全为1）后面!!(~x) 就是这个逻辑。

x                01111111 11111111 11111111 11111111
x + 1            10000000 00000000 00000000 00000000
x + 1 + x        11111111 11111111 11111111 11111111
x + 1 + x + 1    00000000 00000000 00000000 00000000

allOddBits

/*
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
    int e = 0xAA | (0xAA << 8);
    e = e | (e << 16);
    return !((e & x) ^ e);
}

先获取全为奇数位的数，这里的奇数指的是位的阶级是 2 的几次幂。然后取并如果偶数为有值，那么异或之后就不会为0。

// 10101010 10101010 10101010 10101010
int a = 0xAA;        // 00000000 00000000 00000000 10101010
int b = 0xAA << 8;   // 00000000 00000000 10101010 00000000
int c = a | b;       // 00000000 00000000 10101010 10101010
int d = c << 16;     // 10101010 10101010 00000000 00000000
int e = c | d;       // 10101010 10101010 10101010 10101010

negate

/*
 * negate - return -x
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
    return ~x + 1;
}

可以发现取反之后两个之和为 -1，x + ~x = -1，那么-x = ~x + 1然后只需要取反加 1就行，

 -8      -7   -6   -5   -4   -3   -2   -1   0    1    2    3    4    5    6    7
1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111  
0111 1001 0101 0100 0011 0010 0001 0000 1111 1110 1101 1100 1011 1010 1001 1000
  7    6    5    4    3   2    1     0    -1   -2   -3   -4  -5   -6   -7   -8

isAsciiDigit

/*
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x) {
       int min = 0x1 << 31;
       int max = ~min;
       int start = ~0x39;
       int end = max - 0x30 + 1;
       int c = (x + start) >> 31;
       int d = (x + end) >> 31;
       // printf("x=%d, c=%d, d=%d\n",x, c, d);
       return !!(c & d);
}

比如保证 a + start < 0 并且 b + start < 0，然后 a + end < 0 并且 b + end < 0，这个时候是溢出小于零。根据如果 x 为负数x >> 31 = -1，否者 x >> 31 = 0，再通过两次去反获得。

 -8      -7   -6   -5   -4   -3   -2   -1   0    1    2    3    4    5    6    7
1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111  
 
a <= x <= b   1 <= x <= 3    2<= x <= 5 

start  end      -4       7     -6       6
   
-y = ~y + 1

start + b = -1     => start = -1 - b = ~b
a + end = max + 1  => end = max + 1 - a = max - a + 1

conditional

/*
 * conditional - same as x ? y : z
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
    int mask = ~!x + 1;
    return (y & ~mask) | (z & mask);
}

这是一个if-else 语句，我们可以转化为 (y op expr) | (z op expr)，其中 op 为操作符，expr 为表达式。

(y op expr) | (z op expr)

x == 0  mask = 0xFFFFFFF
x != 0  mask = 0xOOOOOOO

isLessOrEqual

/*
 * isLessOrEqual - if x <= y  then return 1, else return 0
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y) {
    int x_sign = (x >> 31) & 0x01; // x 的符号
    int y_sign = (y >> 31) & 0x01; // y 的符号
    int a = !(x ^ y);
    int b = (x_sign & (!y_sign)); // 判断是否 x < 0 y > 0
    int c = (!((x_sign ^ y_sign) & 0x01)); // 判断符号是否相等
    // x - y = x + ~y + 1
    int res_sign = ((x + ~y + 1) >> 31) & 0x01;// 判断x-y的符号
    return a | b | (c & res_sign);
}

用 x - y 通过符号来判断，但是可能会溢出，所以当符号不相同就可以直接判断大小。

x	y	x - y
x > 0	y > 0	正常
x > 0	y < 0	可能向上溢出
x < 0	y > 0	可能向下溢出
x < 0	y < 0	正常

主要分为3部，

• 看看是否两个数相等 !(x ^ y) 如果相等为1
• 判断符号是否相反，主要看 x < 0，y > 0
• 判断符号相等的时候，x - y < 0

logicalNeg

/*
 * logicalNeg - implement the ! operator, using all of
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
 */
int logicalNeg(int x) {
    int neg_x = ~x + 1;
    return ((neg_x | x) >> 31) + 1;
}

求 x | -x ，如果 x 不为 0 的化，那么符号位一定为 1，如果 x 为 0 那么符号为0。

howManyBits

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5               //  0_1100
 *            howManyBits(298) = 10             //  0_100101010
 *            howManyBits(-5) = 4               //  1_101
 *            howManyBits(0)  = 1               //  0
 *            howManyBits(-1) = 1               //  1
 *            howManyBits(1) =  2               //  0_1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
    int b16, b8, b4, b2, b1, b0;
    int mask = x >> 31;
    // 如果x为正数，保持不变；如果为负数，按位取反
    x = (mask & ~x) | (~mask & x);
    // 如果高16位有1，b16 = 16，否者为0
    b16 = !!(x >> 16) << 4;
    // 如果高16位有1，x右移16位，在新的16为重继续找
    x = x >> b16;
    // 高8
    b8 = !!(x >> 8) << 3;
    x = x >> b8;
    // 高4位
    b4 = !!(x >> 4) << 2;
    x = x >> b4;
    // 高2位
    b2 = !!(x >> 2) << 1;
    x = x >> b2;
    // 高1位
    b1 = !!(x >> 1);
    x = x >> b1;
    // 底1位
    b0 = x;
    return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}

对于正数，找到最左边的 1，对于负数，按位取反处理。

0 1 1 1 0 0 0 1     b4 = 4
0 1 1 1             b2 = 2
0 1                 b1 = 0
  1                 b0 = 1

floatScale2

/*
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf) {
    // sign  exp  frac
    //  1     8    23
    unsigned sign = (uf >> 31) & 0x01;
    unsigned exp = (uf >> 23) & 0xFF;
    unsigned frac = uf & 0x7FFFFF;
    // 特殊
    if (exp == 0xFF) {
       return uf;
    }
    // 非规格化
    else if (exp == 0) {
        frac = frac << 1;
        return (sign << 31) | (exp << 23) | frac;
    }
    // 规格化
    else {
        exp ++;
        return (sign << 31) | (exp << 23) | frac;
    }
}

先分别求出 sign ，exp 和 frac，如果是特殊值直接返回，在判断是否是规格化，分别处理。

floatFloat2Int

/*
 * floatFloat2Int - 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.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
    // sign  exp  frac
    //  1     8    23
    unsigned sign = (uf >> 31) & 0x01;
    unsigned exp = (uf >> 23) & 0xFF;
    unsigned frac_v = uf & 0x7FFFFF;

    // E = exp - Bias = exp - 127
    int E = exp - 127;
    // 超过范围
    if (E >= 31) {
       return 0x80000000u;
    }
    // 小数
    if (E < 0) {
        return 0;
    }

    // M = frac + 1;
    unsigned unsigned_res = (frac_v >> (23 - E)) | (1 << E);
    if (sign) {
        return -unsigned_res;
    }
    return unsigned_res;
}

把浮点数转化为有符号整数，M = 1 + frac，frac 一共 23 位，左移 23 - E 就获得我们想要的书，但是要加上隐藏的 1，最后根据符号位取相反数就行。

floatPower2

/*
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *   (2.0 raised to the power x) for any 32-bit integer x.
 *
 *   The unsigned value that is returned should have the identical bit
 *   representation as the single-precision floating-point number 2.0^x.
 *   If the result is too small to be represented as a denorm, return
 *   0. If too large, return +INF.
 *
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatPower2(int x) {
    // 非规格化最小值
    // 0 00000000 00000000000000000000001
    // E = 1 - Bias = 1 - 127 = 126
    // frac = 1 * 2^-22
    // M = frac
    // V = 2^E * M = 2^-148 
    if (x < -148) {
        return 0;
    }

    // 非规格化最大值
    // 0 000000 111111111111111111111111
    // E = 1 - Bias = 1 - 127 = -126
    // frac = 1 (近似,小于)
    // M = frac
    // V = 2^E * M = 2^-126 (近似，小于)
    if (x < -126) {
       return 1 <<  (x + 148);
    }

    // 规格化最大值
    // 0 11111110 11111111111111111111111
    // E = exp - Bias = 254 - 127 = 127
    // M = 1 + frac = 1.111111111111111111111111
    // V = 2^E * M = 2^128 (近似,小于)
    if (x >= 128) {
        return 0xFF << 23;
    }

    // 规格化最小值
    // 0 00000001 00000000000000000000000
    // E = exp - Bias = 1 - 127 = -126
    // M = 1 + frac = 1
    // V = 2^E * M = 2^-126
    if (x >= -126) {
        int exp = x + 127;
        return  exp << 23;
    }
    return 0;
}

求 2.0^x 的浮点数表示，只要抓住几个边界条件就行。

测试一下

最后我们运行一下测试程序，发现都通过了，开心。

总结

主要考察整数和单精度浮点数的表示以及位运算，加强深对对计算机数据表示的理解。

参考

• CSAPP:Lab1-Data Lab
• 【读厚 CSAPP】I Data Lab