信息存儲(chǔ)
大多數(shù)計(jì)算機(jī)以字節(jié)（1 byte = 8 bits）作為最小可尋址的內(nèi)存單位。
虛擬內(nèi)存：機(jī)器級(jí)程序?qū)?nèi)存視為字節(jié)數(shù)組。
地址：標(biāo)識(shí)每個(gè)字節(jié)的唯一數(shù)字。
虛擬地址空間[1]：所有可能的地址集合。
十六進(jìn)制
十六進(jìn)制的表示
-
前綴0x/0X，字母可用大寫A - F或小寫a - f
記住A，C，F(xiàn)的十進(jìn)制值
十六進(jìn)制與二進(jìn)制、十進(jìn)制的轉(zhuǎn)化
十六進(jìn)制&二進(jìn)制：四位二進(jìn)制轉(zhuǎn)化為一位十六進(jìn)制，位數(shù)缺少時(shí)整數(shù)部分左側(cè)補(bǔ)零，小數(shù)部分右側(cè)補(bǔ)零。
-
十六進(jìn)制&十進(jìn)制：乘除法
2的非負(fù)整數(shù)n次冪轉(zhuǎn)化為十六進(jìn)制：n = i + 4 * j （i = 1, 2, 3）時(shí)，十六進(jìn)制表示為2的 i 次方后有 j 個(gè)0
字?jǐn)?shù)據(jù)大小
字長(zhǎng)決定了虛擬地址空間的最大大?。鹤珠L(zhǎng)w位，虛擬地址范圍為0 ~ 2^w - 1，即可以訪問(wèn)2^w個(gè)字節(jié)。
程序時(shí)32位還是64位取決于它是如何編譯的。
尋址和字節(jié)順序
多字節(jié)對(duì)象被存儲(chǔ)為連續(xù)的字節(jié)序列。
-
字節(jié)存儲(chǔ)順序：一個(gè)數(shù)據(jù)類型內(nèi)部字節(jié)的存儲(chǔ)順序
大端法：高位字節(jié)優(yōu)先存儲(chǔ)
-
小端法：低位字節(jié)優(yōu)先存儲(chǔ)
大端法（big endian）和小端法（little endian）取自《格列佛游記》中打破雞蛋的方式。原文暗諷英法兩國(guó)持續(xù)的戰(zhàn)爭(zhēng)，而這里則暗示選擇兩種存儲(chǔ)順序沒(méi)有技術(shù)上的理由，無(wú)謂好壞。
-
需要注意字節(jié)存儲(chǔ)順序的三種情況
不同機(jī)器通過(guò)網(wǎng)絡(luò)傳送二進(jìn)制數(shù)時(shí)，由小端法機(jī)器傳送給大端法機(jī)器的字節(jié)順序會(huì)被認(rèn)為是反序，反之亦然。此時(shí)應(yīng)統(tǒng)一編寫網(wǎng)絡(luò)應(yīng)用程序的字節(jié)順序規(guī)則，由發(fā)送方機(jī)器將其內(nèi)部表示先轉(zhuǎn)化為網(wǎng)絡(luò)標(biāo)準(zhǔn)，再由接收方機(jī)器將收到的網(wǎng)絡(luò)標(biāo)準(zhǔn)轉(zhuǎn)化為其內(nèi)部表示。
閱讀小端法機(jī)器的程序表示時(shí)。
-
規(guī)避正常類型系統(tǒng)時(shí)，即運(yùn)用了強(qiáng)制類型轉(zhuǎn)換或聯(lián)合。例如：運(yùn)用強(qiáng)制類型轉(zhuǎn)換生成對(duì)象的字節(jié)表示。
#include<stdio.h> typedef unsigned char *byte_pointer; //指向字節(jié)序列的指針 void show_bytes(byte_pointer start, size_t len){ size_t i; //size_t是表示數(shù)據(jù)結(jié)構(gòu)大小的首選數(shù)據(jù)類型(這里為sizeof的結(jié)果) for(i = 0; i < len; i++) printf("%.2x", start[i]); //%.2x表示兩位16進(jìn)制數(shù) printf("\n"); } void show_int(int x){ show_bytes((byte_pointer) &x, sizeof(int)); } void show_float(float x){ show_bytes((byte_pointer) &x, sizeof(float)); } void show_pointer(void *x){ show_bytes((byte_pointer) &x, sizeof(void *)); } //這里的強(qiáng)制類型轉(zhuǎn)換并未改變指針, 只是告訴編譯器以新的數(shù)據(jù)類型看待被指向的數(shù)據(jù) //例如, show_int中將&x看作int指針時(shí), 進(jìn)入"下一個(gè)"地址會(huì)跨越四個(gè)字節(jié); 看作char指針時(shí), 進(jìn)入"下一個(gè)"地址只會(huì)跨越1個(gè)字節(jié)
表示字符串
- 字符串編碼以null(0x00)結(jié)尾。
- 最常見(jiàn)的字符編碼是ASCII碼。字符串的字節(jié)序列在使用ASCII編碼的任何系統(tǒng)上都有相同結(jié)果，與字節(jié)順序規(guī)則和字長(zhǎng)大小無(wú)關(guān)。
表示代碼
- 從機(jī)器的角度看，程序代碼只是字節(jié)序列。
- 不同機(jī)器對(duì)于相同程序的二進(jìn)制編碼不同且不兼容。
布爾代數(shù)
- 位向量可用于表示有限集合的子集，位向量的與或非等價(jià)于集合的交并補(bǔ)。
- 布爾代數(shù)與整數(shù)算術(shù)有相似之處：交換律，結(jié)合律，分配律（布爾代數(shù)的分配律可以理解為對(duì)整數(shù)算術(shù)分配律的推廣。因?yàn)椴紶柎鷶?shù)中，不僅&對(duì)|有分配律，|對(duì)&也有分配律）
C語(yǔ)言中相關(guān)運(yùn)算
位級(jí)運(yùn)算：&，|，~
-
掩碼運(yùn)算。掩碼表示從一個(gè)字中選出的位的集合，如0xFF表示一個(gè)字低位字節(jié)都是1。x&0xFF表示x的最低字節(jié)不變，其他字節(jié)都被置為0。
習(xí)題2.10&2.11
注意：指向相同地址的兩個(gè)指針，改變其中一個(gè)，則另一個(gè)也會(huì)變
#include<stdio.h> #include<stdlib.h> void inplace_swap(int *x, int *y){ *y = *x ^ *y; *x = *x ^ *y; *y = *x ^ *y; } void reverse_array(int a[], int cnt){ int first, last; for(first = 0, last = cnt - 1; first <= last; first++, last--) inplace_swap(&a[first], &a[last]); } int main(){ int a[5] = {1, 2, 3, 4, 5}; reverse_array(a, 5); for(int i = 0; i < 5; i++) printf("%d", a[i]); //最終結(jié)果為{5，4，0，2，1}, first = last時(shí), *x = *y, *y = *x ^ *y = 0時(shí), *x也被置為0 return 0; }
邏輯運(yùn)算：&&，||，！
- 邏輯運(yùn)算中，只有0（FALSE）和1（TRUE），所有非零參數(shù)均表示1（TRUE）
- 邏輯運(yùn)算具有提前終止的特點(diǎn)。當(dāng)?shù)谝粋€(gè)參數(shù)就能確定表達(dá)式的值時(shí)，就不會(huì)計(jì)算第二個(gè)參數(shù)。
移位運(yùn)算：<<，>>
- 左移即在低位補(bǔ)0。右移分為邏輯右移和算術(shù)右移。邏輯右移在高位補(bǔ)0，算術(shù)右移在高位補(bǔ)符號(hào)位。
- 由w位組成的數(shù)據(jù)，移動(dòng)k位。若k>w，則只視為移動(dòng)k mod w位。移位指令只考慮移位量k的低logw位。
- 移位運(yùn)算符合左結(jié)合律：x<<j<<k = (x<<j)<<k
- 移位運(yùn)算優(yōu)先級(jí)低于加減法：x<<a+b<<k = (x<<(a+b))<<k
整數(shù)表示
整形數(shù)據(jù)表示
- unsigned / (signed) + char, short, int, long
- 數(shù)據(jù)類型取圍：32位、64位、C語(yǔ)言標(biāo)準(zhǔn)均有不同
編碼
無(wú)符號(hào)數(shù)(Unsigned)
- B2U
- UMax, UMin
- 無(wú)符號(hào)數(shù)編碼具有唯一性（B2U是雙射）
補(bǔ)碼(Two's-Complement)
B2T
-
TMax, TMin
-TMax = 0 - TMax = TMax
補(bǔ)碼編碼具有唯一性（B2T是雙射）
|TMin| = TMax + 1
UMax = 2 * TMax + 1
-1和UMax有相同的位模式
-
有符號(hào)數(shù)的其他表示方法
- 原碼(Sign-Magnitude)
- 反碼(Ones'-Complement)：對(duì)于無(wú)符號(hào)數(shù)x，-x的w位表示在反碼中相當(dāng)于[11…1] - x，在補(bǔ)碼中相當(dāng)于2^w - x
無(wú)符號(hào)數(shù)和有符號(hào)數(shù)之間的轉(zhuǎn)換
保持位模式不變
對(duì)于x，0≤x≤TMax時(shí)T2U(x) = U2T(x)，否則轉(zhuǎn)換時(shí)需對(duì)x加上或減去2^w
C語(yǔ)言中無(wú)符號(hào)數(shù)與有符號(hào)數(shù)的轉(zhuǎn)換
- 顯示轉(zhuǎn)換：強(qiáng)制類型轉(zhuǎn)換
- 隱式轉(zhuǎn)換
- 不同類型變量賦值：保持被賦值的變量類型不變
- 輸出函數(shù)printf中通過(guò)"%d"與"%u"進(jìn)行轉(zhuǎn)換
- 運(yùn)算中，如果有符號(hào)數(shù)和無(wú)符號(hào)數(shù)同時(shí)出現(xiàn)，則視為無(wú)符號(hào)運(yùn)算
擴(kuò)展位表示
- 無(wú)符號(hào)數(shù)進(jìn)行零擴(kuò)展，值不變。
- 有符號(hào)數(shù)進(jìn)行符號(hào)擴(kuò)展，值不變。
- 高位全是1和只有最高位為1對(duì)數(shù)值大小沒(méi)有影響，可用于簡(jiǎn)化運(yùn)算。
截?cái)鄶?shù)字
- 直接截?cái)喔呶弧?/li>
- 無(wú)符號(hào)數(shù)相當(dāng)于取模（x%2^w = x'）
- 有符號(hào)數(shù)相當(dāng)于轉(zhuǎn)化為無(wú)符號(hào)數(shù)取模后，再轉(zhuǎn)化為有符號(hào)數(shù)。
有符號(hào)數(shù)和無(wú)符號(hào)數(shù)之間的轉(zhuǎn)換容易引起錯(cuò)誤。詳見(jiàn)習(xí)題。
整數(shù)運(yùn)算
模數(shù)運(yùn)算形成數(shù)學(xué)結(jié)構(gòu)：阿貝爾群
無(wú)符號(hào)數(shù)運(yùn)算和補(bǔ)碼運(yùn)算有完全相同的位級(jí)表示。
加法
無(wú)符號(hào)加法
正常情況x+y的值保持不變，溢出情況的結(jié)果是x+y-2^w
檢測(cè)無(wú)符號(hào)加法的溢出：對(duì)于無(wú)符號(hào)數(shù)s=x+y，當(dāng)且僅當(dāng)s<x（等價(jià)地，s<y）時(shí)，發(fā)生溢出
補(bǔ)碼加法
正常情況x+y的值不變，正溢出情況結(jié)果是，負(fù)溢出情況結(jié)果是
。
檢測(cè)補(bǔ)碼加法的溢出：對(duì)于補(bǔ)碼s=x+y，當(dāng)且僅當(dāng)x<0，y<0，s≥0時(shí)，發(fā)生負(fù)溢出；當(dāng)且僅當(dāng)x>0，y>0，s≤0時(shí)，發(fā)生正溢出。
取非
得到取非結(jié)果的位級(jí)表示的方法：①按位取反后加一。②設(shè)k是最右邊的1的位置，對(duì)k左邊所有位取反即可。
無(wú)符號(hào)數(shù)
對(duì)于無(wú)符號(hào)數(shù)-x，x=0時(shí)結(jié)果是其本身，否則結(jié)果是2^w-x
補(bǔ)碼
對(duì)于補(bǔ)碼-x，x=TMin時(shí)結(jié)果是其本身，否則結(jié)果是-x
乘法
無(wú)符號(hào)數(shù)
x * y=(x * y) mod 2^w
補(bǔ)碼
將結(jié)果位級(jí)表示轉(zhuǎn)化為補(bǔ)碼即可
乘以常數(shù)
與2的冪相乘
與2的k次冪相乘轉(zhuǎn)化為左移k位實(shí)現(xiàn)。
與任意常數(shù)相乘
將常數(shù)K表示為0和1交替的二進(jìn)制序列，將乘法運(yùn)算轉(zhuǎn)化為移位運(yùn)算和加減法的組合。
設(shè)K的二進(jìn)制表示中所有的1連續(xù)出現(xiàn)，且從位置n到位置m有連續(xù)的1
形式1：x * K = (x<<n )+ (x<<(n-1)) + ... + (x<<m)
形式2：x * K = (x<<(n+1)) - (x<<m)
不符合條件的情況可通過(guò)變換得到。
除以2的冪
無(wú)符號(hào)數(shù)
除以2的k次冪轉(zhuǎn)化為右移k位實(shí)現(xiàn)，得到向下取整的結(jié)果。
補(bǔ)碼
正數(shù)向下取整：除以2的k次冪轉(zhuǎn)化為右移k位實(shí)現(xiàn)
負(fù)數(shù)向上取整：除以2的k次冪轉(zhuǎn)化為，先加偏置量2^k-1=(1<<k)-1，后右移k位
- 原理：
“溢出”是針對(duì)碼值轉(zhuǎn)化為數(shù)值后，不符合直觀運(yùn)算規(guī)則而言的。但實(shí)際上碼值運(yùn)算規(guī)則無(wú)謂“溢出”，永遠(yuǎn)符合相同規(guī)則。如A+B=C就有C-B=A。
浮點(diǎn)數(shù)
二進(jìn)制小數(shù)
IEEE浮點(diǎn)表示
符號(hào)s：0正1負(fù)
尾數(shù)M：1 ~ 2-ε 或 0 ~ 1-ε
階碼E
符號(hào)位s編碼符號(hào)s
k位階碼字段exp編碼E
n位小數(shù)字段frac編碼M
- IEEE編碼保證了從非規(guī)格化到規(guī)格化的平滑過(guò)渡
規(guī)格化
E=Exp-Bias
- Exp是exp的無(wú)符號(hào)整數(shù)值
- Bias=
- exp≠00…0且exp≠11…1
- M=1.frac
非規(guī)格化
E=1-Bias
- Bias=2^k-1
- exp=00…0
- M=0.frac
- 用于表示0附近的小數(shù)值
特殊值
無(wú)窮大
exp=11...1，frac=00...0
NaN(Not-a-Number)
exp=11...1，frac≠00...0
舍入規(guī)則
- 向偶數(shù)舍入：四舍六入五湊偶
- 改變編碼格式時(shí)，對(duì)于非規(guī)格化表示，先考慮能否轉(zhuǎn)化為規(guī)格化保留精確度，否則再舍入
- 其他舍入方式：向0舍入，向下舍入，向上舍入
浮點(diǎn)運(yùn)算
加法
- 滿足交換律，不滿足結(jié)合律
- 除了無(wú)窮和NaN之外都有逆元
- 符合單調(diào)性：若a≥b，則x+a≥x+b（a,b,x為除NaN之外的任意值）。無(wú)符號(hào)數(shù)和補(bǔ)碼加法不符合單調(diào)性。
乘法
- 滿足交換律，不滿足結(jié)合律
- 乘法對(duì)加法不滿足分配律
- 符合單調(diào)性：a≥b，若c≥0，則a * c ≥ b * c；若c≤0，則a * c ≤ b * c（a,b,c為除NaN之外的值）無(wú)符號(hào)數(shù)和補(bǔ)碼乘法不符合單調(diào)性。
- a * a ≥ 0（a≠NaN）
類型轉(zhuǎn)換
- int -> float 不會(huì)溢出，但可能舍入
- int/float -> double 不會(huì)溢出，保留精度
- double -> float 可能溢出或者舍入
- float/double -> int 向0舍入，或在無(wú)法確定整數(shù)近似值時(shí)（例如溢出）產(chǎn)生TMin
-
對(duì)于程序存儲(chǔ)的管理完全是在虛擬地址空間中進(jìn)行的。例如，指針指向的就是字節(jié)塊的虛擬地址。 ?
