# 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.

• If you need to increment, one half adder per bit is enough (you'll have the same result if you simplify the above circuit by considering the constant input). – AProgrammer Dec 22 '15 at 15:58
• Won't the Cout of each stage be generated from an OR gate? Can't help but notice you are using an X-OR gate to generate the Couts'. – Shashata Sawmya Aug 6 '17 at 5:38
• You are very perceptive. The Cout can be generated by either an OR gate or an XOR gate. This is because the two inputs to that gate are never both 1 at the same time. (Create a truth table to convince yourself of this.) But you should post your question as a comment to my answer, and not as a new answer to the question. – sifferman Aug 6 '17 at 11:05