CS:APP 電腦系統:程式設計師的角度 第二章之一-Information Storage筆記

二進制非常適合機器來儲存以及處理訊息，而且有很多方式可以輕鬆的表達二進制，例如:

• punched card上的洞
• 線上的高低電壓
• 磁場的順時針與逆時針

二進制有以下三種常見的表示數字方式:

• Unsigned
• Two's-complement
• Floating-point

一些特性

• 用32bit的int來計算以下算式會溢出變為負數，
  這和電腦如何表示以及儲存數字有關

$200 * 300 * 400 * 500 = -884,901,888$

• 浮點數運算並沒有associative(結合律)因為有限精度
• 雖然會有期待之外的結果，但這些結果是可預測的，熟知這些電腦數字運算的特性對於寫程式有極大的幫助，可以避免bug以及安全問題產生

---

• 電腦使用blocks來當記憶體的最小單位，通常是8bits，1byte，也就是每個地址是一個區塊
• Machine-level program把記憶體視為一個很大的bytes陣列，稱之為virtual memory
• 記憶體每個byte都有其唯一標示，稱為address(位址)，這些所有的位址稱之為virtual address space
• virtual address space是給machine-level program看的，事實上他是由各種記憶體(DRAM, flash memory, disk, special hardware)實作而成，為了給程式一個單純的byte array使用

16進制

• 二進制冗長，通常使用16進制
• 在C語言中0x或0X開頭的是16進制，後面的字母可以是大寫或小寫或是大小寫混合，例如:
  • 0xFA1D37B
  • 0xfa1d37b
  • 0xFa1D37b都是合法的
• 可以記住A、C、以及F分別代表多少來快速運算16->10進制或其他

0x173A4C轉換為10進制只要把全部拆開換成二進制就可以

反之，二進制四個一組轉換為16進制，如果剛好不是四的倍數，最左邊剩幾個就幾個一組，然後前面補0

資料大小

• 每個電腦都有word size，是pointer的大小
• w-bit word size的電腦，virtual addresses的範圍是$0\text{\textasciitilde}2^w - 1$，給程式最多$2^w$bytes
• 32-bits word size的virtual address space最多只有4GB(4 x 10^9bytes)，而64-bit可以到$1.84 \times 10^{19}$bytes
• 大多64位元機器也能執行給32位元機器執行的程式，但64位元編譯的只能給64位元用，編譯方法不同
• C語言支援不同格式的integer和floating point data

• ISO C99統一資料大小，無論哪個編譯器或是機器設定
• 大多資料型態都是signed，除非聲明unsigned
• char在C標準中沒有明確被定義為應該存有符還是無符的數值。工程師應該聲明為signed char來保證1-byte signed value，雖然很多時候char的有符或無符並不會影響程式
• 以下聲明完全相同
  • unsigned long
  • unsigned long int
  • long unsigned
  • long unsigned int
• 工程師應致力於寫出具可移植性的code，例如避免程式對於資料的最大值敏感；以前32位程式時常用int儲存指針，但是這個方法在64位會導致問題。至於確切的前因後果書上並未收錄，至少在這邊的原文沒寫

Addressing and Byte Ordering

• 有些機器會把物件在記憶體裡從LSB(Least significant bit)排到MSB，這樣的方式稱為little endian，反過來就是big endian

例如在位址0x100有數值0x01234567，可以排成以下兩種

• Intel-compatible machines通常採用little endian，而IBM和Oracle則是大多採用big endian，現在的微處理器很多採用bi-endian，可以使用任意一種模式
• ARM微處理器可以用little或是big，而Android(Google)和IOS則是只用little-endian
• 兩種模式沒有正確與否，只是一種選擇

那，知道這個有什麼用?

的確，對於現在的程式設計師，幾乎無所謂，但有時候還是會造成問題

1. 兩個不同模式的機器透過網路傳遞資料，就會造成字節順序錯亂 - 章節11會舉例說明
2. 以字節來看資料，例如以下

• 4004d3: 01 05 43 0b 20 00
• add %eax,0x200b43(%rip)

byte反過來了

3. 第三種情況比較特殊，當程式想要跳出平常的資料型態，在C中可以用cast或是union to allow an object to be referenced according to
   a different data type from which it was created(這段有看沒有懂)，但這個小技巧在開發應用程式大多數時候是強烈建議不要使用，但有時候在系統層的程式編寫會很好用

以下程式可以用來顯示bytes

// Code to print the byte representation of program objects
#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len) {
  int 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 *));
}

在以下機器執行:

• Linux 32: Intel IA32 processor running Linux.
• Windows: Intel IA32 processor running Windows.
• Sun: Sun Microsystems SPARC processor running Solaris. (These machines
  are now produced by Oracle.)
• Linux 64: Intel x86-64 processor running Linux

void test_show_bytes(int val) {
  int ival = val;
  float fval = (float) ival;
  int *pval = &ival;
  show_int(ival);
  show_float(fval);
  show_pointer(pval);
}

可以看到int和float在不同的系統與處理器中有字節序的不同，linux32、windows以及linux64都是使用little-endian，也就是LSB放在最前面；Sun則是相反

最後的位址，Linux64和大家都不同，因為他使用的是8 byte位址

把12345的int與float轉為二進制發現有一段是一樣的，這不是巧合，詳細會在浮點數格式章節說明

C的String則是an array of characters終止於null

冷知識: Unicode標準收錄了超過十萬個字，支援古埃及與巴比倫文字，但Universal Technical Committee拒絕了把克林貢語(星際大戰中的虛構語言)加入的提案

Boolean Algebra

• 是電腦邏輯的基礎，使得我們可以精確的描述與分析電腦系統的行為
• 還能作為遮罩使用，過濾掉各種signals，詳細在第八章會講解

Bit-level Operations in C

• C語言支援位元運算

以下是不用第三個變數就可以直接交換兩個數字的炫技方式，這樣做不會有任何效能上的提升，單純好玩

void inplace_swap(int *x, int *y) {
  *y = *x ^ *y; /* Step 1 */
  *x = *x ^ *y; /* Step 2 */
  *y = *x ^ *y; /* Step 3 */
}

Logical Operations in C

• ||
• &&
• !
• ||以及&&如果在第一個argument就可以確定，就不會看第二個argument了，例如:
  • a && 5/a
  • p && *p++

Shift Operations in C

• x << k，出界的捨棄，後面的空位補零
• x >> k，通常支援以下兩種右移
  • Logical: 右移後左邊空位補零
  • Arithmetic: 右移後左邊補上原本的MSB(對signed integer很有用)
• C並沒有規定右移signed numbers時應該使用哪種右移(當遇到有符數字時，幾乎所有編譯器/機器都使用arithmetic右移，而無符就用logical)
• Java對於右移有明確規定
  • x >> k shifts x arithmetically by k positions
  • x >>> k shifts logically
• C沒有明確規定當移動超過word size的時候該怎麼辦，通常都是取k mod w，但還是不建議C的工程師移動超過word size；相反的，Java有定義一定要取mod，所以可以放心移動超過word size

小知識: 1<<2 + 3<<4在C中會變成(1 << (2+3)) << 4，而不是(1<<2) + (3<<4)。在C中弄清楚優先順序很重要，如果不確定就加括號就對了!