Two’s complement is a unary operator on fixed-width binary numbers. Given that x is a binary number, then the two’s complement of x is C2(x) = bitnot(x) + 1 (here, + means addition in modulo arithmetics).
Modulo-m arithmetics means that all values that have the same remainder after being divided by m are “congruent” (considered the same). If m = 7, for example, then 1 ≡ 8 ≡ 15.
bitnot is essentially the ~ operator in C (bitwise not). What is important about two’s complement is that the result is truncated to the same width as x.
For example, let us consider 8-bit binary numbers.
The converse is as follows:
Let us take a look at a slightly more interesting case. What is the two’s complement of 0?
It would appear that step 9 is wrong. Shouldn’t the result be 1000000002? That’d be true if we were using regular addition. However, the addition that we use is modulo-28, which means 255 + 1 = 0. One can also say that we keep the least significant 8 bits.
An alternative definition is that bitnot(x) = 2n - 1 - x, in which n is the width of binary numbers. This works because the binary representation of 2n - 1 is n 1’s. As such, subtraction will not yield any borrows of 1. Any bit of x that is 0 will turn into 1 because 1 - 0 = 1. However, any bit of x that is 1 will turn into 0 because 1 - 1 = 0.
For example, let us consider a four-bit number.
This also works in theory. Consider the definition of C2(x) using this method of bit negation:
This is a result of modulo-2n arithmetics. 2n - x can have the same remainder as -x when divided by 2n.
