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 運算, 花費三個指令.