计算机科学学习程序员

深入理解计算机系统（CS:APP) - Data Lab详解

2017-07-21  本文已影响75人  viseator

本文首发于我的博客

关于CS:APP

《深入理解计算机系统》(Computer Systems: A Programmer's Perspective;CS:APP)这本书作为CMU核心课程的核心教材，一直被众人所推崇。这本书的主要内容就如它的英文名称那样：以一个程序员的视角看待计算机系统（现在的中文书名翻译给人一种这本书非常精深的错觉）。实际上这本书的内容并没有太过于深入，并且一直都作为计算机科学与技术专业低年级的计算机基础课来开设。所需要的前置知识也不是很多，一般来说学习过C语言之后就可以看了，并不需要提前学习汇编（本书第三章会讲解汇编的基础内容）。但个人感觉在学习过王爽的8086汇编以后学习本书的汇编会顺利不少。

我在三月份时得知本书第三版的英文版即将出版就早早预订了（第三版中文翻译版早已出版），苦苦等待一个月以后终于如愿成为了这版CS:APP的第一批读者。

读这本书的感受第一就是非常地爽，可以说这本书可以引领你从表层的程序一直深入到计算机内部的运作方式中，里面对于一些概念的理解也是给人一种前所未有的透彻感觉（溢出的图形表示、补码的权值理解等等）都切中了问题的本质。

除了书本上的内容，CMU的课程官网上还提供了9个lab，这9个lab也一直深受CMU开设的课程的学生们的喜爱，在lab中我们可以将在各章中学习到的知识运用到解决一个有趣的问题中，并且通过自动化的评分机制评估对知识的掌握程度。这9个lab同样是这本书的核心内容。

Data Lab

实验代码见GitHub

简介

在严格限制的条件下实现简单的逻辑、补码、浮点数操作函数。

本lab旨在帮助学生理解C中各类型的位表示和操作符对数据的位级作用行为。

所用工具

VS Code-用于代码编写
gcc-用于编译

第一部分 整数

所编写的程序必须满足如下要求：

  1. 只能使用0-255的整型常数
  2. 只能使用函数参数与函数内声明的局部变量
  3. 只能使用如下单目操作符：! ~
  4. 只能使用如下双目操作符：& ^ | + << >>
  5. 最多只能使用有限个运算符（等于号、括号不计），可以认为使用的运算符个数越少得分越高
  6. 一些函数可能对操作符有更多的限制（在题目前以操作符限制给出）
  7. 禁止使用任何控制结构如 if do while for switch等
  8. 禁止定义或使用任何宏
  9. 禁止定义任何函数
  10. 禁止调用任何函数（除了可以使用printf输出中间变量，但提交时必须去掉）
  11. 禁止使用任何形式的类型转换
  12. 禁止使用int以外的任何类型（包括结构体、数组、联合体）

可以假设程序在如下环境的机器上运行：

bitAnd

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

getByte

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

logicalShift

int logicalShift(int x, int n) {
    int a = 1 << 31;
    return ((x & ~a) >> n) | ((!!(x & a)) << (32 + ~n));
}

bitCount

bitCount.jpg 
可以看到最终的0x0000000F即为1的数量15

该算法能成功的关键在于一开始中每组中的数值即为每组中1的数量，然后将相邻两组中的数值相加的过程就相当于将之前一级的1的数量汇总，不断重复这个过程就可以将1的数量汇总到最后的一个数中。

有了算法我们还要考虑如何在题目的限制条件下实现这一算法。

为了实现将相邻两组中的值相加并放在合适的位置，我们采用掩码+位移的方式，例如有掩码：

`int mask1 = 0x55555555 (0101...0101)`

那么`x = x & mask1 + (x >> 1) & mask1;`实现了相加的过程，前面一部分先取出了一半的组，右移后再取出的就是后一半的组，再由按位相加的特点，它们相加后的值就存放在特定的位上（可以参照上面的图理解这一过程）。

接下来只要使用不同的掩码和不同的位移就可以一步步实现这一过程。

但是题目限制中我们只能使用0x00-0xFF的整型值，所以掩码也需要我们进行构造。

答案如下，注意到当剩下4组，每组8位的时候我们就可以直接位移相加再取出低8位得到它们的和。

int bitCount(int x) {
    // referenced :
    // https://stackoverflow.com/questions/3815165/how-to-implement-bitcount-using-only-bitwise-operators
    int mask1 = 0x55;
    int mask2 = 0x33;
    int mask3 = 0x0F;
    int result = 0;
    mask1 = mask1 | (mask1 << 8);
    mask1 = mask1 | (mask1 << 16);
    mask2 = mask2 | (mask2 << 8);
    mask2 = mask2 | (mask2 << 16);
    mask3 = mask3 | (mask3 << 8);
    mask3 = mask3 | (mask3 << 16);

    result = (x & mask1) + ((x >> 1) & mask1);
    result = (result & mask2) + ((result >> 2) & mask2);
    result = (result & mask3) + ((result >> 4) & mask3);
    return (result + (result >> 8) + (result >> 16) + (result >> 24)) & 0xff;
}

bang

int bang(int x) { return 1 & (1 ^ ((x | (~x + 1)) >> 31)); }

tmin

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

fitBits

int fitsBits(int x, int n) {
    int a = 33 + ~n;
    return !((x << a >> a) ^ x);
}

divpwr2

int divpwr2(int x, int n) {
    int a = 1 << 31;
    int isALessThanZero = !!(x & a);
    int isXHasMoreBit = (!!((~(a >> (32 + ~n))) & x));
    return (x >> n) + (isXHasMoreBit & isALessThanZero);
}

negate

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

isPositive

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

isLessOrEqual

int isLessOrEqual(int x, int y) {
    int t = 1 << 31;
    int xp = !(x & t);
    int yp = !(y & t);
    int p = x + ~y + 1;
    return (!!(((!xp) & yp) | ((p & t) | !p))) & (!(xp & (!yp)));
}

ilog2

int ilog2(int x) {
    int result = 0;
    int b4 = !!(x >> 16);
    int b3 = 0;
    int b2 = 0;
    int b1 = 0;
    int b0 = 0;
    result = b4 << 4;
    b3 = !!(x >> (8 + result));
    result = result | (b3 << 3);
    b2 = !!(x >> (4 + result));
    result = result | (b2 << 2);
    b1 = !!(x >> (2 + result));
    result = result | (b1 << 1);
    b0 = !!(x >> (1 + result));
    result = result | b0;
    return result;
}

第二部分 浮点数

所编写的程序必须满足如下要求：

  1. 只能使用函数参数与函数内声明的局部变量
  2. 最多只能使用有限个运算符（等于号、括号不计），可以认为使用的运算符个数越少得分越高
  3. 禁止定义或使用任何宏
  4. 禁止定义任何函数
  5. 禁止调用任何函数（除了可以使用printf输出中间变量，但提交时必须去掉）
  6. 禁止使用任何形式的类型转换
  7. 禁止使用int、unsigned以外的任何类型（包括结构体、数组、联合体）
  8. 禁止定义或使用任何浮点常量

也就是说在浮点数题目中，我们可以使用任意大小的整型数值，可以使用流程控制语句，可以使用任何操作符。

float_neg

unsigned float_neg(unsigned uf) {
    unsigned result = uf ^ 0x80000000;
    if ((uf & 0x7F800000) == 0x7F800000 && (uf & 0x007FFFFF)) {
        result = uf;
    }
    return result;
}

float_i2f

unsigned float_i2f(int x) {
    int i = 1;
    int nega = 0;
    unsigned temp;
    unsigned result;

    if (x & 0x80000000) {
        nega = 1;
        x = ~x + 1;
    }
    if (x == 0) {
        return 0;
    }
    while ((x & 0x80000000) != 0x80000000) {
        ++i;
        x <<= 1;
    }
    result = x << 1;
    temp = result;
    result >>= 9;
    if (nega) {
        result |= 0x80000000;
    } else {
        result &= 0x7FFFFFFF;
    }
    i = (32 - i) + 127;
    result = (result & 0x807FFFFF) | (i << 23);
    if ((temp & 0x00000100) == 0x00000100) {
        if (temp & 0x000000FF) {
            return result + 1;
        } else {
            if (result & 1) {
                return result + 1;
            } else {
                return result;
            }
        }
    }
    return result;
}

float_twice

实验小结

作为CS:APP的第一个lab，绝大部分的题目在经过仔细思考与测试后是可以自主完成的，但是其中的bitCount与ilog2由于需要使用分治与二分查找的算法，自己想出来的难度还是比较大的，在卡了两天以后还是去查了答案。

上一篇 下一篇

猜你喜欢

热点阅读