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

[Marc LeBrun]

 >=Antti Karttunen
 > ...  A + B =  (A XOR B) + 2 (A AND B)
 > crystallizes as a recursive relation the standard
 > "Ripple Carry Adder" logic circuit...
 > (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).

Coming full logic circus:

While we were designing HDTV graphics chips in the '80s I wondered, what 
would happen if you changed that "arbitrary constant" 2 to something else?

What if we messed up the mask and misaligned the carries one place more to 
the left, so that that 2 was 4 instead?  What the heck would it be computing?

Generally, if you multiply by M instead of 2 the radix R is got by solving 
the numbral polynomial equation 2[M]R=2 (as written in rebasing notation).

So multiplying by 4 means solving 2[4]R=R^2=2 for R, thus the bad adder 
would be computing in base R=sqrt(2)!

Of course you can substitute other values of 2 besides 4.  For instance 
1/2, 1 and 0 are fun (what "bases" do they implement?).

Multiplying by 3 produces an interesting unary tally arithmetic with holes.

Raising that 4 to 4.5 gives a different unary, but, also, the golden base 
phi (roots :: radixes!)

(One caution regarding exploring this by parameterizing the recursive 
formula: you have to be careful about termination.  Fortunately 
non-uniqueness of expansions often allows making judiciously "canonical" 
choices that ensure convergence.)


PS: Sorry if I missed it, but I'm curious: who or what is "Inquiry 
<inquiry at stderr.org>" that appeared in the CCs?