> Beat me to death, but I can't understand how it works. But it works.<p>I'm pretty certain you could figure it out by substituting the mathematical symbols for their circuit counterparts (remember that all binary mathematical ops are merely a sequence of ANDs, ORs, XORs, etc.) and using boolean algebra to simplify - you would probably end up with X XOR Y after the simplification.<p>E.g. A way to square without a square or multiplication op is to: CUBE(X) / X, which is really X * X * X / X just like the mathematical functions have some underlying binary operations that do involve the XOR that you are not allowed to use.
Both examples seem rather obvious to me. The first one adds the carries onto the bitwise sum, similar to a carry ripple adder. The second subtracts the carries from the result to retrieve the bitwise sum (XOR).