好啦，昨天好像有點講太長了。今天開始文章會很短。今天來介紹隨機存取模型～

為什麼會有隨機存取模型呢？我們知道現在的電腦有「記憶體位址」這樣的東西。為了讓中央處理器(CPU)能夠迅速知道要存取的資料在哪裡，每一次能夠計算的位元數便被設計成記憶體位址能夠支援的範圍，也就是說，如果我們要表示 0x00000000~0xFFFFFFFF 的記憶體位址，那我們要表示一個位址就需要 個位元。而這個位元數則被我們定義為一個字組 (Word) 的大小 。現在大多數我們稱乎「32位元電腦」、「64位元電腦」其實就對應著 或 。

有了這樣的模型以後，我們自然可以假設存取任何一個記憶體位址所對應的位元組都只需要 1 單位的時間（常數時間，通常寫作 ）。而且我們還可以假設對任何兩個 位元的整數進行加法、減法、位移(shift)、以及各種逐位元運算子（AND, OR, XOR, NOT 等）都只要花 1 單位的時間。

Note 1: 乘法、除法和取餘數的計算，被我們排除在這個模型之外。在一般電腦中由於 不大，乘法除法只要晶片設計得宜通常可以在數個 CPU 循環(cycle) 內計算出答案。但在 變成一個模型中被定義的參數以後，我們會發現計算乘除法所需要的時間必須與 的值有關（無法作到常數時間），無法忽略。

這個模型有什麼好處呢？一個常見的加速小手段，就是可以偷偷用位元運算技巧幫我們節省一些時間。我們來看看一些例子：

Parity Bit 較驗位元問題

在資料傳輸的過程中（非常非常非常底層），有時候我們會想要確認傳過來的位元們是否有出現錯誤。一個很簡單的想法就是檢查傳過來的 1-位元 總數的奇偶性。如果今天我們想在應用程式層，實作類似的檢查，怎麼辦？

我們可以寫出以下的程式碼，逐一檢視所有 bit。對於第 i 個 bit，我們只要把 跟 取 AND 運算，就可以知道該 bit 是否為 0，最後把所有位元全部 XOR 起來放到 result 就可以了！

for (unsigned int i = 0; i < w; i++) {
    result ^= ((N & (1<<i)) != 0);
}

但這個方法需要 的時間，因為對於每一個位元都必須要逐一檢查。而事實上，由於迴圈中的每一步我們只用到了其中一個 bit，浪費的其他位置的運算資源。經過了一些觀察，我們可以發現，要 XOR 所有 的位元 ，等價於把 拆成長度相等的兩半 ，然後計算 。但事實上，！

我們可以利用 CPU 能在一單位時間內同時計算 個 bit 的 XOR 值，而在一單位時間內直接算出 的值。原本要關心的整數有 個 bit，經過一次分拆以後變成了長度為 個 bit 的整數。我們可以依樣畫葫蘆：日取其半（但是不會擔心萬世不竭，因為是整數不是實數）然後得到以下的遞迴方法：

int Parity(int N, int w) {
    if (w == 1) return N;
    int upper_bits = (N >> (w/2));
    int lower_bits = (N & ((1<<((w+1)/2))-1));
    return Parity(upper_bits ^ lower_bits, (w+1)/2);
}

由於每一次呼叫 都會減半，所以時間複雜度變成了 。

想像一下， 的話，原本需要 32 單位時間才能算出來的東西，現在只花了 5 單位時間就可以算出來了，是不是很快呢～明天我們將看到更多類似例子！

Note 2
在 GNU 提供的 C++ 函式庫中，有一個方便的內建函式叫做 __builtin_popcount(); 它可以幫你計算一個整數裡面有多少個 1 bit。

Note 3
如果我們被允許預處理，我們可以先開一段記憶體把 1~ 的奇偶性都算出來，實際計算時只需要兩次查表就好。

Note 4
如果我們被允許使用乘除法，那麼有一些黑魔法可以幫我們更快速地算出 Parity 或 Population Count，有興趣的朋友們可以參考 http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 。

Note 7
可能會爆炸。