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)
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.