po主是在讀大學生一枚,最近在學校中上ics課(introduction to computer science)并做配套的10個lab。特在此将lab内容以及我的思考解答過程與各位大神分享,希望能給真正想了解此課及這些實驗之人一些幫助。若我的所言有不當之處,也請各位多多加以指正,也算是帶一帶我這個新人,我将感激不盡。
廢話不多說,直入正題。
datalab 是初讀此課的新手将要面臨的第一個lab(po主當初花了很久才适應啊!),相對來說比較簡單,主要是關于bits-level運算的一些題目。說實話,這個lab與整門課的方向比較脫節,很多bits-level的實作也确實更像智力測試題,不過既然有,便要攻克之。在做完之後,也确實對底層bits-level運算實作的了解有頗多加深。
Q1:(藍色部分是lab要求,其中包括對要求實作的函數的解釋、舉例、可以用的bits-level操作、最多操作數以及分值,下面是我的函數實作)
很經典的bits-level實作絕對值運算,這也是我認為整個lab中唯一對以後實際應用(包括面試)有價值的運算。不用if操作的絕對值運算可以有效加快運算速度。
第一步取符号位,(正為0,負為111……1),第二步抑或操作對于正數相當于不變,對于負數相當于取反加一(即得相反數),進而完成了統一的取絕對值。
************************************************************************************************************************************************************************
Q2:
狄摩根定律,不解釋。
************************************************************************************************************************************************************************
Q3:
boring but a little hard one.
題目要求是給出最高位和最低位,完成輸出在最高位和最低位之間所有數字為1,其他位為0的一個mask。如題目所給例子即是bitMask(5,3)=(111000)2。
整體思路是建構兩個mask,分别是從左端到最高位全部是1,剩下的為0的mask1,和從左端到最低位全部是1,其他是0的mask2,并将二者抑或,即可得到所求的mask。
而中間有一些小細節有其需要注意。
第一個是(exp<<highbit)<<1之是以不寫成exp<<(highbit+1),是因為若highbit=31,此時左移(highbit+1)=32位,該操作不進行任何移位。
第二個是最後result&(exp<<lowbit)看似多餘,實際上是防止(lowbit>highbit)的情況出現,并将其置0,使其符合題目要求。
************************************************************************************************************************************************************************
Q4:
分支選擇,若x為真(x!=0)則表達式=y,若x為假(x==0)則表達式=z。
利用!操作(當x=0時!x=1,當x!=0時!x=0)容易得到。
************************************************************************************************************************************************************************
Q5:
不解釋。。看不懂的話看看math logic吧。。
************************************************************************************************************************************************************************
Q6:
要求做一個mask所有偶數位都為1,奇數位都為0。
思路就是從01->0101->01010101->......
利用左移和or操作實作很簡單。
************************************************************************************************************************************************************************
Q7:
相同兩數抑或後為0,不同數抑或後不為0.利用此性質易解。
************************************************************************************************************************************************************************
Q8:
a little difficult.
第一步做一個mask記錄x y是否相等
二三步做x-y
第四步要分xy符号相同和xy符号不同兩種情況考慮,完成并取符号位。(正則為0,負則為1111……1)
第五步是将0 和1111……1都化成一位的0or1輸出。
************************************************************************************************************************************************************************
Q9:
很簡單,取符号位再少許進行運算輸出就行。
************************************************************************************************************************************************************************
Q10:
利用隻有0|-0 的符号位是0,其他x|-x符号位是1 即可求出。
************************************************************************************************************************************************************************
Q11:
若x是2的倍數,必有x&x-1=0.
另外x還需要大于0。(即是上面的isNegative的反)
将兩個條件取和運算即可。
************************************************************************************************************************************************************************
Q12:
題目要求求出輸入值2進制中最低位的1的所在位置。
很巧妙的運算,我是通過實驗找的規律,具體證明我也無能為力,希望大神能幫忙指出!
************************************************************************************************************************************************************************
Q13:
利用其它操作符實作!操作。
思想就是壓縮法,保留出不為1的位置,最後壓縮到隻有1位,結果是0則是表明該數之前全非1,結果是1表明該數必有某一位不為0(即該數非0)。
************************************************************************************************************************************************************************
Q14:
題目要求将每個byte位置颠倒。
思想很簡單,就是利用一個mask(1111 1111)将每個byte取出來,之後再利用|操作把每個取出的byte放到應該放的位置。
************************************************************************************************************************************************************************
Q15:
終于到了最後一個大boss了!
诶話說這個題看起來好長啊。。肯定很難吧。。
仔細分析一下,其實就是要用1個加号實作3個數字相加。
初看可能沒啥思路,但是仔細一想可以想到将三個數相加化成兩個數相加,最應該直接想到的便是一個數記錄無進位結果,另一個數記錄進位情況。
三個數相加的無進位可以用抑或表示,x^y^z即可。
而進位情況則是兩個數中,兩個加數的某一位同為1時需要進位。
3個數的情況下,最多某一位相加是1+1+1 不需要考慮雙重進位的情況,那麼結果很明了了。
word1是無進位結果,word2代表進位情況(不要忘記最後左移一位!)
************************************************************************************************************************************************************************
data lab 完成!