顯示具有 Hackers Delight 標籤的文章。 顯示所有文章
顯示具有 Hackers Delight 標籤的文章。 顯示所有文章

2007年2月11日 星期日

Hackers Delight 2-2

2-2 只用到加(減)法與基本邏輯運算的式子

本節選錄一系列只用到加(減)法與基本邏輯運算的式子.

a.
(譯註: by definition of 2's complement)
b.
(譯註: -x = -(NOT(NOT(x-1))+1) = -(-NOT(x-1)) = NOT(x-1) )

c.

(譯註: by a.)

d.

(譯註: by a.)

e.

(譯註: by c.)

f.

(譯註: x+y = x-(-y) = x-(NOT(y)+1) = x-NOT(y)-1)

g.

(譯註: (x XOR y) = x+y with carry bits ignored,

2(x AND y) = carry bits )

h.

(譯註: (x OR y) = x+y - (x AND y) )

i.

(譯註: by g. and h.)

j.

(譯註: by a.)

k.

(譯註: (x XOR y) = x-y with borrow bits ignored,

2(NOT(x) AND y) = borrow bits)

l.

(譯註: first calculate 1-0 parts, then minus the 0-1 parts)

m.

(譯註: by k. and l.)

n.

(譯註: by definition of XOR)

o.

(譯註: (x AND NOT(y)) = the mask where x(i)=1 AND y(i)=0)

p.

q.

(譯註: NOT(x-y) = -(x-y)-1 = y-x-1)

r.

(譯註: by q. - NOT(x) = -x-1)

s.

(譯註: NOT(x XOR y)

= NOT((x OR y) - (x AND y))

= (x AND y) - (x OR y) -1)

t.

(譯註: by s.)

u.

(譯註: by o.)

v.

(譯註: by p. (x AND y)

= (x - (x AND NOT(y)))

= x + (NOT(x AND NOT(y)) + 1)

= x + (NOT(x) OR y) + 1

= (NOT(x) OR y) + NOT(NOT(x)) + 1

= (NOT(x) OR y) - NOT(x) )


(d) 式可以循換地套用, 例如 -NOT(-NOT(x)) = x + 2, 依此類推. 同樣地, (e) 式也一樣: -NOT(-NOT(-x)) = x - 2. 我們可以利用這兩招對 x 任意增減任意常數.

(f) 式是 (j) 式的共軛式, (j) 式是使用加法來計算減法的常見技巧.

(g) 式跟 (h) 式出自 HAKMEN. (g) 式首先忽略進位地計算 x+y, 再補上忽略掉的進位.

對於兩個各位元獨立, 且為0與為1機率同高的亂數, 計算其加法的時候, 已被證明任一位元上發生進位的機率為 0.5. 當使用 (g) 式來計算兩數和的話, 任一位元上發生進位的機率小於 0.5.

(譯註: 原文此處估計為機率大於 0.25 且小於 0.5, 但證明不嚴謹故此處僅保留部份結論)

(k), (l) 式與 (g), (h) 式是共軛式. (k) 式首先忽略借位地計算 x-y (該借位的位元憑空加1, 不實際借位), 再扣回忽略掉的借位.

(n) 式只使用三種運算(AND, OR 跟減) 來實作 XOR 運算, 花費三個指令. 若只用 AND, OR 跟 NOT 的話, 須花費四個指令: (x XOR y) = (x OR y) AND NOT(x AND y).

與此相似, (u), (v) 兩式分別使用三種運算來實作 OR 跟 AND 運算, 花費三個指令.

2007年2月7日 星期三

Hackers Delight 2-1 (5/5)

總和以上流程, 可以得到以下式子:




(譯註: 原文附上了C語言的實作原始碼, 我想這裡就免了吧)

如果你的處理器算除法很慢, 但是可以很快地計算尾端0-位元序列長度函數 ntz(x), 前端0-位元序列長度函數 nlz(x), 或1-位元個數函數 pop(x). 則上述式組中的最後一式, 可以代換為下列任一式:

2007年2月6日 星期二

Hackers Delight 2-1 (4/5)

根據此定理, 我們可以推得 - 想要透過基本運算序列來關閉最左的1-位元是不可能的, 因為某個1-位元是否應該被關閉, 取決於它的左側是否還有其他的1-位元. 觀察其左側位元的需求是絕對無法迴避的, 也因此不可能透過右至左計算法達成.

同理, 想要透過基本運算序列來對一個 word 右移, 旋轉, 左移不定位元, 或計算當中的尾端0-位元序列長度, 都是不可能的. (計算尾端0-位元序列長度時, 輸出的最右位元取決於序列長度的奇偶性, 該性質是不可能只看輸入的最右位元就能決定的)

(譯註: 左移不定位元之所以無法達成, 可透過以下觀察得証: 令輸入當中的最右1-位元為第 x 號位元, 則輸出的第 x 號位元究竟是1還是0, 取決於左移量是否為0, 而想判斷左移量是否為0, 只看左移量的第 x 號位元或其右的位元是絕對不足以判定的)

對於上述的位元運算技巧, 有一個特別的應用: 輸入一個數字, 輸出下一個比它大, 而且含有等量 1-位元的數字. 這技巧可以幫助我們在利用數字來表示子集合的情形下, 窮舉所有相同大小的子集合.

(譯註: 原文很囉唆地說明了用數字來表示子集合的方法, 以下簡單帶過)
想要表示一個子集合, 我們可以把元素宇集存入序列當中, 如此一來每個子集合可以透過一個唯一個數字來表示: 數字當中的 i 號位元為1的時候, 代表該子集內包含 i 號元素.

R. W. Gosper 提出了一個演算法達成了上述的功能. 令 x 為輸入的數字, 該演算法的概念是尋找 x 當中最右的連續1-位元以及其右的0-位元序列, 並"增加"其數值直到含有等量的1-位元為止.

例如, 輸入 xxx0 1111 0000 (xxx 表示任意位元), 輸出 xxx1 0000 0111. 該演算法首先透過 s = x AND (-x) 來找出最右的1-位元. 在本例中得到的是 0000 0001 0000.
然後把它加入 x 得到 r (譯註: r 當中少了 n-1 個1-位元, n 代表連續1-位元的長度). 在本例中 r=xxx1 0000 0000.

接著, 我們必須補上少了的 n-1 個1-位元, 首先計算 r XOR x, 將造出一個有著 n+1 個1-位元的數字. 在本例中 r XOR x = 0001 1111 0000. 很明顯這數字又有了太多的1-位元, 我們將它除以 s, 可消去右側的0-位元序列, 最後再右移兩位元使得當中的1-位元個數為 n-1.

把這個拼拼湊湊造出來的, 有著 n-1 個置右1-位元序列的數字, 和 r 做 OR 運算就可以得到最終的輸出.

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 個基本運算序列並平行計算之, 定理一得証.

2007年2月4日 星期日

Hackers Delight 2-1 (2/5)

使用下面式子可指示出數字內最右為1的位元以及其右的連續0-位元, 如果根本沒有為1的位元存在, 本式輸出零 (例如 01011000 => 00001111)



使用下面式子可延伸數字內最右為1的位元, 如果根本沒有為1的位元存在, 本式輸出全1 (例如 01011000 => 01011111)



使用下面式子可關閉最右的連續1-位元序列 (例如: 01011000 => 01000000)


這式子亦可用來判斷一個非負整數是否為 2^j - 2^k, j>=k>=0 型. 將數字帶入本式之後檢查是否為0即可.

以上所有式子都有對應的共軛型. 把每個式子的用途描述裡的1和0交換, 然後把式子裡的x-1用x+1取代, x+1用x-1取代, -x用NOT(x+1)取代, AND用OR取代, OR用AND取代, 但維持x跟NOT(x)不變. 轉換後的式子將達成轉換後的用途. 以本節第一個式子為例

用下面式子可以關閉word裡最右為0的位元, 如果根本沒有該位元, 本式將輸出全1 (例如: 10100111 => 10101111)


譯注: 令 f(x) 為原式, f'(x) 為共軛式, 則 f'(x) = NOT(f(NOT(x)) 據此可推得上述的取代規則

Hackers Delight 2-1 (1/5)

2-1 操縱最右位元

這節提到的式子, 有些看其來沒啥用, 但在後面的章節會陸續找到它們可應用之處

下面式子將把word內 (譯注: 本書所述的word大小為32位元) 最右為1的位元關閉, 當最右為1的位元根本不存在的時候, 本式輸出零 (例如: 01011000 => 01010000)


該式亦可用來偵測一個無號整數是否為power of 2. 把數字帶入該式之後再判斷輸出是否為0即可.
下面這個式子可用來偵測一個無號整數是否為2^n-1型 (包含0跟全1)

下面這個式子可以孤立最右為1的位元, 如果根本沒有為1的位元, 本式輸出零 (例如 01011000 => 00001000)
下面這個式子可以孤立最右為0的位元, 如果根本沒有為0的位元, 本式輸出零. (例如 01011000 => 00001000)
使用下列任一式可產生找出數字最右的連續0-位元串, 如果輸入為零則輸出全1 (例如01011000 => 00000111)
當中第一式可以切割成能同時計算的多個指令 (譯注: 原因詳見本節定理1)