這個(gè)lab針對(duì)的是CSAPP第二章的內(nèi)容，要想完成此lab必須對(duì)計(jì)算機(jī)信息的表示和處理非常熟悉，題目有嚴(yán)格的要求，有些題目難度很大，與其說是考編程不如說是考數(shù)學(xué)。

1、bitAnd

這一題比較容易，原理是“德摩根定律”。

2、getByte

從32位的4個(gè)字節(jié)中取出第n個(gè)字節(jié)的單字節(jié)，一個(gè)字節(jié)8位，所以8*n就是要移動(dòng)的次數(shù)，用n<<3移位代替，與0xff取&得到一個(gè)字節(jié)。

3、logicalShift

系統(tǒng)默認(rèn)是算數(shù)右移，也就是擴(kuò)展符號(hào)位。這里要求邏輯右移，最高位補(bǔ)零，所以思路就是想辦法把擴(kuò)展出來的位跟0取&，其他位跟1與。我的方法是用得到低n位為1的數(shù)，再把它移到最高位，取反后與目標(biāo)值求&即可。這里規(guī)定不能用減法，所以-1可以用~0或者~1+1表示，-n也是用同樣的辦法~n+1，就是取反加一。這里有個(gè)可能的潛在問題是當(dāng)n為0時(shí)，要移動(dòng)32位，這超出了32位系統(tǒng)的范圍，c語言沒有明確規(guī)定超出后的行為，雖然在我的電腦上結(jié)果正常，但是可能在別的機(jī)器會(huì)出問題。下面的代碼用了另一個(gè)思路，可以避免移位超限的問題。

4、bitCount

這個(gè)是我覺得最難的一道題目了，統(tǒng)計(jì)x中1的個(gè)數(shù)，難就難在不能使用循環(huán)，而且限制最大操作數(shù)40，所以必須找其他思路。下面是整個(gè)流程的說明和示意圖。

輸入x如下所示：

先構(gòu)造輔助位，如下所示：

具體辦法是先將相鄰位兩兩相加，結(jié)果就是這兩位中1的個(gè)數(shù)，保存在它倆對(duì)應(yīng)的兩個(gè)位中，

然后再相鄰的2位兩兩相加，保存在他們對(duì)應(yīng)的4個(gè)位中，

之后是相鄰的4位兩兩相加，保存在他們對(duì)應(yīng)的8個(gè)位中，

再然后相鄰的8位兩兩相加，保存在他們對(duì)應(yīng)的16位中，

最后高16位和低16位相加，得到最終的結(jié)果。

此題值得好好研究，相信還有其他解法，歡迎大家交流討論。

5、bang

此題不用！取非，原理就是判斷x中是否有1，“或 |” 可以將1保留下來，用二分法5步或下來結(jié)果就跑到最低位了，用1取&就知道是0還是1了，再與1異或就?。×?。

6、tmin

二進(jìn)制補(bǔ)碼的最小值，就是符號(hào)位1，其他位0的值,0x80000000

7、fitsBits

這題有點(diǎn)繞，不過理解二進(jìn)制補(bǔ)碼最高位是符號(hào)位就不難了。我的思路是將當(dāng)前32位的符號(hào)位與n位的符號(hào)位進(jìn)行比較，如果相同就能表示。這題測(cè)試不過，我試過網(wǎng)上的其他答案也過不了，看來是測(cè)試本身的問題。這題還有其他思路，歡迎大家交流討論。

8、divpwr2

除以2的n次就是向右移動(dòng)n位，但是要求向0舍入，負(fù)數(shù)需要加一個(gè)偏置（1<<n）-1。（x>>31）根據(jù)符號(hào)位得到全0或者全1的值。

9、negate

取反加一

10、isPositive

此題主要是對(duì)0的處理，(((x>>31)&1)^1)判斷符號(hào)位，(!(!x))判斷是否為0。

11、isLessOrEqual

此題解法也很多，思路都是異號(hào)直接通過符號(hào)位判斷大小，同號(hào)就相減判斷大小。(x^y)>>31同號(hào)為0，計(jì)算+后邊的表達(dá)式，異號(hào)為1，計(jì)算+前面的表達(dá)式。

12、ilog2

此題我用了笨辦法，剛剛好卡在所允許的最大操作數(shù)上，log2的結(jié)果剛好是x中最高位1的位置，x>0，x符號(hào)位肯定是0，最低位肯定是1，然后右移1位判斷是否是0，如果是0，就說明上一位是最高位1，之后的移位都是0，n記錄了移位后結(jié)果為0的次數(shù)，也就是低29位高位0的個(gè)數(shù)，29-n就是前29位最高位1的位置，如果第30位為1，n必然為0，30就是最高為1的位，否則29-n就是最高為1的位。之所以把30位特殊處理是可以減少操作數(shù)，n+=(!(x>>30))多一個(gè)！。

此題還有更好的辦法，如下所示：

如果b4=1,x>=(1<<16)，高16位為非0，否則b4=0高16位肯定為0，利用這點(diǎn)可以根據(jù)x>>16后判斷是否為0得出b4的值，然后在上一步的基礎(chǔ)上判斷高8位是否為0得出b3，之后在上兩步的基礎(chǔ)上判斷高4位是否為0得出b2，以此類推得出b1和b0。這種方法看著優(yōu)雅多了。

受此方法啟發(fā)，還可以用二分法找最高為1的位，效率應(yīng)該比我第一個(gè)笨辦法高不少，這里就不列代碼了，大家自行嘗試實(shí)驗(yàn)。

下面是對(duì)浮點(diǎn)數(shù)的題目，雖然考察的是浮點(diǎn)，但參數(shù)和返回值都是整型，只是二進(jìn)制層面解釋為浮點(diǎn)，所以要對(duì)浮點(diǎn)的二進(jìn)制結(jié)構(gòu)非常熟悉。

13、float_neg

浮點(diǎn)取負(fù)，對(duì)于NaN直接返回，其他情況只需要將最高位取反即可。

14、float_i2f

此題實(shí)現(xiàn)將整型數(shù)強(qiáng)轉(zhuǎn)為浮點(diǎn)型，考察的是整型與浮點(diǎn)二進(jìn)制表示之間的關(guān)系。0和tmin比較特殊，需要單獨(dú)處理，負(fù)數(shù)需要轉(zhuǎn)成正數(shù)，正數(shù)與浮點(diǎn)的關(guān)系如下圖所示：

浮點(diǎn)使用科學(xué)計(jì)數(shù)法，所以我們只需要得到符號(hào)、指數(shù)部分和小數(shù)部分，把他們合起來就可以了。

符號(hào)位簡(jiǎn)單，整數(shù)最高位是啥浮點(diǎn)最高位就是啥；

指數(shù)部分需要找出高位第一個(gè)1的位置n，127+n就是指數(shù)部分的值，但是要將它左移23位，保存在符號(hào)位后8位中；

小數(shù)部分如圖所示，通過移位操作移動(dòng)到低23位中左對(duì)齊即可。對(duì)于左移低位補(bǔ)零，沒有舍入問題，而右移由于將最低幾位舍棄了，所以需要考慮舍入問題，通常使用向偶數(shù)舍入，它類似四舍五入，但對(duì)于中間值需要根據(jù)舍入后的最低有效位的奇偶進(jìn)位（奇）或者舍棄（偶）。我們先舉個(gè)10進(jìn)制的例子：1.12、1.18、1.15、1.25舍入到小數(shù)點(diǎn)后1位，中間值是10/2=5

再看個(gè)二進(jìn)制的例子1.0100、1.0101、1.0111、1.0110、1.0010，舍入到小數(shù)點(diǎn)后2位，中間值是4/2=2,二進(jìn)制10。

理解了向偶數(shù)舍入就好辦了?？梢苑謩e判斷上面的幾種情況進(jìn)行處理，我覺得麻煩，所以我的思路是先加上舍棄位的半值，利用四舍五入，小于半值的加上半值也不會(huì)進(jìn)位，移位后自然舍棄，大于半值的加上半值會(huì)產(chǎn)生進(jìn)位，完全符合我們的需求。對(duì)于剛好半值，加上半值會(huì)進(jìn)位，但是它比較特殊，加完后舍棄的值是全0，如果最低有效位是1，說明原來是0，不該進(jìn)位，所以再減1去掉進(jìn)位。

15、float_twice

浮點(diǎn)數(shù)乘2，Nan和無窮大直接返回即可。對(duì)于非規(guī)格化的值，二進(jìn)制層面就是小數(shù)位左移1位，溢出也沒關(guān)系，剛好變成指數(shù)部分為1的規(guī)格化數(shù)，這是浮點(diǎn)數(shù)設(shè)計(jì)的妙處。對(duì)于規(guī)格化數(shù)，直接指數(shù)部分加1即可。

以上就是所有data lab的題目和解答，歡迎大家交流討論。