資訊安全系統設計基礎第三周學習總結

第二章  資訊的表示和處理

一、前言

1、二進制數字稱為位（bit）

2、三種重要的數字表示：無符号編碼、補碼（有符号）、浮點數（科學計數法）

3、浮點運算雖然溢出會産生特殊的值 + ∞,但是一組正數的乘積總是正的。由于表示的精度有限,浮點運算是不可結合的。 整數運算和浮點數運算會有不同的數學屬性是因為它們處理數字表示有限性的方式不同—整數的表 示雖然隻能編碼一個相對較小的數值範圍,但是這種表示是精确的 ;而浮點數雖然可以編碼一個較大的數值範圍,但是這種表示隻是近似的。 

二、資訊存儲

1、大多數計算機使用 8 位的塊,或者位元組(byte),作為 最小的可尋址的存儲器機關。機器級程式将存儲器視為一個非常大的位元組數組,稱為虛拟存儲器(virtual memory)。存儲器的每個位元組都由 一個唯一的數字來辨別,稱為它的位址(address),所有可能位址的集合稱為虛拟位址空間(virtual address space)。

2、編譯器和運作時系統是如何将存儲器空間劃分為更可管理的單 元,以存放不同的程式對象(program object),即程式資料、指令和控制資訊。 C 語言中 一個指針的值(無論它是指向一個整數、一個結構或是某個其他程式對象)都是某個存儲塊的第 一個位元組的虛拟位址。 

3、十六進制表示法

一個位元組由 8 位組成。在二進制表示法中,它的值域是 000000002 ~ 111111112 ;如果用十進制整數表示,它的值域就是 0 ~ 255。以 16 為基 數,或者叫十六進制(hexadecimal)數,來表示位模式。十六進制(簡寫為“hex”)使用數字‘0’~‘9’,以及字元‘A’~‘F’來表示 16 個可能的值。用十六進制書寫,一個位元組的值域為 0016 ~ FF16。 

以 0x 或 0X 開頭的數字常量被認為是十六進制的值。字元‘A’~‘F’既可以 是大寫,也可以是小寫,甚至是大小寫混合。 

編寫機器級程式的一個常見任務就是在位模式的十進制、二進制和十六進制表示之間人工進 行轉換。 

當 n 表 示 成 i + 4 j 的 形 式 , 其 中 0 ≤ i ≤ 3 時 , 我 們 可 以 把 x 寫 成 開 頭 的 十 六 進 制 數 字 為 1( i = 0 )、2( i = 1 )、 4(i=2)或者 8(i=3) 

4、每台計算機都有一個字長(word size),指明整數和指針資料的标稱大小(nominal size)。因 為虛拟位址是以這樣的一個字來編碼的,是以字長決定的最重要的系統參數就是虛拟位址空間的 最大大小。對于一個字長為 w 位的機器而言,虛拟位址的範圍為 0 ~ 2w-1,程式最多 通路 2w 個位元組。 

5、資料大小

C 的資料類型 char 表示一個單獨的位元組。盡管 “char”是由于它被用來存儲文本串中的單個字元這一事實而得名,但它也能用來存儲整數值。

C 的資料類型 int 之前還能加上限定詞 short、long,以及最近的 long long,以提供各種 大小的整數表示。 

準确的位元組數依賴于機 器和編譯器。“短”整數配置設定有 2 個字 節,而不加限定的 int 為 4 個位元組。“長”整數使用機器的全字長。ISO C99 引入的“長長”整 數資料類型允許 64 位整數。

單精度(在 C 中聲明為 float)和雙精度(在 C 中聲明為 double)。格式分别使用 4 位元組和 8 位元組。 

6、尋址和位元組順序

這個對象的位址是什麼,以及在存 儲器中如何排列這些位元組。

某些機器選擇在存儲器中按照從最低有效位元組到最高 有效位元組的順序存儲對象,而另一些機器則按照從最高有效位元組到最低有效位元組的順序存儲。前 一種規則— 最低有效位元組在最前面的方式,稱為小端法(little endian)。大多數 Intel 相容機都 采用這種規則。後一種規則— 最高有效位元組在最前面的方式,稱為大端法(big endian)。大多 數 IBM 和 Sun Microsystems 的機器都采用這種規則。 

網絡應用程式 的代碼編寫必須遵守已建立的關于位元組順序的規則,以確定發送方機器将它的内部表示轉換成網絡 标準,而接收方機器則将網絡标準轉換為它的内部表示。 

反彙編器是一種确定可執行程式檔案所表示的指 令序列的工具。 

當閱讀此類小端法機器生成的機器級程式表示時,經 常會将位元組按照相反的順序顯示。書寫位元組序列的自然方式是最低位位元組在左邊,而最高位位元組 在右邊,這正好和通常書寫數字時最高有效位在左邊,最低有效位在右邊的方式相反。

位元組順序變得可見的第三種情況是當編寫規避正常的類型系統的程式時。在 C 語言中,可 以使用強制類型轉換(cast)來允許以一種資料類型引用一個對象,而這種資料類型與建立這個 對象時定義的資料類型不同。 

Linux 32、Windows 和 Linux 64 上這說明它們是小端法機器 ;而Sun 是大端法機器。 

多位元組對象都被存儲為連續的位元組序列,對 象的位址為所使用位元組中最小的位址。 

Linux 32、Windows 和 Sun 的機器使用 4 位元組位址,而 Linux 64 使用 8 位元組位址。 

十進制數字 x 的 ASCII 碼正好是 0x3x,而終止位元組的十六進制表示為 0x00。在使用 ASCII 碼作為字元碼的 任何系統上都将得到相同的結果,與位元組順序和字大小規則無關。因而,文本資料比二進制資料 具有更強的平台獨立性。 

Java 程式設計語言使用 Unicode 來表示字元串。對于 C 語言也有支援 Unicode 的程式庫。 

7、布爾代數

二進制值是計算機編碼、存儲和操作資訊的核心 。

最簡單的布爾代數是在二進制集合 {0,1} 基礎上的定義。 

創立資訊理論領域的 Claude Shannon(1916 — 2001)首先建立了布爾代數和數字邏輯之間的聯系。

布爾運算擴充到位向量的運算,位向量就是有固定長度為 w、由 0 和 1組成的串。位向量的運算可以定義成參數的每個對應元素之間的運算。 

位向量一個很有用的應用就是表示有限集合。

 布爾運算 | 和 & 分别對應于集合的并和交,而 ~ 對應于于集合的補。 

這個掩碼表示的就是設定為有效信号的集合。 

8、C語言中的位級運算

确定一個位級表達式的結果最好的方法,就是将十六進制的參數擴充成二進制表示并執行二進制運算,然後再轉換回十六進制。

位級運算的一個常見用法就是實作掩碼計算，這裡掩碼是一個位模式，表示從一個字中選出的位的集合。

掩碼 0xFF(最低的 8 位為 1)表示一個字的低位位元組 。

9、C語言中的邏輯運算

10、C語言中的移位運算

機器支援兩種形式的右 移 :邏輯右移和算術右移。邏輯右移在左端補 k 個 0, 算術右移是在左端補 k 個最高有效位的值 

C 語言标準并沒有明确定義應該使用哪種類型的右移。對于無符号資料(也就是以限定詞 unsigned 聲明的整型對象),右移必須是邏輯的。而對于有符号資料(預設的聲明的整型對 象),算術的或者邏輯的右移都可以。 

幾乎所有的編譯器 / 機器組合都對有符号資料使 用算術右移,且許多程式員也都假設機器會使用這種右移。

另一方面,Java 對于如何進行右移有明确的定義。表達式 x>>k 會将 x 算術右移 k 個位置, 而 x>>>k 會對 x 做邏輯右移。 

三、整數表示

1、整型資料類型

C語言支援多種整形資料類型——表示有限範圍的整數。

要用C99中的“long long”類型，編譯是要用 gcc -std=c99

2、無符号數的編碼  p39-44

假設一個整數資料類型有w位。我們可以将位向量寫成x→，表示整個向量，或者寫成[xw-1 ，xw-2，…，x0]，表示向量中的每一位。把x→看做一個二進制表示的數，就獲得了x→的無符号表示。

無符号二進制有一個很重要的屬性，就是每個介于0~2^w-1之間的整數都有唯一一個w為的值編碼，函數為一個雙射。

3、有符号數和無符号數的轉換  p44-47

C語言允許在各種不同的數字資料類型之間做強制類型轉換。将負數轉換成無符号數可能會得到0。如果轉換的無符号數太大以至于超出了補碼能夠表示的範圍，可能會得到TMax。

C語言允許有符号數與無符号數之間的轉換，轉換的原則是底層的位表示保持不變

4、C語言中的有符号數和無符号數  p47-49

5、擴充一個數字的位表示

将一個無符号數轉換為一個更大的資料類型，隻需在表示的開頭添加0，即0擴充；将一個補碼數字轉換為一個更大的資料類型可以執行符号擴充，規則是表示中添加最高有效位的值的副本。

6、截斷數字  p51

将一個w位的數假設我們不用額外的位來擴充一個數值，而是減少表示一個數字的位數。x=[xw-1 ，xw-2，…，x0]截斷為一個k位的數字時，會丢棄高w-k位，得到一個位向量[xk-1 ，xk-2，…，x0]，截斷一個數字可能會改變他的值——溢出的一種形式。

注意：有符号數到無符号數的隐式強制類型轉換導緻了某些非直覺的行為。而這些非直覺的特性經常導緻程式錯誤，并且這種包含隐式強制類型轉換細微差别的錯誤很難被發現。因為這種強制類型轉換是在代碼中沒有明确訓示的情況下發生的，程式員經常忽視了它的影響。

7、補碼編碼

最常見的有符号數的計算機表示方式就是補碼形式。在這個定義中，将字的最高有效位解釋為負權。

所能表示的數值範圍[-2^(w-1)~2^(w-1)-1]，在可表示的範圍内每個數字 都有一個唯一的w位的補碼編碼，函數為一個雙射。

注意：

• 補碼的利用寄存器的長度是固定的特性簡化數學運算。想想鐘表，12-1 等價于 12 + 11，利用補碼可以把數學運算統一成加法，隻要一個加法器就可以實作所有的數學運算。
• 補碼的範圍是不對稱的：|TMin| = |TMax| + 1，也就是說，TMin沒有與之對應的正數。這導緻補碼運算的某些特殊的屬性，并且容易造成程式中細微的錯誤。之是以會有這樣的不對稱性，是因為一半的位模式（符号位設定為1的數）表示負數，而一半的數（符号位設定為0的數）表示非負數。因為0是非負數，也就意味着能表示的正數比負數少一個。
• 最大的無符号數值剛好比補碼的最大值的兩倍大一點：UMaxw = 2 TMaxw + 1。補碼表示中所有表示負數的位模式在無符号表示中都變成了正數。
• • 反碼：除了最高有效位的權是-(2w-1-1)而不是-2w-1，它和補碼是一樣的

  

  • 原碼：最高有效位是符号位用來确定剩下的位應該取負權還是正權。

  

8、符号數的其他表示方法

四、整數運算

1、無符号加法

考慮兩個非負整數x和y，滿足0≤x， y≤2w-1。每個數都能表示為w位無符号數字。然而，如果計算它們的和，我們就有一個可能的範圍0≤x + y≤2w+1-2。表示這個和可能需要w + 1位。這種持續的“字長膨脹”意味着，要想完整地表示算術運算的結果，要對字長做限制。

無符号運算可以被視為一種模運算形式。無符号加法等價于計算和模上2w。可以通過簡單的丢棄x + y的w + 1位表示的最高位，來計算這個數值。

溢出：一個算術運算溢出，是指完整的整數結果不能放到資料類型的總長限制中去。

2、補碼加法

3、補碼的非

範圍在-2w-1≤x < 2w-1中的每個數字x都有+wt下的加法逆元。定義對于範圍-2w-1 ≤ x < 2w-1内的x，補碼的非運算-wt如下：

4、無符号乘法

範圍在0≤x, y≤ 2w-1内的整數x和y可以表示為w位的無符号數，但是它們的乘積x · y的取值範圍為0到(2w-1)2 = 22w-2w+1+1之間。這可能需要2w位來表示。不過，C語言中的無符号乘法被定義為産生w位的值，就是2w位的整數乘積的低w位表示的值。可以看作等價于計算乘積模2w。

是以，w位無符号乘法運算* wu的結果為：

5、補碼乘法

C語言中的有符号乘法是通過将2w位的乘積截斷為w位的方式實作的。

6、乘以常數

編譯器使用了一項重要的優化，試着用移位和加法運算的組合來代替乘以常數因子的乘法。将整數拆成2的幂相加，再利用移位進行計算(左移)，最後将結果相加。 同理，對于非負數來說，算術右移k位與除以2^k是一樣的。

我們可以在移位之前“偏置”（biasing）這個值，通過這種方法修正這種不合适的舍入。這種技術利用的屬性是：對于整數x和任意y > 0的y，有 「x/y例如，當x = -30且y = 4，我們有x + y - 1 = -27，而 「-30/4我們有x + y - 1 = -29，而 「-32/4這裡0 ≤ r < y，得到(x + y - 1)/y = k + ( r + y - 1) / y，是以時，後面一項等于0，而當r > 0時，等于1。也就是說，通過給x增加一個偏量y - 1，然後再将除法向下舍入，當y整除x時，我們得到k，否則，就得到k + 1。是以，對于x < 0，如果在右移之前，先将x加上2k-1，那麼我們就會得到正确舍入的結果了。

四、浮點數

浮點表示對形如V = x×2y的有理數進行編碼。它對執行涉及非常大的數字（|V |>

0）、非常接近于0（|V |<<1）的數字，以及更普遍地作為實數運算的近似值的計算，是很有用的。

1、二進制小數

2、IEEE浮點表示

IEEE浮點标準用V = (-1)^s × M × 2^E的形式來表示一個數：

• 符号：s決定這個數是負數（s=1）還是正數（s=0），而對于數值0的符号位解釋作為特殊情況處理。

• 尾數：M是一個二進制小數，它的範圍是1～2-ε，或者是0～1-ε。

• 階碼：E的作用是對浮點數權重，這個權重是2的E次幂（可能是負數）。

将浮點數的位表示劃分為三個字段，分别對這些值進行編碼：

• 一個單獨的符号位s直接編碼符号s。

• k位的階碼字段exp = ek-1…e1e0編碼階碼E。

• n位小數字段frac = fn-1…f1 f0編碼尾數M，但是編碼出來的值也依賴于階碼字段的值是否等于0。

給定了位表示，根據exp的值，被編碼的值可以分為以下三種情況：

• 情況1：規格化的值

當exp的位模式既不全為0（數值0），也不全為1（單精度數值為255，雙精度數值為2047）時，都屬于這類情況。在這種情況中，階碼字段被解釋為以偏置（biased）形式表示的有符号整數。也就是說，階碼的值是E = e-Bias，其中e是無符号數，其位表示為ek-1…e1e0，而Bias是一個等于2k-1-1（單精度是127，雙精度是1023）的偏置值。由此産生指數的取值範圍，對于單精度是-126～+127，而對于雙精度是-1022～+1023。

• 情況2：非規格化的值

當階碼域為全0時，所表示的數就是非規格化形式。在這種情況下，階碼值是E = 1 - Bias，而尾數的值是M = f，也就是小數字段的值，不包含隐含的開頭的1。非規格化值要這樣設定偏置值的原因是使階碼值為1-Bias而不是簡單的-Bias似乎是違反直覺的。我們将很快看到，這種方式提供了一種從非規格化值平滑轉換到規格化值的方法。

非規格化數有兩個用途：

首先，它們提供了一種表示數值0的方法，因為使用規格化數，我們必須總是使M≥1，是以我們就不能表示0。

另外一個功能是表示那些非常接近于0.0的數。它們提供了一種屬性，稱為逐漸溢出，其中，可能的數值分布均勻地接近于0.0。

• 情況3：特殊值

當指階碼全為1的時候出現的。當小數域全為0時，得到的值表示無窮，當s = 0 時是+∞，或者當 s = 1時是-∞。當我們把兩個非常大的數相乘，或者除以零時，無窮能夠表示溢出的結果。

3、舍入

**舍入：**因為表示方法限制了浮點數的範圍和精度，浮點運算隻能近似地表示實數運算。是以，對于值x，我們一般想用一種系統的方法，能夠找到“最接近的”比對值x'，它可以用期望的浮點形式表示出來。

**在兩個可能值的中間确定舍入方向：**一種可選擇的方法是維持實際數字的下界和上界。例如，我們可以确定可表示的值x-和x+，使得x的值位于它們之間：x- ≤ x≤ x+。

IEEE浮點格式定義了四種不同的舍入方式。

• 預設的方法是找到最接近的比對，而其他三種可用于計算上界和下界。

• 其他三種方式産生實際值的确界。這些方法在一些數字應用中是很有用的。向零舍入方式把正數向下舍入，把負數向上舍入，得到值x^，使得| x ^|≤| x |。向下舍入方式把正數和負數都向下舍入，得到值x-，使得x-≤x。向上舍入方式把正數和負數都向上舍入，得到值x+，滿足x≤x+。

4、浮點運算

IEEE标準指定了一個簡單的規則，用來确定諸如加法和乘法這樣的算術運算的結果。把浮點值x和y看成實數，而某個運算⊙定義在實數上，計算将産生Round (x ⊙ y)，這是對實際運算的精确結果進行舍入後的結果。當參數中有一個是特殊值（如-0、-∞或NaN）時，IEEE标準定義了一些使之更合理的規則。例如，定義1/-0将産生-∞，而定義1/+0會産生+∞。

• 浮點加法不具有結合性，這是缺少的最重要的群屬性。

• 浮點加法滿足了單調性屬性：如果a≥b，那麼對于任何a、b以及x的值，除了NaN，都有x + a ≥ x + b。無符号或補碼加法不具有這個實數（和整數）加法的屬性。

• 對于任何a、b和c，并且a、b和c都不等于NaN，浮點乘法滿足下列單調性：

5、C語言的浮點數

所有的C語言版本提供了兩種不同的浮點資料類型：float和double。在支援IEEE浮點格式的機器上，這些資料類型就對應于單精度和雙精度浮點。

較新版本的C語言，包括ISO C99，包含第三種浮點資料類型long double。對于許多機器和編譯器來說，這種資料類型等價于double資料類型。不過對于Intel相容機來說，GCC用80位“擴充精度”格式來實作這種資料類型，提供了比标準64位格式大得多的取值範圍和精度。

============遇到的問題==================

對于公式的了解還是不太夠，雖然老師說公式可以不看，但是不看公式的話後面會有很大一部分内容無法了解，練習做起來也麻煩。是以我花了很多時間在公式上，但是到頭來收益還不如以前上的彙編、計算機導論對數制的了解簡單。代碼也有很多需要構造的部分。如果沒有答案，我覺得可能就不知道怎麼寫了。