Two's Compliment
2024-07-19 18:42:11 UTC
Two's Complement is the most common way computers encode signed integers internally. This is done to solve two main problems: 1) We can avoid duplicate representations of the value 0. 2) It means no additional logic is required to subtract numbers beyond having an addition operator.
The first issue we need to consider with signed integers is how to represent a negative value. All of our data in a computer is just a series of 0s and 1s. If we imagine our computer can operate over 1 byte at a time, then our values would be 8 bits wide which we can represent as bbbbbbbb where b equals either a 0 or a 1. Thus, 00000000 could equal 1 and 11111111 could equal 256. However, we're going to want a representation of 0 so let's instead just start counting at 0 by subtracting 1. Thus, 00000000 = 0 and 11111111 = 255.
0 through 255 certainly doesn't contain any negative values. How shall we denote a number as negative? One way to do this would be to designate one of our bits as a "sign" bit. This is known as a signed magnitude representation. We could say our most significant bit (MSB) denotes sign rather than magnitude. So, 00000000 = 0 but 11111111 no longer equals 255. The MSB is 1, which means the number is negative. However, we've now used up one of our bits in denoting sign. So, we're only left with 7 bits to denote magnitude. 2^7 = 128. Thus, 11111111 = -128. This also means that 01111111 = 128.
If we take a closer look at the values we have with our representation, we'll spot an anomaly. We have 128 values in the positive direction and 128 values in the negative direction. That is a sum of 256 different values which makes sense because we have an 8-bit value. However, let's think about this on a smaller scale and use slightly different wording. How many integer values are represented by the inclusive set of -2 through 2? If we use our math from before, we'd get 2 + 2 = 4. But this isn't true. If we count the integers in our set, we get -2, -1, 0, 1, and 2. That's five different values. So, in our byte representation, we're missing the value 0, just like we were with our range from 1-256. Let's examine the set of 3-bit values with signed magnitude representation:
000 = +1
001 = +2
010 = +3
011 = +4
100 = -1
101 = -2
110 = -3
111 = -4
Sure enough, we're missing 0. Let's fix that the way we did before by starting our count at 0 instead of 1:
000 = +0
001 = +1
010 = +2
011 = +3
100 = -0
101 = -1
110 = -2
111 = -3
This is where we discover our first problem. We have a +0 and a -0. This doesn't make any sense. We need to get rid of one of these zeroes.
Let's table that problem for a minute and talk about our second problem: avoiding additional logic beyond addition. We can leverage equivalence classes. A byte is 8 bits. 2^8 = 256, so we'll use a modulus of 256. Modular arithmetic allows us to move in two different directions when we perform operations. If you imagine a clock, adding 4 hours to 11 o'clock results in it being 3 o'clock. 11 + 4 = 3. However, 11 - 8 = 3 as well. So, we can restate subtraction as an addition operation in the opposite direction. Precisely: y - x = y + (m - x) where m is our modulus, x is the value we wish to subtract, and y is the value we're subtracting from. To put it succinctly, y - x = y + (x with inverted digits). Let's take a look at a small example:
For reference, modulus 5 values starting at 0 and adding one are 0 -> 1 -> 2 -> 3 -> 4 -> 0 -> ...
We want to subtract 431mod5 - 133mod5. We can restate this as addition by inverting the digits of 133mod5. The inverse of a digit is how much further you must travel along the "clock" to get back to zero. So, with a modulus of 5, the inverse of 1 is 4. The inverse of 3 is 2. That means we can rewrite our subtraction as 431mod5 + 422mod5. You should try this exercise on paper by performing both the subtraction and the addition. You will see that you indeed get the same answer for both: 303mod5.
This solves our second problem but we still haven't solved the problem of +0 and -0. That's where our Two's Compliment encoding comes in. As before, our MSB is going to represent a negative sign. Unlike before, this is not going to be arbitrary. Instead, we're going to associate a weight to the MSB and that weight is going to be -2^(x-1) where x is the number of bits in our value. This means that instead of 11111111 being our most negative value, 10000000 is going to be our most negative value. 01111111 will represent our most positive value. But what we're going to do for our positive values is simply subtract 1. That way, we get rid of one of our zeroes. So, 01111111 = 2^(x-1) - 1. You'll see why we took the 0 from the positive side instead of the negative side in a moment.
Now we have a range of -128 through 127, including 0. We've defined 10000000 as our most negative value. So, in our representation, if 10000000 is our most negative value, then 11111111 should be our least negative value, which is -1. If we add 1 to that value, our sum should equal 0.
11111111 + 00000001 = 00000000
Observe that what has happened is that all of the bits have flipped and we've added 1. If we flip the bits of 11111111 we get 00000000. We then add 1 to get 00000001. 00000001 is the Two's Compliment of 11111111. The Two's Compliment of 01011100 is 10100100; 10100011 + 00000001 = 10100100.
By removing 0 from the positive side, we get these nice properties where 11111111 + 1 = 0. We also ensure that the sign is retained. It will always flip which we want because subtracting a number is the same as adding the inverse of that number.
So, for any value of bits, the Two's Compliment will be the value where the original bits have been flipped and 1 has been added to that result. You can then add the Two's Compliment to another value to effectively perform subtraction of the original value.
x - y = x + (Two's Compliment of y)