Hackers Delight 2-1 (3/5)

定理一 . 一個函數 f: word -> word 可由能同時計算的加, 減, AND, OR, NOT指令序列所實作, 若且為若 其輸出的 word 當中, 每一個位元都只和所有運算元的對應位元, 或其右的位元有關聯.

(譯注: 例如 f1(x,y) = x AND (SHL(y, 1)) 可由基本運算序列達成: x AND (SHL(y, 1)) = x AND (y + y). 而 f2(x,y) = x AND (SHR(y, 1)) 就辦不到)

換句話說, 想像你嘗試計算某函數輸出當中的最右位元, 如果你能夠只看每個運算元的最右位元就能夠計算出來, 而且, 當你嘗試計算右二位元時, 也能只看各運算元的最右及右二位元就能獲得答案, 如此依此類推地嘗試計算.

如果你能夠在上述的限制之下完成計算, 那麼這個函數必定可以可由能同時計算的加, 減, AND, OR, NOT指令序列所實作, 反之則不行.

定理當中, "反之不行"的部分, 証明相當容易.

因為加, 減, AND, OR, NOT指令有個共通的特性, 它們都是即使施以上述限制(以後將以 "右至左計算法" 代稱之), 也能夠進行計算的指令. 所以這些指令的任意組合, 也必定能夠以右至左計算法完成.

而另一個方向的証明, 我們以一個例子來非嚴謹證明之.

假設有一個函數 f 能使用右至左計算法得到輸出, 並假設輸出當中的 2 號 (右 3) 位元定義如下:

我們可以透過下面的方法這樣計算該位元:

首先計算出 SHL(x, 2) (譯註: = (x+x+x+x)), SHL(y, 1) 以及 2 號位元的遮罩

計算 (列 1 OR (列 2 AND 列 3)) AND 列 4 將得到一個輸出, 當中的 2 號位元就是我們想計算的 r_2. 對於其他位元我們可以如法泡製造出它們各自的計算式, 然後和 2 號位元同步地進行運算. 等 32 個輸出被同步地計算完成之後, 再把它們全部 OR 起來即可得到最終輸出.

很容易可以觀察出來, 任何可使用右至左計算法達成的函數, 都能夠以上述的方法造出 32 個基本運算序列並平行計算之, 定理一得証.