本文首發(fā)于我的博客

關(guān)于CS:APP

《深入理解計算機系統(tǒng)》(Computer Systems: A Programmer's Perspective;CS:APP)這本書作為CMU核心課程的核心教材衔掸，一直被眾人所推崇。這本書的主要內(nèi)容就如它的英文名稱那樣：以一個程序員的視角看待計算機系統(tǒng)（現(xiàn)在的中文書名翻譯給人一種這本書非常精深的錯覺）。實際上這本書的內(nèi)容并沒有太過于深入便脊，并且一直都作為計算機科學(xué)與技術(shù)專業(yè)低年級的計算機基礎(chǔ)課來開設(shè)馒疹。所需要的前置知識也不是很多朝群，一般來說學(xué)習(xí)過C語言之后就可以看了饮醇，并不需要提前學(xué)習(xí)匯編（本書第三章會講解匯編的基礎(chǔ)內(nèi)容）硕蛹。但個人感覺在學(xué)習(xí)過王爽的8086匯編以后學(xué)習(xí)本書的匯編會順利不少岸更。

我在三月份時得知本書第三版的英文版即將出版就早早預(yù)訂了（第三版中文翻譯版早已出版）鸵膏，苦苦等待一個月以后終于如愿成為了這版CS:APP的第一批讀者。

讀這本書的感受第一就是非常地爽怎炊，可以說這本書可以引領(lǐng)你從表層的程序一直深入到計算機內(nèi)部的運作方式中谭企，里面對于一些概念的理解也是給人一種前所未有的透徹感覺（溢出的圖形表示、補碼的權(quán)值理解等等）都切中了問題的本質(zhì)评肆。

除了書本上的內(nèi)容债查，CMU的課程官網(wǎng)上還提供了9個lab，這9個lab也一直深受CMU開設(shè)的課程的學(xué)生們的喜愛瓜挽，在lab中我們可以將在各章中學(xué)習(xí)到的知識運用到解決一個有趣的問題中盹廷，并且通過自動化的評分機制評估對知識的掌握程度。這9個lab同樣是這本書的核心內(nèi)容久橙。

Data Lab

實驗代碼見GitHub

簡介

在嚴(yán)格限制的條件下實現(xiàn)簡單的邏輯俄占、補碼管怠、浮點數(shù)操作函數(shù)。

本lab旨在幫助學(xué)生理解C中各類型的位表示和操作符對數(shù)據(jù)的位級作用行為缸榄。

所用工具

VS Code-用于代碼編寫
gcc-用于編譯

第一部分 整數(shù)

所編寫的程序必須滿足如下要求：

1. 只能使用0-255的整型常數(shù)
2. 只能使用函數(shù)參數(shù)與函數(shù)內(nèi)聲明的局部變量
3. 只能使用如下單目操作符：! ~
4. 只能使用如下雙目操作符：& ^ | + << >>
5. 最多只能使用有限個運算符（等于號渤弛、括號不計），可以認(rèn)為使用的運算符個數(shù)越少得分越高
6. 一些函數(shù)可能對操作符有更多的限制（在題目前以操作符限制給出）
7. 禁止使用任何控制結(jié)構(gòu)如 if do while for switch等
8. 禁止定義或使用任何宏
9. 禁止定義任何函數(shù)
10. 禁止調(diào)用任何函數(shù)（除了可以使用printf輸出中間變量碰凶，但提交時必須去掉）
11. 禁止使用任何形式的類型轉(zhuǎn)換
12. 禁止使用int以外的任何類型（包括結(jié)構(gòu)體暮芭、數(shù)組黎炉、聯(lián)合體）

可以假設(shè)程序在如下環(huán)境的機器上運行：

• 采用補碼表示整型
• 32位int
• 執(zhí)行算術(shù)右移
• 右移超過類型的長度時的行為未定義

bitAnd

• 要求：只用~ |實現(xiàn)x&y
• 操作符限制：~ |
• 操作符使用數(shù)量限制：8
• 思路：略

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

getByte

• 要求：取出x中的n號字節(jié)

  編號從低位到高位從0開始

• 操作符使用數(shù)量限制：6

• 思路：將x右移n*8位之后取出低8位的值

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

logicalShift

• 要求：將x邏輯右移n位（0<=n<=31)
• 操作符使用數(shù)量限制：20
• 思路：將x的最高位除去后右移n位（保證高位補0）留攒，然后使用|操作符手動將最高位移動到的位置置上x的最高位。

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

bitCount

• 要求：統(tǒng)計x的二進(jìn)制表示中1的數(shù)量

• 操作符使用數(shù)量限制：40

• 思路：

  做這道題參考了stackoverflow上的一個回答宇智，核心思想是分治：

  1. 將所有位分成32組砾莱，一組中只有1位
  2. 將相鄰兩組合為一組瑞筐，組中的數(shù)值為原來兩組中的數(shù)值相加
  3. 重復(fù)第2步，直到合成只有1組腊瑟，組中的數(shù)值即為結(jié)果

  用圖片比較便于理解：

bitCount.jpg

可以看到最終的0x0000000F即為1的數(shù)量15

該算法能成功的關(guān)鍵在于一開始中每組中的數(shù)值即為每組中1的數(shù)量聚假，然后將相鄰兩組中的數(shù)值相加的過程就相當(dāng)于將之前一級的1的數(shù)量匯總，不斷重復(fù)這個過程就可以將1的數(shù)量匯總到最后的一個數(shù)中闰非。

有了算法我們還要考慮如何在題目的限制條件下實現(xiàn)這一算法膘格。

為了實現(xiàn)將相鄰兩組中的值相加并放在合適的位置，我們采用掩碼+位移的方式财松，例如有掩碼：

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

那么`x = x & mask1 + (x >> 1) & mask1;`實現(xiàn)了相加的過程瘪贱，前面一部分先取出了一半的組，右移后再取出的就是后一半的組辆毡，再由按位相加的特點菜秦，它們相加后的值就存放在特定的位上（可以參照上面的圖理解這一過程）。

接下來只要使用不同的掩碼和不同的位移就可以一步步實現(xiàn)這一過程舶掖。

但是題目限制中我們只能使用0x00-0xFF的整型值球昨，所以掩碼也需要我們進(jìn)行構(gòu)造。

答案如下眨攘，注意到當(dāng)剩下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

• 要求：不使用!實現(xiàn)!操作符

• 操作符限制：~ & ^ | + << >>

• 操作符使用數(shù)量限制：12

• 思路：

  !操作符的含義是0變?yōu)?鲫售，非0變?yōu)?河哑，我們自然可以想到要做的是區(qū)分非零和零，零相對的非零數(shù)有一個非常明顯的特征是-0=0龟虎，而對于非零數(shù)，取負(fù)后必定是一正一負(fù)而不可能相等沙庐，利用這一點鲤妥，可以得出非零數(shù)與它的相反數(shù)進(jìn)行|運算后符號位一定為1佳吞，我們將符號位取出并取反就可以返回正確的值。

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

tmin

• 要求：返回補碼表示的整型的最小值
• 操作符使用數(shù)量限制：4
• 思路：按照補碼的權(quán)值理解棉安，只要將權(quán)為-32的位置為1即可

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

fitBits

• 要求：如果x可以l只用n位補碼表示則返回1底扳，否則返回0

  1 <= n <= 32

• 操作符使用數(shù)量限制：15

• 思路：

  如果x可以用n位補碼表示，那么左移多余的位的個數(shù)后再右移回來的數(shù)值一定與原值相等贡耽，這個方法利用了左移后溢出的位會被丟棄衷模，而右移回來時的是補符號位，如果丟棄了1或者右移時補的是1都會導(dǎo)致值的改變蒲赂，而這兩種情況也正說明了x不可以只用n位補碼表示阱冶。

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

divpwr2

• 要求：計算x/(2^n) 0 <= n <= 30 結(jié)果向零取整

• 操作符使用數(shù)量限制：15
• 思路：對于正數(shù)，我們直接把x右移n位就可以得到向零取整的結(jié)果（實際上是向下取整）滥嘴；對于負(fù)數(shù)木蹬，雖然我們右移n位可以得到結(jié)果，但是這個結(jié)果是向下取整的若皱，所以我們需要適當(dāng)?shù)丶由?來補為向零取整镊叁，那么我們什么時候需要加1呢？整除時當(dāng)然不用走触，在不能整除時就都需要加上1來調(diào)整晦譬，如何判斷是否整除？只要移出的位中有一個不為0互广，那么就表示無法整除敛腌。?

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

• 要求：計算-x
• 操作符使用數(shù)量限制：5
• 思路：略。

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

isPositive

• 要求：如果x大于0返回1兜辞，否則返回0
• 操作符使用數(shù)量限制：8
• 思路：檢測符號位與x是否為0即可迎瞧。

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

isLessOrEqual

• 要求：如果x小于等于y則返回1，否則返回0
• 操作符使用數(shù)量限制：24
• 思路：本題的基本思路是判斷x-y得到的值是否小于等于0逸吵，但是要考慮溢出帶來的影響凶硅，首先定義了兩個變量xp,yp分別表示x,y是否大于等于0。return的表達(dá)式的含義為并并非x大于等于0且y小于0的情況下（&的后半部分）扫皱，如果x-y小于或等于0或x小于零且y大于等于0足绅，則返回1。

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

• 要求：返回x求以2為底的對數(shù)的結(jié)果 向下取整
• 操作符使用數(shù)量限制：90
• 思路：本題參照了陳志浩學(xué)長的答案韩脑。
  解題算法的核心思想是二分查找氢妈，首先我們要明白這道題實際上想讓我們求的是什么，經(jīng)過觀察我們可以得出結(jié)論段多，一個數(shù)求以2為底的對數(shù)的結(jié)果就相當(dāng)于它二進(jìn)制中位置最高的1的序號（序號從零開始由低位到高位）首量。那么我們需要做的就是查找并記錄這個位置最高的1的位置。
  算法過程如下：
  1. 如果x >> 16的結(jié)果大于0，那么可以說明最高位的位置至少是16加缘，那么我們可以將結(jié)果的第4位置1（序號編號規(guī)則同上）鸭叙，因為2 ^ 4 = 16，反之置0說明結(jié)果小于16.
  2. 下面考慮兩種情況拣宏，如果第1步中x >> 16 大于0沈贝，說明我們需要在16位之后的第8位（第24位，相當(dāng)于再二分）再進(jìn)行二分查找勋乾，如果x >> 16小于0宋下，那我們需要在16位之前的第8位（第8位，相當(dāng)于再二分）進(jìn)行查找辑莫，那么我們可以得出学歧，下次查找時的范圍為x >> (8 + result) (result表示上一步得到的結(jié)果（0或16）)，這個+result的意義可以認(rèn)為是重新確定開始進(jìn)一步二分查找的位置摆昧。
     如果x >> (8 + result) 的結(jié)果大于0撩满，那么說明結(jié)果（result)的第3位必為1，相當(dāng)于在結(jié)果上加上了查找到的新位置绅你，反之第3位應(yīng)該仍為0.
  3. 按照上面的思路繼續(xù)查找到不能再二分（偏移為x >> (1 + reuslt)）伺帘，此時result中得到最終的最高位的位置。
     算法描述起來比較難忌锯，參照代碼推理幾次就可以明白其中的巧妙之處：

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;
}

第二部分 浮點數(shù)

所編寫的程序必須滿足如下要求：

1. 只能使用函數(shù)參數(shù)與函數(shù)內(nèi)聲明的局部變量
2. 最多只能使用有限個運算符（等于號伪嫁、括號不計），可以認(rèn)為使用的運算符個數(shù)越少得分越高
3. 禁止定義或使用任何宏
4. 禁止定義任何函數(shù)
5. 禁止調(diào)用任何函數(shù)（除了可以使用printf輸出中間變量偶垮，但提交時必須去掉）
6. 禁止使用任何形式的類型轉(zhuǎn)換
7. 禁止使用int张咳、unsigned以外的任何類型（包括結(jié)構(gòu)體、數(shù)組似舵、聯(lián)合體）
8. 禁止定義或使用任何浮點常量

也就是說在浮點數(shù)題目中脚猾，我們可以使用任意大小的整型數(shù)值，可以使用流程控制語句砚哗，可以使用任何操作符龙助。

float_neg

• 要求：返回-f的位級表示

  本題及以下所有的題目都采用unsigned int來存放位級表示

  所有的浮點類型都為float

  如果輸入為NaN，返回NaN

• 操作符使用數(shù)量限制：10
• 思路：對于一般的浮點數(shù)蛛芥，我們只需要對它的符號位取反就可以了提鸟。需要特殊處理的只是無窮與NaN這兩種非規(guī)格化的情況

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

float_i2f

• 要求：實現(xiàn)由int到float的類型轉(zhuǎn)換

• 操作符使用數(shù)量限制：30

• 思路：

  由于浮點數(shù)的表示中對于負(fù)數(shù)并沒有使用補碼的方式，正負(fù)號完全取決于符號位仅淑，所以對于負(fù)數(shù)輸入称勋，我們需要做的第一步工作就是把它取負(fù)為正數(shù)再進(jìn)行后面的操作。在這個過程我們需要記錄下正負(fù)涯竟，在之后的操作中需要使用赡鲜。

  由于浮點數(shù)與整數(shù)表示的不同空厌，浮點數(shù)的有效數(shù)字的位置在第0-22位的23位中，并且第一個1在規(guī)格化表示中會被省略蝗蛙，我們只需要第一個1以后的位數(shù)蝇庭，并且我們需要知道在浮點數(shù)表示中它的指數(shù)應(yīng)該為多少，所以在這個過程中我們同時需要記錄第一個1出現(xiàn)的位置并以此決定指數(shù)捡硅。

  在代碼中使用了一個i來記錄左移的位數(shù)，也就是最高位的1之前的零的個數(shù)盗棵，那么32-i就是最后的指數(shù)壮韭。

  在循環(huán)中我們將整數(shù)的有效數(shù)字提前到了最前，然后將最高位移出纹因， 這時我們用temp保存這時的狀態(tài)喷屋。供之后的舍入判斷使用。

  接下來瞭恰，我們需要將有效位移到正確的位置上屯曹，也就是向右位移9位。

  下面按照之前的記錄把符號位置上正確的值惊畏。

  現(xiàn)在已經(jīng)處理好有效數(shù)字與符號部分恶耽，下面要做的就是處理指數(shù)部分。

  之前說過32-i是指數(shù)的數(shù)值颜启，注意我們需要將這個值加上偏移量127偷俭，再放入表示指數(shù)的位置中。

  下面就要處理舍入的情況了缰盏，浮點數(shù)表示的舍入規(guī)則比較特殊涌萤，也是本題的難點。結(jié)合本題的情況進(jìn)行介紹：

  在右移之前我們保存了這時的狀態(tài)口猜，因為當(dāng)右移九位后原來的低九位如果有數(shù)據(jù)就會被舍棄负溪，我們就需要根據(jù)舍棄的這九位與未被舍棄的最后一位（也就是原數(shù)第9位，下稱第9位）來判斷舍入的情況济炎。

  如果舍棄的這九位的最高位為0川抡，那么說明舍去的數(shù)值小于保留下來的最低位表示的值的二分之一，那么我們不需要舍入冻辩。

  如果舍棄的這九位的最高位為1猖腕，并且后面的位有數(shù)值，那么說明舍去的數(shù)值大于第9位表示的值的二分之一恨闪，這個時候我們需要舍入倘感，也就是把最終結(jié)果加一。

  如果舍棄的這九位的最高位為1咙咽，并且后面的位都是0老玛，這個時候正好就是第9位表示的值的二分之一。那么這個時候我們就要看第9位，如果第9位為0蜡豹，那么不舍入麸粮。如果第9位為1，那么進(jìn)行舍入弄诲，也就是把最終結(jié)果加一。

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

• 要求：返回2*f的位級表示

• 操作符使用數(shù)量限制：30

• 思路：

  如果該浮點數(shù)是非規(guī)格化的娇唯，那么我們需要將它的有效數(shù)字部分左移一位就可以達(dá)到乘二的效果齐遵，這個過程需要注意兩個地方，第一是如果左移后如果有效數(shù)字的最高位溢出了塔插，那么正好移到了指數(shù)部分成為了一個規(guī)格化的表示形式梗摇，所以我們無需擔(dān)心左移后有效數(shù)字溢出的問題。第二是左移后會導(dǎo)致符號位被移出想许，我們需要在位移之后手動置上原來的符號位伶授。

  如果該浮點數(shù)是規(guī)格化的，那么我們只需要將它的指數(shù)部分加一流纹。

  其他情況的應(yīng)該直接返回原值糜烹。

實驗小結(jié)

作為CS:APP的第一個lab，絕大部分的題目在經(jīng)過仔細(xì)思考與測試后是可以自主完成的捧颅，但是其中的bitCount與ilog2由于需要使用分治與二分查找的算法景图，自己想出來的難度還是比較大的，在卡了兩天以后還是去查了答案碉哑。