Mathematics

Because examples are worth a million words, let's see some examples of numbers and their two's complements for unsigned 4-bit numbers (the idea extends to any bit width, but we'll limit ourselves to 4 for simplicity). The table below lists numbers in binary and decimal form, and their complements.

Again, note that the complement goes both ways — 1 is 15's two's complement and vice versa. The table above lists all two's complements for \(2^4\) (4 bit-word).

You may be wondering how to compute the complement. The obvious way is to use a word that is 1 extra bit wide (in the example above, 10000 is 5 bits wide), and then subtract the 4-bit number you have. Hence to compute the two's complement of 0111 (7), you can just do 10000 (16) minus 0111 (7), which is 1001 (9).

But hold on — that's too easy right? So let's now consider the following constraint: what if the maximum word size of your CPU architecture is 4 bits? In this scenario you can no longer load a 5-bit word into a single CPU register because each register is only 4 bits wide. Annoying!

Is there a way to only use 4-bits to still compute the two's complement? Indeed there's a neat bitwise trick to do this, involving 2 steps:

1. apply binary NOT to the word, and
2. add 1.

In Python and C, the ~ (tilde) symbol is used to get the binary NOT value of a word. This just means flipping the bits so that they are the opposite of what they are in the original word. So the binary NOT of 0111 (7) is 1000 (8). So if we add 1 to it, we get 8 + 1 = 9, what we got using plain subtraction previously.

You may now be wondering how the above trick even works. It's actually trivial, if we tweak the problem so that we want to get \(2^N - 1\) (one away from our answer) instead of \(2^N\) directly.

For a 4-bit word, 0xf (hex), or 1111 in binary is the value for \(2^4 - 1\). So now if you wanted to arrive at 1111 by adding two binary words together, at least one thing must be true — there must be no carries. That is, wherever there is a 1 bit set in one word, the other word has to have a 0 set in the same bit index, and vice versa. The two words cannot step on each other's toes. This is exactly the property of the binary NOT operation — it gives us 1-bits wherever there are 0-bits. Below is a table of examples.

And now all that remains to get the complement is just adding 1 to NOT X so that the total on the right is 16 instead of 15.

In the discussion above, we only talked about unsigned numbers. That is, the decimal equivalent of the binary number assumes that this binary number is an unsigned (always positive) word.

We can use two's complement to represent negative numbers in a super convenient way: just make the leading high-order bit equal to \(-(2^{N - 1})\). So using the 4-bit words above, the leading bit, if on, represents \(-(2^{4 - 1}) = -2^3 = -8\). Then we treat all other bits as their regular "unsigned" part, and add these two pieces together to arrive at our final number.

Below are all possible values of signed 4-bit words.

This is all well and good, but where/how should we use the two's complement? Technically speaking, we're already using two's complement in the table above, although it's implied. Let's make it explicit in the table below:

If we pretend we are using just unsigned values, the first two columns are the same as in 1. So if we add them together, we always get 16 (third column). The interesting thing to note is that the negative numbers are exactly that — they are literally the two's complement of the original number, but with a negative sign in front. For example, the unsigned value \(4\) (0100) in the middle column above is represented as \(-4\) via its two's complement 1100 in the first column. Another way to say this is that for any number with a leading high-order bit turned on (as in number 1000 to 1111), we will make the computer interpret it as a negative number, where the value of this negative number is its two's complement. So for 1100 (12), we know it's a negative number because of the leading high-order bit, and to find the value we get the two's complement (0011 plus 1) 0100 (4). So the signed representation of 1100 is \(-4\).

This "paper folding" idea presented above is essentially the same idea for figuring out how to add 1 to 100 quickly where you take pairs of number from both ends — e.g. 1 and 100 (sums to 101), 2 and 99 (sums to 101), etc. — and multiply how many pairs you have. This is attributed to the story of Carl Frederich Gauss. The key to Gauss's formula, where you take pairs of numbers that all add up to the same number (101), is strikingly similar to two's complement where all of these complementary pairs add up to the same \(2^N\) number.

You may have noticed that some of the examples above spill over to 5 bits, because of our desire to stay as true to the mathematical notion of complement as possible. For the computer, when we spill over to using 5 bits, the high-order (leftmost) gets discarded. So for example the 2's complement of 0 for a 4-bit word (0000) is 10000 (16), but this just reduced back down to 0000 because the leading bit is necessarily discarded as the word only allows for 4 bits. For this discussion though, it doesn't matter because we only care about taking the two's complement when we want to represent negative numbers, and for 0 there is no need to get the negative of this number.