Two's Complement Notation for Binary Addition

Two’s complement is a format for representing negative numbers in binary. A number -X is represented as an N bit value using the binary value of 2^N-X. E.g. -5 in 4-bit integers would be 2^4 - 5 = 11 (or 0b1010). The advantage of using this representation is that it makes addition of negative numbers possible with existing binary adder circuits (or logic gate implementation). The reason this works is that the output we get from an adder circuit is actually the “modulo 2^n” representation.

Example: -2 + -3 using 4-bit integers

-2 in 2’s complement is 2^4 - 2 = 16-2 = 14 or 0b1110 -3 in 2’s complement is 2^4 - 3 = 16-3 = 13 or 0b1101

Performing binary addition of 0b1110 and 0b1101 we get, 0b1011 and a carry bit of 1 which is discarded. 0b1011 is 11 in decimal. This is equal to -5 in 2’s complement representation which is the correct answer.

In order to do subtractions using a digital adder circuit, it becomes necessary to compute “-x” given a value “x”. This is done as follows:

Negative value of X in 2’s complement notation is given by

2^n - x = 1 + 2^n - 1 - x = 1 + (2^n -1 ) - x = 1 + (0b111111… - x) = 1 + ~X where ~ is the bitwise inverse = ~(X + 0b11111…) (from ALU truth table)

Other properties

(x + 1) = ~(~x + 0b1111….) (x - 1) = x + 0b1111…. (x - y) = ~(~x + y) (y - x) = ~(x + y)

References

[1] Nand2Tetris Unit 2.3 [2]: https://en.wikipedia.org/wiki/Two%27s_complement#Addition [[2]] https://en.wikipedia.org/wiki/Two%27s_complement#Addition