北郵CSAPP第二章之資訊存儲

• 為什麼使用二進制？

  二值信号能更容易地被表示、存儲、傳輸

• 三種最重要的數字表示：

1. 無符号
2. 補碼：表示有符号整數
3. 浮點數

• 計算的表示是有限數量的，是以，答案太大時，結果會溢出
• 浮點運算的精度有限，不可結合（指-1 + 1 != 0）
• 整數能表示小範圍的精确的數值，浮點數能表示大範圍的近似的數值
• 大量計算機的安全漏洞都是由于計算機算數運算的微妙細節引起的

資訊存儲

• 最小的可尋址機關：byte，8個位組成。
• 虛拟記憶體：将記憶體視作一個非常大的char數組
• 盡管C編譯器維護着指針的類型資訊，但是實際生成的機器級程式不包含這個資訊
• 每個程式對象可以視為一個位元組塊，而程式本身就是一個位元組序列

十六進制表示法

• 為什麼使用十六進制表示法：

  一個位元組8位，有16種取值，使用二進制過于冗長，使用十進制需要進制轉換。是以，十六進制剛剛好。

• 二進制、十六進制、十進制之間的互相轉換

  二進制<->十六進制，可以一次執行一個十六進制數組的轉換，4位二進制一組。不足4的倍數，将最左邊的一組用0補足。

  十六進制<->十進制：竅門：記住A、C、F對應的數字，将B、D、E的值通過計算與前三個值的關系記住(A:10 C:12 F:15)

  當x = 2^n時，隻要記住x寫成二進制就是1後面跟n個0，就很容易寫成十六進制。将n表示為i + 4j的形式。(0 <= i <= 3)(0: 0, 1: 2, 2: 4, 3: 8)

  例子：2048 = 2^11, 11 = 4 × 2 + 3，=> 0x800

十進制->十六進制：用16除，得商q與餘數r=> x = q · 16 + r。倒着來：例如餘數12 2 11 12 4，則從4開始，轉為16進制：4 C B 2 C

字資料大小

• 字長決定的最重要的系統參數：虛拟位址空間的最大大小
• 字長為w位，虛拟位址的範圍：0~2^w - 1
• 大多數64位機器能運作32位機器編譯的程式（向後相容）
• 32位程式/64位程式：程式是如何編譯的，而不是運作的機器類型
• 計算機和編譯器支援多種不同方式編碼的數字格式
• 為了避免由于編譯器不同導緻的錯誤，C99引入了一類資料類型，例如int_32t與int_64t，大小固定，不随編譯器變化而變化(stdint.h)
• char：不保證它是有符号或者無符号
• 可移植性的一個方面：使得程式對不同資料類型的确切大小不敏感
• 注意：在32位程式中，char的指針為4位，而是64位程式中，char的指針位8位

尋址與位元組順序

• 對跨多位元組對象建立兩個規則（如int）：

1. 對象位址在何處

2. 如何排序

   如int a，位址為&a = 0x100，位元組排列為0x100、0x101、0x102、0x103

• 假設一個變量值：0x01234567 高位<-低位

  ->位址變大方向

  大端法排序：01 23 45 67：高位->低位

  小端法排序：67 45 23 01：低位->高位

  大多數Intel相容機使用小端模式

雙端法：可以進行配置

實際情況：使用了特定作業系統後，位元組順序便固定了下來

Android與iOS隻能使用小端模式

• 對于大多數應用程式的程式員來說，機器使用的位元組順序是完全不可見的

  産生影響的情況：

1. 網絡傳輸時需要遵守有關位元組順序的規則
2. 小端法機器生成的機器代碼低位在左邊，高位在右邊，要反着讀
3. 編寫規避正常類型系統的程式。C語言可以使用強制類型轉換或聯合類型來允許一種資料類型引用一個與建立這個對象時定義的資料類型與該資料類型不同的對象。

#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len)  // 列印出每個十六進制表示的位元組
{
	size_t i;
	for (i = 0; i < len; i ++)
		printf(" %.2x", start[i]);
	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 *));
}

int main()
{
	int a = 2;
	show_int(a);
	show_float(a);
	show_pointer(&a);
	return 0;
}
           

• 解釋：

  将指針強制類型轉換為unsighed char*，系統就會将其視作一個位元組序列

  該指針将被看作最低位元組位址

  使用sizeof而不是一個固定的值表示其對象大小，增加其可移植性

指針值不同的原因：不同機器、作業系統使用不同的存儲配置設定規則

Linux 32、window使用4位元組的指針，linux 64使用8位元組位址

整型數與浮點數使用截然不同的編碼方法

表示字元串

• 十進制數字x的ASCII碼為：0x3x
• 使用ASCII碼作為字元碼的任何系統都是這樣的，與位元組順序和字大小順序無關。
• 文本資料比二進制資料更具平台獨立性

“12345” -> 0x31 32 33 34 35 00

表示代碼

• 二進制代碼是不相容的，二進制代碼很少能在不同機器和作業系統組合之間移植
• 不同的機器類型使用不同的且不相容的指令和編碼方式
• 從機器的角度看，程式僅僅隻是位元組序列

布爾代數簡介

• 将與、或、非、異或的布爾運算擴充到位向量的運算
• 位向量：固定長度為w、由0和1組成的串
• 布爾環：a^a = 0 ^ 0 = 1 ^ 1 = 0 => (a ^ b) ^ a = b

• 位向量 的一個應用：表示有限集合

  使用位向量 [ a w − 1 , . . . , a 1 , a 0 ] [a_{w-1}, ..., a_1, a_0] [aw−1​,...,a1​,a0​] 編碼任何子集 0 , 1 , . . . , w − 1 {0, 1, ..., w - 1} 0,1,...,w−1

• 在大量實際應用中，我們能看到使用位向量來對集合編碼

  （不是很懂）

C語言中的位級運算

• 确定一個位級表達式結果的最好方式，就是将十六進制的參數擴充成二進制表示并執行二進制計算，然後再轉換回十六進制
• 一個常見的錯誤：對布爾環沒有了解而導緻的錯誤
• 位級運算的一個常見用法是實作掩碼運算
• 掩碼：位模式，表示從一個字中選出的位的集合
• 例子：x & 0xFF = 0x000000XX，其它位元組将被覆寫
• ~0将生成一個全1的掩碼，相比于0xFFFFFFFF，這樣的代碼更具備可移植性

x ^ y = (x & ~y) | (~x & y)

C語言中的邏輯運算

• 邏輯運算：隻有0與1兩個值
• 隻有在參數僅為0與1時才與位運算有一樣的行為模式

• 重要差別二：如果第一個參數求值就能确定結果，那麼就不會對第二個參數求值

  a && 1 / a不會導緻除以0

  p && *p++

  不會導緻引用空指針

x == y <=> !(x ^ y)

C語言中的移位運算

• 左移位：向左移動k位，丢棄最高的k位，用0補足。從左至右可結合
• 右移位：分為邏輯右移和算術右移。邏輯右移：左端補k個0。算術位移：左端補k個最高有效位的值（在有符号整數的運算中很有用）
• C語言标準沒有明确定義有符号數使用哪種類型的右移，導緻任何一種隻假設其中一種的情況的代碼都有可移植性的問題
• 但是，事實上幾乎所有的實作都是采用算術右移的方式
• 而對于無符号數，右移必須是邏輯右移
• Java中，x>>k表示算術位移，x>>>k表示邏輯位移
• 在很多機器上，當移動一個w位的值時，移位指令隻考慮位移量的低log2 w位，是以實際上的位移量是通過計算k mod w得到的

int lval = 0xFEDCBA98 << 32 => 0xFEDCBA98	32 % 32 = 0
int aval = 0xFEDCBA98 >> 36 => 0xFFEDCBA9	36 % 32 = 4
           

• 但是在C語言上，這一點是沒有保證的
• 是以應當盡量避免出現k >= w的情況
• 加減法的優先級高于位移運算，是以當優先級不确定時，最好加上括号

上課筆記

對齊

請移步部落格：記憶體對齊

或CSDN部落格記憶體對齊