• 信息存儲
  • 十六進制
    • 十六進制的表示
    • 十六進制與二進制酣倾、十進制的轉化
  • 字數(shù)據(jù)大小
  • 尋址和字節(jié)順序
  • 表示字符串
  • 表示代碼
  • 布爾代數(shù)
  • C語言中相關運算
    • 位級運算：&汪厨，|，~
    • 邏輯運算：&&断医，||，蔬捷！
    • 移位運算：<<蓄坏，>>
• 整數(shù)表示
  • 整形數(shù)據(jù)表示
  • 編碼
    • 無符號數(shù)(Unsigned)
    • 補碼(Two's-Complement)
    • 無符號數(shù)和有符號數(shù)之間的轉換
    • C語言中無符號數(shù)與有符號數(shù)的轉換
  • 擴展位表示
  • 截斷數(shù)字
• 整數(shù)運算
  • 加法
    • 無符號加法
    • 補碼加法
  • 取非
    • 無符號數(shù)
    • 補碼
  • 乘法
    • 無符號數(shù)
    • 補碼
  • 乘以常數(shù)
    • 與2的冪相乘
    • 與任意常數(shù)相乘
  • 除以2的冪
    • 無符號數(shù)
    • 補碼
• 浮點數(shù)
  • 二進制小數(shù)
  • IEEE浮點表示
    • 規(guī)格化
    • 非規(guī)格化
    • 特殊值
      • 無窮大
      • NaN(Not-a-Number)
  • 舍入規(guī)則
  • 浮點運算
    • 加法
    • 乘法
  • 類型轉換

信息存儲

• 大多數(shù)計算機以字節(jié)（1 byte = 8 bits）作為最小可尋址的內存單位。

• 虛擬內存：機器級程序將內存視為字節(jié)數(shù)組枫慷。

• 地址：標識每個字節(jié)的唯一數(shù)字让蕾。

• 虛擬地址空間^[1]：所有可能的地址集合浪规。

十六進制

十六進制的表示

• 前綴0x/0X，字母可用大寫A - F或小寫a - f

  記住A探孝，C笋婿，F(xiàn)的十進制值

十六進制與二進制、十進制的轉化

• 十六進制&二進制：四位二進制轉化為一位十六進制顿颅，位數(shù)缺少時整數(shù)部分左側補零缸濒，小數(shù)部分右側補零。

• 十六進制&十進制：乘除法

  2的非負整數(shù)n次冪轉化為十六進制：n = i + 4 * j （i = 1, 2, 3）時粱腻，十六進制表示為2的 i 次方后有 j 個0

字數(shù)據(jù)大小

• 字長決定了虛擬地址空間的最大大斜优洹：字長w位，虛擬地址范圍為0 ~ 2^w - 1栖疑，即可以訪問2^w個字節(jié)讨永。

• 程序時32位還是64位取決于它是如何編譯的。

2-1.png

尋址和字節(jié)順序

• 多字節(jié)對象被存儲為連續(xù)的字節(jié)序列遇革。

• 字節(jié)存儲順序：一個數(shù)據(jù)類型內部字節(jié)的存儲順序

  • 大端法：高位字節(jié)優(yōu)先存儲

  • 小端法：低位字節(jié)優(yōu)先存儲

    大端法（big endian）和小端法（little endian）取自《格列佛游記》中打破雞蛋的方式卿闹。原文暗諷英法兩國持續(xù)的戰(zhàn)爭，而這里則暗示選擇兩種存儲順序沒有技術上的理由萝快，無謂好壞锻霎。

• 需要注意字節(jié)存儲順序的三種情況

  • 不同機器通過網(wǎng)絡傳送二進制數(shù)時，由小端法機器傳送給大端法機器的字節(jié)順序會被認為是反序揪漩，反之亦然旋恼。此時應統(tǒng)一編寫網(wǎng)絡應用程序的字節(jié)順序規(guī)則，由發(fā)送方機器將其內部表示先轉化為網(wǎng)絡標準奄容，再由接收方機器將收到的網(wǎng)絡標準轉化為其內部表示冰更。

  • 閱讀小端法機器的程序表示時。

  • 規(guī)避正常類型系統(tǒng)時昂勒，即運用了強制類型轉換或聯(lián)合蜀细。例如：運用強制類型轉換生成對象的字節(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ù)結構大小的首選數(shù)據(jù)類型(這里為sizeof的結果)
        for(i = 0; i < len; i++) printf("%.2x", start[i]); //%.2x表示兩位16進制數(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 *));
    }
    //這里的強制類型轉換并未改變指針, 只是告訴編譯器以新的數(shù)據(jù)類型看待被指向的數(shù)據(jù)
    //例如, show_int中將&x看作int指針時, 進入"下一個"地址會跨越四個字節(jié); 看作char指針時, 進入"下一個"地址只會跨越1個字節(jié)
    

表示字符串

• 字符串編碼以null(0x00)結尾戈盈。
• 最常見的字符編碼是ASCII碼奠衔。字符串的字節(jié)序列在使用ASCII編碼的任何系統(tǒng)上都有相同結果，與字節(jié)順序規(guī)則和字長大小無關塘娶。

表示代碼

• 從機器的角度看归斤，程序代碼只是字節(jié)序列。
• 不同機器對于相同程序的二進制編碼不同且不兼容刁岸。

布爾代數(shù)

• 位向量可用于表示有限集合的子集脏里，位向量的與或非等價于集合的交并補。
• 布爾代數(shù)與整數(shù)算術有相似之處：交換律虹曙，結合律迫横，分配律（布爾代數(shù)的分配律可以理解為對整數(shù)算術分配律的推廣鸦难。因為布爾代數(shù)中，不僅&對|有分配律员淫，|對&也有分配律）

C語言中相關運算

位級運算：&合蔽，|，~

• 掩碼運算介返。掩碼表示從一個字中選出的位的集合拴事，如0xFF表示一個字低位字節(jié)都是1。x&0xFF表示x的最低字節(jié)不變圣蝎，其他字節(jié)都被置為0刃宵。

  習題2.10&2.11

  注意：指向相同地址的兩個指針，改變其中一個徘公，則另一個也會變

  #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]);
      //最終結果為{5牲证，4，0关面，2坦袍，1}, first = last時, *x = *y, *y = *x ^ *y = 0時, *x也被置為0
      return 0;
  }
  

邏輯運算：&&，||等太，捂齐！

• 邏輯運算中，只有0（FALSE）和1（TRUE）缩抡，所有非零參數(shù)均表示1（TRUE）
• 邏輯運算具有提前終止的特點奠宜。當?shù)谝粋€參數(shù)就能確定表達式的值時，就不會計算第二個參數(shù)瞻想。

移位運算：<<压真，>>

• 左移即在低位補0。右移分為邏輯右移和算術右移蘑险。邏輯右移在高位補0滴肿，算術右移在高位補符號位。
• 由w位組成的數(shù)據(jù)漠其，移動k位嘴高。若k>w竿音，則只視為移動k mod w位和屎。移位指令只考慮移位量k的低logw位。
• 移位運算符合左結合律：x<<j<<k = (x<<j)<<k
• 移位運算優(yōu)先級低于加減法：x<<a+b<<k = (x<<(a+b))<<k

整數(shù)表示

整形數(shù)據(jù)表示

• unsigned / (signed) + char, short, int, long
• 數(shù)據(jù)類型取圍：32位春瞬、64位柴信、C語言標準均有不同

編碼

無符號數(shù)(Unsigned)

• B2U
• UMax, UMin
• 無符號數(shù)編碼具有唯一性（B2U是雙射）

補碼(Two's-Complement)

• B2T

• TMax, TMin

  -TMax = 0 - TMax = TMax

• 補碼編碼具有唯一性（B2T是雙射）

• |TMin| = TMax + 1

• UMax = 2 * TMax + 1

• -1和UMax有相同的位模式

• 有符號數(shù)的其他表示方法

  • 原碼(Sign-Magnitude)
  • 反碼(Ones'-Complement)：對于無符號數(shù)x，-x的w位表示在反碼中相當于[11…1] - x宽气，在補碼中相當于2^w - x

無符號數(shù)和有符號數(shù)之間的轉換

• 保持位模式不變

• 對于x随常，0≤x≤TMax時T2U(x) = U2T(x)潜沦，否則轉換時需對x加上或減去2^w

2-2.png

C語言中無符號數(shù)與有符號數(shù)的轉換

• 顯示轉換：強制類型轉換
• 隱式轉換
  • 不同類型變量賦值：保持被賦值的變量類型不變
  • 輸出函數(shù)printf中通過"%d"與"%u"進行轉換
  • 運算中，如果有符號數(shù)和無符號數(shù)同時出現(xiàn)绪氛，則視為無符號運算

擴展位表示

• 無符號數(shù)進行零擴展唆鸡，值不變。
• 有符號數(shù)進行符號擴展枣察，值不變争占。
  • 高位全是1和只有最高位為1對數(shù)值大小沒有影響，可用于簡化運算序目。

截斷數(shù)字

• 直接截斷高位臂痕。
• 無符號數(shù)相當于取模（x%2^w = x'）
• 有符號數(shù)相當于轉化為無符號數(shù)取模后，再轉化為有符號數(shù)猿涨。

有符號數(shù)和無符號數(shù)之間的轉換容易引起錯誤握童。詳見習題。

整數(shù)運算

模數(shù)運算形成數(shù)學結構：阿貝爾群

無符號數(shù)運算和補碼運算有完全相同的位級表示叛赚。

加法

無符號加法

正常情況x+y的值保持不變澡绩，溢出情況的結果是x+y-2^w

2-3.png

檢測無符號加法的溢出：對于無符號數(shù)s=x+y，當且僅當s<x（等價地俺附，s<y）時英古，發(fā)生溢出

補碼加法

正常情況x+y的值不變，正溢出情況結果是昙读，負溢出情況結果是召调。

2-4.png

檢測補碼加法的溢出：對于補碼s=x+y，當且僅當x<0蛮浑，y<0唠叛，s≥0時，發(fā)生負溢出沮稚；當且僅當x>0艺沼，y>0，s≤0時蕴掏，發(fā)生正溢出障般。

取非

得到取非結果的位級表示的方法：①按位取反后加一。②設k是最右邊的1的位置盛杰，對k左邊所有位取反即可挽荡。

無符號數(shù)

對于無符號數(shù)-x，x=0時結果是其本身即供，否則結果是2^w-x

補碼

對于補碼-x定拟，x=TMin時結果是其本身，否則結果是-x

乘法

無符號數(shù)

x * y=(x * y) mod 2^w

補碼

將結果位級表示轉化為補碼即可

乘以常數(shù)

與2的冪相乘

與2的k次冪相乘轉化為左移k位實現(xiàn)逗嫡。

與任意常數(shù)相乘

將常數(shù)K表示為0和1交替的二進制序列青自，將乘法運算轉化為移位運算和加減法的組合株依。

設K的二進制表示中所有的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)

不符合條件的情況可通過變換得到延窜。

除以2的冪

無符號數(shù)

除以2的k次冪轉化為右移k位實現(xiàn)恋腕，得到向下取整的結果。

補碼

正數(shù)向下取整：除以2的k次冪轉化為右移k位實現(xiàn)

負數(shù)向上取整：除以2的k次冪轉化為逆瑞，先加偏置量2^k-1=(1<<k)-1吗坚，后右移k位

• 原理：
  

“溢出”是針對碼值轉化為數(shù)值后，不符合直觀運算規(guī)則而言的呆万。但實際上碼值運算規(guī)則無謂“溢出”商源，永遠符合相同規(guī)則。如A+B=C就有C-B=A谋减。

浮點數(shù)

二進制小數(shù)

IEEE浮點表示

• 符號s：0正1負

• 尾數(shù)M：1 ~ 2-ε 或 0 ~ 1-ε

• 階碼E

2-5.png

• 符號位s編碼符號s

• k位階碼字段exp編碼E

• n位小數(shù)字段frac編碼M

2-6.png

• IEEE編碼保證了從非規(guī)格化到規(guī)格化的平滑過渡

規(guī)格化

E=Exp-Bias

• Exp是exp的無符號整數(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ù)值

特殊值

無窮大

exp=11...1牡彻，frac=00...0

NaN(Not-a-Number)

exp=11...1，frac≠00...0

舍入規(guī)則

• 向偶數(shù)舍入：四舍六入五湊偶
• 改變編碼格式時出爹，對于非規(guī)格化表示庄吼，先考慮能否轉化為規(guī)格化保留精確度，否則再舍入
• 其他舍入方式：向0舍入严就，向下舍入总寻，向上舍入

浮點運算

加法

• 滿足交換律，不滿足結合律
• 除了無窮和NaN之外都有逆元
• 符合單調性：若a≥b梢为，則x+a≥x+b（a,b,x為除NaN之外的任意值）渐行。無符號數(shù)和補碼加法不符合單調性。

乘法

• 滿足交換律铸董，不滿足結合律
• 乘法對加法不滿足分配律
• 符合單調性：a≥b祟印，若c≥0，則a * c ≥ b * c粟害；若c≤0蕴忆，則a * c ≤ b * c（a,b,c為除NaN之外的值）無符號數(shù)和補碼乘法不符合單調性。
• a * a ≥ 0（a≠NaN）

類型轉換

• int -> float 不會溢出悲幅，但可能舍入
• int/float -> double 不會溢出套鹅，保留精度
• double -> float 可能溢出或者舍入
• float/double -> int 向0舍入，或在無法確定整數(shù)近似值時（例如溢出）產(chǎn)生TMin

1. 對于程序存儲的管理完全是在虛擬地址空間中進行的汰具。例如卓鹿，指針指向的就是字節(jié)塊的虛擬地址。 ?