Two's complement Using ONLY Logic Gates

How can a 4-bit two's complement operation be implemented using only boolean logic gates (AND, OR, NOR, NOT, NAND, XOR, and XNOR)?

(This question was redirected to CS from Stack Overflow)

A two's complement operation is simply a one's complement operation followed by the addition of 1 to the result. One's complement is easy: simply invert all of the input bits.

The addition of 1 must be done with a 4-bit adder. A 4-bit adder is constructed using four stages of a 1-bit full adder. The 1-bit full adder accepts two bits, plus a Carry input, and generates the sum of the two bits, plus a Carry output. The following diagram is a 1-bit full adder:

We can cascade four of the 1-bit full adder stages together, feeding the Carry output of each stage to the Carry input of the next stage. The inverted (one's complement) inputs are applied to the B inputs of the four stages. To perform an addition of 1, we apply the 4-bit binary value 0001 to the A inputs. The complete boolean circuit is shown below:

The above circuit can be reduced by noting that each XOR operation on the input of each adder stage can be replaced either with an inverter if the A input is a 0, or a NOP (no operation) if the A input is a 1. On further analysis, further reductions may be made to the circuit, as well.

StackExchange Computer Science Q#51034, answer score: 2