(A XOR B) + 2 (A AND B) and Ripple Carry Adders.

[Antti Karttunen]

Jon Awbrey wrote:

>o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
>JA: back when we used to call these "mask operations", it was
>    said that ADD was a combination of XOR plus a shifted AND,
>    and of course the process would have to be iterated until
>    it terminated.
>
>AK: This is the item #23 (by Richard Schroeppel) in HAKMEM:
>    (A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B).
>
>AK: Follow the link in:
>
>    http://www.research.att.com/projects/OEIS?Anum=A050600
>
>JA: Thanks for the link, though I'm sure it is much older than that.
>  
>

Just realized this (consciously!): Certainly the latter formula  A + B 
=  (A XOR B) + 2 (A AND B)
must have been known already by the pioneers (Wiener, von Neumann?)
as it actually crystallizes as a recursive relation the standard
"Ripple Carry Adder" logic circuit, used to add two binary numbers
in computer ALU's, before the advent of "Carry LookAhead" techniques.

(We can think the operation + 2 (A AND B) as the feeding of carry bits
back to the (full) adders, shifted one bit to the msb-direction).

See for example:
http://www.seas.upenn.edu/~ee201/lab/CarryLookAhead/CarryLookAheadF01.html

http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Comb/adder.html


(Hmm. How to generate automatically HDL-code from that kind of recursive
definitions?)


BTW, People here might find many papers of Jerzy Karczmarczuk
( at: http://users.info.unicaen.fr/~karczma/arpap/ ) amusing/inspiring.
See for example the first one there, titled:
"The Most Unreliable Technique in the World to Compute PI".
illustrating "Infinite precision real fractions, and lazy carry 
propagation".
which might be even related to this discussion.

(For more about Haskell-language, see http://www.haskell.org/ )
/

/Yours,

Antti