淺析信息的表示和處理

信息存儲

數字表示

二進制：區別于我們平時計數使用的十進制，二進制使用的是逢二進一原則，而我們的十進制則是逢十進一，比如我們十進制的 9+1 中的 9，答案應該是十，但是十應該進一，因此得出了我們常規的答案 10。在二進制里面，每一位只要大于等于 2 則都要向高位進一。為了方便表示，還衍生出了二進制的子類，比如八進制，十六進制等，主要是二進制向這些進制轉換較為容易，而計算機平時又都處理二進制數據，因此就出現了這些常見的進制計數。

信息存儲

大多數計算機使用的都是8位（在計算機中，除特殊說明外，一位均指的是二進制的位）的塊，或者叫字節，字節是作為計算機可尋址的最小單位。一般來說我們并不習慣于將一個字節寫成八位二進制的數，而是會寫成兩位十六進制的數。十六進制與二進制之間的轉換也會十分容易，舉個例子：

0x99->0b100110010x88->0b10001000

我們可以發現我們并不用像十進制那樣權值相加或者是除二取余那么麻煩，我們把一位十六進制視為四位二進制即可，這樣我們在轉換的時候就是直接每一位分別轉了，可以看出十分的方便。

字數據大小

每臺計算機都有一個字長，字長為計算機 CPU 一次能處理的最大數據，也有一種說法是能表示的最大內存。其實意思是差不多的，比如我們都知道 32 位的計算機最多能裝 4GB 的內存，再多它也是只能使用這么多的內存，那是因為 CPU 要訪問內存的時候，也只能使用一個 32 位的數據來表示地址，32位的數能表示的數的個數也就是 2^32 這么多，而地址指示的單位是字節，所以最多就是 2^32 字節，那就是熟知的 4GB 了。

C 語言中 sizeof() 會返回一個對象所占的字節數，我們對比輸出下 32 位機子和 64 位機子的各個基本數據類型所占的字節數。我們不必找兩個機子，只需要在 64 位的機子上分別編譯 32 位和 64 位的程序即可。

#include int main(){    printf("char:%d",sizeof(char));    printf("short:%d",sizeof(short));    printf("int:%d",sizeof(int));    printf("long:%d",sizeof(long));    printf("char *:%d",sizeof(char *));    printf("float:%d",sizeof(float));    printf("double:%d",sizeof(double));}

32位的結果：

64 位的結果：

我們總結出如下表格：

其實有些時候， long 的字節數也會隨機器字長有所變化的，只是好像某個版本區分了 64 位整數就叫 long long 而 long 地位與 int 一致了。但是除了這個問題，可以發現只有指針類型的數據會隨著機器字長發生變化，這也如我們所說，機器字長決定了指針就多少位，決定了有多少個地址，能用多少內存，多出的內存機器就無法做區分了。

尋址和字節順序

對于多字節的數據類型我們必須確定兩點：

1. 這個對象地址在哪里。
2. 這個對象中的字節按什么順序排列。

比如一個 int 它有四個字節，那么我定義 int a=0x12345678。首先它一定是連續排列的，因此我們確定一個 int 的地址只需要確定它的最高字節的位置即可確定整個 int 的位置。假如 int 的地址是在 0x100 的，那么它應該怎么排列這些字節呢？

我們最初可能按照慣性，認為它是按照如下方式存儲的：

字節：12  34  56  78地址：100 101 102 103

這個也很符合我們的書寫規則，但是實時卻恰恰相反，在現在大部分的機器中，它是反著存儲的。也就是：

字節：78  56  34  12地址：100 101 102 103

這兩種存儲方式我們分別叫大端序和小端序。

• 大端序：最高有效字節在低地址
• 小端序：最高有效字節在高地址

在我們書寫匯編語言的時候，要寫一個值通常也是以小端序的方式書寫的。

比如我給 eax 寄存器加上 0x12345678 你會發現它的字節碼是：

mov    $0x12345678,%eaxb8 78 56 34 12

我們通過定義以下的函數以十六進制來逐個顯示內存中的字節。

void show_bytes(void *start,size_t len){       size_t i;    for(i=0;i        printf("%.2x ",*(unsigned char *)(start+i));    printf("");}

其中 start 參數為該對象的起始地址，len 參數為顯示的字節數，可以任意定義變量調用這個函數來查看這個對象在內存中的排布，理解浮點數的時候這個函數非常有用。

來查看下面的一個例子：

void show_bytes(void *start,size_t len){       size_t i;    for(i=0;i        printf("%.2x ",*(unsigned char *)(start+i));    printf("");}int main(){    int x=0x3039;    show_bytes(&x,sizeof(x));    float y=x;    show_bytes(&y,sizeof(y));}

可以發現浮點數的輸出在整數形態下為 0x4640E400。與整數的存儲有著截然不同的結果，但是我們對這個結果的二進制適當移位就會發現它們有13個相匹配的位。

  0   0   0   0   3   0   3   90000000000000000001000000111001            4   6   4   0   E   4   0   0         01000110010000001110010000000000

我們也可以看到13個位剛好就是 int 形式下的低 13 位，這并不是巧合，大家可以試試看其它數，并且可以看看它最多能匹配多少位的整數，但是要注意結論需要有一般性，特殊的數字符合并不能得出什么結論，只能說是特性。

表示字符串

字符串的定義就是一個以 null 字符結尾的字符數組，如果將字符串看成一個數據類型的話，那么它是以大端形式存儲的，但是其實實際上應該說是數組是大端存儲的。我們在書寫的時候，一般下標 0是最小的，但是我們習慣把它稱為高位，高位在低地址便是大端序。比如 char s[]="1234"; 那么 s[0]='1',s[1]='2',s[2]='3',s[3]=4,s[4]=NULL。請注意末尾的空字節也會包括在字符串里面，但是我們算長度不會算上這個字節。在 gcc 編譯器中，我們編譯如下的程序：

#includechar s[]="0123456789ABCDEF";int main(){    char buf[16];    strcpy(buf,s);    printf("%s",s);}

編譯器會發出可能存在溢出的警告，因為在拷貝的時候會多攜帶一個 0 字節過來，這在后面堆利用中也是很常見的 off by null 的手段。

再比如我們用這樣的方式：

#includechar s[]="0123456789ABCDEF";int main(){    printf("%d",sizeof(s));}

運行我們也可以發現這個 char 數組占用了 17 個字節的空間。

布爾代數簡介

布爾代數是一個建立在二元集合集合 G={0,1} 上的定義。

非

非0即為1，非非0即為0。

與

全1為1，不全1為0

或

全0為0，不全0為1

異或

相同為0，不同為1

結論：

1. 非0為1，非1為0
2. 1與1為1，1與0為0，0與1為0，0與0為0
3. 1或1為1，1或0為1，0或1為1，0或0為0
4. 1異或1為0，1異或0為1，0異或1為1，0異或0為0

在C語言中也有一個類型是 bool，它們有特殊的運算符：

• 與：&&
• 或：||
• 非：!

不一樣的是，在進行這些運算的時候，統統會把參與運算的值轉為 bool 類型，0 就是 0，不是 0 一律都是 1

C語言當中的位級運算

位邏輯運算

我們平時C語言的位運算會擴展到每一位，位之間獨立地運算，我們可以把一個整數(int)視為32維的向量，每個維度為0或者1，對整數進行位邏輯運算相當于每一位分別做邏輯運算，每一位結果為新向量對應位的結果。在 C 語言中，以上邏輯運算對應的符號分別為：

• 非：~
• 與：&
• 或：|
• 異或：^

我們可以在只擁有非和其它任意一個雙目運算來實現所有的位邏輯運算。

比如我不用異或實現異或的功能，那么就是：

一個為 1，一個為 0 那么為或者一個為 0，一個為 1 的情況都是 1，其余都是 0。我們知道與的特性就是只有全 1 的時候為 0，那么如果我其中一個取非了，再與還是1的話就說明一個為 1 一個為 0 了，兩邊都非一下，最后把符合條件的位或一下就能得到異或的結果了。

int xor(int x,int y){    return (~x&y)|(x&~y)}

那與和或，把非運用到位了它們兩個也能運用自如自由轉換。

比如我用與和非實現或，首先我對兩個元素都非一下然后與起來，是不是就變成了：

全 0 為 1，其余為 0 了，這和或的全 0 為 0，其余為 1 差了什么？很顯然結果反了，那么我就對結果再非一下，最后就變成了：

int or(int x,int y){    return ~(~x&~y);}

或和非實現與運算同理。

移位運算

這里分邏輯移位和算數移位，其實差不多，只不過邏輯移位適用無符號整數，算數移位適用有符號整數。

分左移和右移，分別用符號 << 和 >> 來表示，假設整數一共 w 位，右移 n 位表示丟棄低 n 位，原來的高w-n 位變為低 w-n 位，高 n 位變為0。左移 n 位表示丟棄高 n 位，原來的低 w-n 位變為高 w-n 位，低 n 位變為0。

邏輯移位

左移右移就是字面意思。

算數移位

正數與邏輯移位一樣，負數則會在右移的時候高位添1。

左移x相當于對該數乘 2 的 x 次方，右移相當于對該數除 2 的 x 次方取整。

當移位的位數大于等于該整數的最大位數，則會取模再移位。

整數表示

整數我們之前講過了它的字節排布規律，但是對于負數計算機又將如何處理呢？

整數數據類型

我們先來看一張表格：

我們可以很清楚地看到，有符號數在正數和負數的范圍并不嚴格對稱，這是為什么我們接下來再看。

無符號數的編碼

無符號數的編碼就是用一個固定長度的向量來表示，每個維度上的值取 0 或者 1，那么有

這個是我們最容易理解的。

補碼編碼

有符號數因為需要表示負數，因此它規定：最高位的權值為負。

也就是說若最高位為1，而我們知道，在等比數列 ai=2^i 中，數列的前n項和永遠比第 n+1 項小 1，根據等比數列前 n 項和的公式。因此若最高位為1，那么其它位不管是是怎樣都不會使這個數變為一個正數。而前 n-1 項可以表示 0~2^n-1 的范圍，所以負數的范圍就是-2^n+0~-2^n+2^n-1 也就是我們熟知的 -2^n~-1 再加上正數表示的 0~2^n-1 連起來的范圍就是 -2^n~2^n-1 啦。

有符號與無符號數之間的轉換

隱式轉換按順序遵從以下原則：

1. 浮點數參與運算就是浮點數，出現過double則結果一定為double
2. 若都是整數參與運算則結果也是整數
3. 整數運算的結果為出現過的位數最大的整數，若最大的整數中有無符號類型的則結果無符號。

因此，如果

• 運算中有 unsigned short 和 int 則結果為 int。
• 運算中有 unsigned int 和 int 則結果為 int。
• 運算中有 unsigned int 和 float 則結果為 float。

也就不一一列舉了。

有符號與無符號的位于區別就是最高位的權值正負問題，比較的時候任意一方出現無符號則另一方也會變成無符號比較，所以如果我們做以下運算：

-1<(unsigned)1

會發現它結果為0.

因為 -1 的補碼全為 0，轉為無符號之后會變成無符號整數的最大值。

擴展一個數字的表示

將一個位數較小的整數擴展為位數較大的整數非常簡單，我們只需要在開頭添加 0 即可，但是如果是負數，則需要開頭添 1，我們運行以下代碼試試看：

#includevoid show_bytes(void *start,size_t len){       size_t i;    for(i=0;i        printf("%.2x ",*(unsigned char *)(start+i));    printf("");}int main(){    short x=0x1234;    short y=-0x1234;    show_bytes(&x,sizeof(x));    show_bytes(&y,sizeof(y));    int x1=x;    int y1=y;    show_bytes(&x1,sizeof(x1));    show_bytes(&y1,sizeof(y1));}

運行可以看到結果如我們所說。

截斷數字

有擴展，自然有截斷，當運算的結果可能超出類型所能表示的最大范圍的時候，就會發生溢出。

在無符號數或者正數當中，截斷為 w 位的整數就相當于取模 2^w ，但是截斷有負整數的時候就會發生意想不到的事情。比如負數最小值再減一那么做的運算就是：

0x80000000 0xFFFFFFFF0x17FFFFFFF

顯然多了一位，高位被截斷，最終結果為 0x7FFFFFFF ，兩個負數相加結果得出了正數，這顯然超出了我們的認知范圍。這個我們叫它負溢出。再看一個例子：正數的最大值加 1。

0x7FFFFFFF0x000000010x80000000

結果是負數的最大值，兩個正數相加得出了負數，顯然也不合理，這個我們叫他正溢出，但是正溢出并沒有發生截斷，而負溢出是由截斷引起的。

計算機歷史上，有很多安全漏洞都是因為有符號和無符號的正數引起的

無符號乘法

對于乘法有 x*y=(x*y) mod 2^w 其中 w 為 x 和 y 的位數。因為 x 和 y 相乘可能得到最大 2w 位的整數，因此會發生截斷，對于無符號來說，截斷就相當于對 2^w 取模 。

補碼乘法

這個乘法就相當于先像無符號乘法，乘出來截斷之后再轉為補碼就是結果。

乘常數

因為我們知道一個特性：移位運算相當于對 2^x 做乘除法，因此利用這個特性我們能把乘法轉成移位運算，執行乘法指令的時間比其它指令時間要長的多，因此很多編譯器在編譯常數乘法的時候會把常數二進制拆開然后分別相乘相加。

比如乘9：

9=0b1001x*9=x*8+x*1=(x<<3)+(x<<0);

但是我們會發現一個問題：如果1的位數很多那就相當于要做很多次移位和加法，最后的復雜度可能跟乘法指令差不多，但是我們可以通過另外一種姿勢避免這個問題：

15=0b1111=0b10000-0b1x*15=x*16-x*1=(x<<4)-(x<<0);

通過借一個高位，其余位權值取反之后再加1的方式避免了進行大量的運算。

除2的冪

對于2的冪，非常簡單，右移運算即可，但是需要注意：除法沒有分配律，所以乘常數的方式并不適用于除法。除法會向零取整，比如算出來結果為 3.5 則會變成 3，算出來結果 -3.5 則會變成 -3。

浮點數表示

顯然整數并不能滿足我們平時的需要，平時還需要進行大量的浮點數運算，達到太陽的質量，小到電子的質量，都需要能在計算機中表示。而這個范圍要用整數的思路表示顯然是不行的，因此我們需要有特殊的表示方法。

二進制小數

我們都知道十進制的小數，小數點左邊的數字位的權值從 10^0 開始，指數逐位遞增，而小數點右邊的數字的位的權值從 10^(-1) 開始，逐位遞減。

二進制同理，只不過權值的底數都變成了 2。

IEEE浮點數表示

這個標準規定的浮點數用如下方式表示：

里面包含了

• 符號(s)：1 表示負數，0 表示正數
• 尾數(M)：是一個二進制的小數，取值范圍為 [1,2)
• 階碼(E)：為浮點數加權。

其實這個定義就相當于二進制的科學計數法，想想原來科學計數法的定義是不是能更清晰地理解它了呢？

講完理論來講點實際的：

我們知道實際上我們經常用的浮點數有兩類，一類是 float 一類是 double，float 為 32 位，double 為 64 位。

• 對于 float，最高位表示符號位，第 2 到第 9 位表示階碼，第 10 位到第 32 位均為尾數
• 對于 double，最高位表示符號位，第 2 到第 12 位表示階碼，第 13 位到第 64 位均為尾數

我們具體以 float 來分析：

第一位是符號位沒啥大問題。后面的八位是指數，這個指數需要能表示無窮大，也要能表示無窮小，因此指數必須有正有負。我們定義一個數 Bias=2^(k-1)-1 其中 k 為階碼的位數，在 float 中，這個值為 127，在 double 中，這個值為 1023。階碼實際值 E=e-Bias，其中 e 表示階碼本身的無符號二進制的數值。然后就是這個尾數了，因為我們的范圍是 [1,2)，在這個范圍內的小鼠，不難發現小數點前有一位一直是 0，因此這個 0 我們就不必多花一位存儲它了，因此我們的尾數都是小數點后的值。

如果一個 32 位浮點數在內存中的二進制表示如下：

bin:0b01000000010000000000000000000hex:0x40400000

那么可以發現它是正數，階碼為 128，尾數為 100000……，因為小數點后面的0都能忽略，因此尾數實際就是 1。然后注意這個階碼并不是真正的實際值，這只是它表面上看上去的值，再給它減去一個 127 之后可以發現指數為 1。小數位數因為有一個隱含的 1，所以它的實際值為 1.1，十進制值就是 1.5，所以最后結果就是 1.5*2^1=3。

然后我們再運行程序看看 3 的字節顯示。

#includevoid show_bytes(void *start,size_t len){       size_t i;    for(i=0;i        printf("%.2x ",*(unsigned char *)(start+i));    printf("");}int main(){    float x=3.0;    show_bytes(&x,sizeof(x));}

運行之后可以發現與我們上面書寫的十六進制值一致。

浮點數還有 3中表示值的情況。

（1）規格化的值：這是最普遍的情況，階碼位不為全 0 也不為全 1。

（2）非規格化的值：當階碼位全為 0 的時候，表示非規格化的值，這個非規格化的意思就是跟我們上面介紹的規律稍稍有點不一樣，此時尾數是不帶隱含的 1 的，也就是說它的有效數字直接是從尾數開始的，因此它和階碼位模式為00000001 的指數一樣，但是有效數字多一個小數點前的 1，因為這樣表示能夠使得非規格化數值向規格化數值轉化更為平滑。

（3）特殊值：包括 INF 和 NAN，階碼位全為 1 的時候，若尾數全為0，則得到 INF，若不全為 0 則得到 NAN。

舍入

浮點數因為表達的不是一個具體的數，只是一個近似值，因此在精度不夠的情況，只能選擇舍掉一些精度保證能夠存儲。如何舍入便成為了一項難題，目前一共有四種舍入方式：下面我們給出一些例子：

后面三個方式還好，應該都能理解，主要是這個向偶數舍入，它首先滿足：被舍入的值不超過最小單位的一半則丟棄，若超過一半則加上一個最小單位，若等于一半則一定會使得舍入的結果為偶數個最小計量單位。

浮點運算

在進行浮點數加減法的時候，首先需要對階，小階向大階對齊，然后尾數相加。由于特殊值的存在，浮點數加減法并不滿足交換規則，因此它不是一個阿貝爾群，很多整數規律不適用。

比如最經典的：

1+1e111-1e111!=1e111-1e111+1

小結

這里來回答一下之前遺留的一個問題，那就是為什么整數轉為浮點數之后會有部分位相匹配。其實不難發現是因為浮點數的尾數基本是和原二進制的值一致的。比如下面的一個數：

1001001010101

轉為浮點數之后就會變成：

1.001001010101*2^12

這個尾數是與原二進制的值一致的，想到這里你肯定明白了之前的那個問題了。

CSAPP:datalab

終于到了最激動的實驗環節了，原先我對這本書并沒有很深的了解，直接上手做的實驗，不會就搜，現在看完一遍之后感覺理解很多，做實驗基本也是暢通無阻。

用給定的運算符實現函數的功能，解壓得到源碼之后在 bits.c 中編寫自己的代碼，然后要查看結果可以使用如下命令：

$make$./btest

實驗規定并非強制，但是想獲得提升還是嚴格遵守它給定的條件。

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

只允許使用位運算 ~ 和 & 實現按位異或，這個我們在上面有寫過，只不過沒有合在一起，稍微轉換一下即可，反正實現的思想就是要位之間不一樣才返回 1。

答案

int bitXor(int x, int y) {    return ~(~(~x&y)&~(x&~y));}

tmin

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

獲得整數的最小值，最小值就是我們喜聞樂見的 -2147483648 啦，但是我們稍微轉換一下思路，最小就是最高位一個0，用個 1，然后移位運算把它移到最高位即可。

答案

int tmin(void) {    return 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 2;}

判斷 x 是否為最大值，最大值應該是最小值取反，然后判斷是否一樣我們使用異或運算，異或只有在兩邊相等時才返回 0，我們用非運算符反一下就可以了。

答案

int isTmax(int x) {    return !((~(1<<31))^x);}

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) {    return 2;}

判斷 x 是否奇數位上全為 1。全 1 我們直接用一個立即數好了 0xAAAAAAAA，然后與屏蔽偶數位之后判斷是否相等即可。

答案

int allOddBits(int x) {    return !((0xAAAAAAAA&x)^0xAAAAAAAA);}

negate

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

實現對一個數取負，取負的話就是取反再加一即可。

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

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){    return 2;}

判斷一個整數是否在 ASCII 碼的數字位置，再轉換一下就是滿足這個條件：

x-0x30>=0  && x-0x3a<0

我們的目標就是判斷 x-0x30 是否為非負數，x-0x3a 是否為負數，也許需要考慮溢出，但是結果發現不需要，因為這個是兩邊判斷的。

答案

int isAsciiDigit(int x){//x-0x30>=0  && x-0x3a<0    return !((x+(~0x30+1))&(1<<31))&!!((x+(~0x3a+1))&(1<<31));}

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) {    return 2;}

相當于實現運算 x?y:z，如果 x 為 0 則返回 x，如果不為 0 則返回 y。

我們先把 x取值變為只有 0 和 -1。用掩碼的思路，如過結果為 -1 則說明位模式全為 1，相與的結果就是另一個數本身，如果是 0 則不論與誰結果都是 0，我們讓 x 與 y，讓 ~x 與 z，最后得到的兩個值或起來即可。x 如果是 -1 則返回 y ，如果是 0 則返回 z。得到 x 我們只要非兩次，再取負即可，就達到了我們的要求了。

int conditional(int x, int y, int z) {    x=~(!!x)+1;    return (x&y)|(~x&z);}

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) {  return 2;}

實現一個小于等于的功能，這里需要注意的是不能直接相減，會有溢出。

因此我們選擇先判斷符號位，符號位一致再相減一定不會溢出，符號不一致則強行返回不一致的結果，一致則返回直接相減的結果。首先我們先拿兩個變量保存符號的結果，然后再判斷符號是否一致，一致則屏蔽符號的結果，不一致則屏蔽相減的結果。

這里好好再理解一下，仔細看 signx^signy 和 !(signx^signy) 如何起到屏蔽答案的效果。

答案

int isLessOrEqual(int x, int y) {//y-x>=0    int signx=!(x&(1<<31));    int signy=!(y&(1<<31));    int sign=(signx^signy)&signy;//若不一致則返回y是否為非負數    x=x&0x7fffffff;    y=y&0x7fffffff;    return sign|(!(((y+(~x+1))&(1<<31))))&(!(signx^signy));}

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) {    return 2;}

實現邏輯非的功能，我們這里需要研究一下 0 的特性，0 是除了 TMIN 以外的負數值等于自己本身的數了。然后再判斷一下最高位即可。

答案

int logicalNeg(int x) {    return ((x|(~x+1))>>31)+1;}

howManyBits

/* howManyBits - return the minimum number of bits required to represent x in *             two's complement *  Examples: howManyBits(12) = 5 *            howManyBits(298) = 10 *            howManyBits(-5) = 4 *            howManyBits(0)  = 1 *            howManyBits(-1) = 1 *            howManyBits(0x80000000) = 32 *  Legal ops: ! ~ & ^ | + << >> *  Max ops: 90 *  Rating: 4 */int howManyBits(int x) {    return 2;}

這題挺難的，首先要想到一個二分，然后要注意正數需要多一位，負數不需要。假如我給了你 0x7fffffff，那么你肯定要 32 位，雖然我只有 31 位有效數字。我給你個 -1 那一位就夠了，因為一位的范圍就是 -1~0。

我們先判斷高 16 位是否有 1，若有則判斷高 16 位，答案加上 16，否則判斷低 16 位。

再判斷的 16 位中，判斷高 8 位是否有 1，若有則繼續判斷高 8 位，答案加上8，否則判斷低 8 位。

直到判完。我一開始想到了這個：

int howManyBits(int x) {    int sign=!(>>31);    int b16=(!!((x>>16)&0xffff))<<4;    x=x>>b16;    x=x&0xffff;    int b8=(!!((x>>8)&0xff))<<3;    x=x>>b8;    int b4=(!!((x>>4)&0xf))<<2;    x=x>>b4;    int b2=(!!((x>>2)&0x3))<<1;    x=x>>b2;    int b1=(!!((x>>1)&0x1))<<0;    x=x>>b1;    printf("%d %d %d %d %d %d %d",b16,b8,b4,b2,b1,x,sign);    return b16+b8+b4+b2+b1+sign+x;}

但是經過多方調試還是輸給了 -1 這個測試點。后來想到如果負數則取反即可，然后符號位就默認給它加著上去即可。

答案

int howManyBits(int x) {    int sign=x>>31;    x = (sign&~x)|(~sign&x);    int b16=(!!((x>>16)&0xffff))<<4;    x=x>>b16;    x=x&0xffff;    int b8=(!!((x>>8)&0xff))<<3;    x=x>>b8;    int b4=(!!((x>>4)&0xf))<<2;    x=x>>b4;    int b2=(!!((x>>2)&0x3))<<1;    x=x>>b2;    int b1=(!!((x>>1)&0x1))<<0;    x=x>>b1;    return b16+b8+b4+b2+b1+X+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) {    return 2;}

就是返回一個浮點數乘 2。首先排除掉那些特殊值： NAN，INF 和 0，乘二返回指數 +1 即可。

答案

unsigned floatScale2(unsigned uf) {    int exp = (uf&0x7f800000)>>23;    int sign = uf&(1<<31);    if(exp==0) return uf<<1|sign;    if(exp==255) return uf;    exp++;    if(exp==255) return 0x7f800000|sign;    return (exp<<23)|(uf&0x807fffff);}

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) {    return 2;}

實現一個類似是強制轉換的東西吧，首先還是按照浮點數的規則把各個字段提取出來，然后特判移位就行了。

答案

int floatFloat2Int(unsigned uf) {    int s=uf>>31;    int exp=((uf&0x7f800000)>>23)-127;    int frac=(uf&0x007fffff)|0x00800000;    if(!(uf&0x7fffffff)) return 0;     if(exp>31)return 0x80000000;    if(exp<0) return 0;     if(exp>23)frac<<=(exp-23);    else frac>>=(23-exp);     if(!((frac>>31)^s)) return frac;    else if(frac>>31) return 0x80000000;    else return ~frac+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) {    return 2;}

實現運算 pow(2,x)，返回結果為 int 雖然我們可以直接 1<

首先防止溢出先判斷，因為是 2 的整數次方，所以它的結果就是 (exp+127)<<23，然后判斷無窮小和溢出即可，這個比較簡單。

答案

unsigned floatPower2(int x) {    int INF = 0xff<<23;    int exp = x + 127;    if(exp <= 0) return 0;    if(exp >= 255) return INF;    return exp << 23;}

需要注意，由于最后一個題目測試數據比較多，因此要修改時限才能通過。我也不知道我算法有什么問題，這 O(1) 的復雜度也不知道上哪優化去。

result

小結

CSAPP，入門二進制必備書籍，二刷都能感覺學到了很多以前沒學到的東西，接下來沒以前認真看的也都得去看一遍了。