x|y = ~(x.y)               (1)

So Suppose C_i indicates the carry number on ith position, . indicates 'AND', || indicates 'OR', ~ indicates ‘Not'

Then

C_{i+1} = (A_i . B_i) || ((A_i || B_i) . C_i)

= ~(~(A_i . B_i) . ~((A_i || B_i) . C_i))

Based on (1)

We have

C_{i+1} = (A_i | B_i) | (C_i | (A_i || B_i))  (2)

Notice that 

A_i || B_i = ~(~A_i . ~B_i)

= ~A_i | ~B_i                  (3)

Since

A_i = A_i . A_i

Based on (1), (3) can transform to 

(A_i | A_i) | (B_i | B_i)      (4)

Take (4) to (3) and (3) to (2),

We have

C_{i+1} = (A_i | B_i) | (C_i | (A_i | A_i) | (B_i | B_i)))

不过很好奇为啥不给SPJ

• Re:还是可以简单推倒那个公式的 (22) 11119999 2013-09-17 15:51:30