How to represent negative integers in binary
In our common decimal numerical system we are used to see the minus sign when we have negative numbers. This means that, beyond the common 10 digits, we can also use the minus sign to tell the number is negative.
In the computer’s world we only have zeros and ones and there is no way to use the minus sign. So, how can we represent and deal with negative numbers?
Let’s say we want to build a calculator in binary. To start with, we have to take into account the number of bits we want to use in our “calculator”. So, let’s start by considering we have 8 bits. In this case, we’ll have 28 = 256 combinations we can number from 0000 0000 to 1111 1111 in binary, or from 0 to 255 in decimal. And as a reminder, from 00h to FFh in hexadecimal.
The solution is to use one bit to identify whether a number is positive or negative and we will name that bit as the sign bit. Normally, the sign bit is the MSB (Most Significant Bit) in our binary number. If we use a sign bit, we will have 7 bits left to represent numbers but now we can say whether they are positive or negative. For each part (positive and negative) we will have 27 = 128 combinations.
There are some different ways to codify positive and negative numbers. In this article I’m going to talk about the most common way: The two’s complement.
In the two’s complement, when a number is positive, the sign bit (MSB) will be 0. So, we have a range of positive numbers from 0000 0000 to 0111 1111 in binary, or from 0 to 127 in decimal. And here we have the “non negative” 128 combinations, including zero. To represent a negative number, the sign bit will be set to 1. In this case, we can have a range of negative numbers from 1000 0000 to 1111 1111. But how this range will be represented in decimal? I’m going to say in advance that it will be from -128 to -1 (because we have 128 combinations for negative numbers),
But how can we determine the negative number? By using the two’s complement rule, we have to:
- Invert all the bits (to this step we also call it the one’s complement)
- Add +1
Let’s see an example:
- 1000 0000 → (inverting all bits) 0111 1111 → adding +1 = 1000 0000 (2) = 128 (10)
- 1111 1111 → (inverting all bits) 0000 0000 → adding +1 = 0000 0001 (2) = 1 (10)
Because we had the sign bit set to 1, the results will be -128 and -1, respectively.
Let’s see another example. Let’s represent the following binary number to decimal with a sign bit:
1101 0011 (2)
To simplify, let’s use a table to apply the two’s complement:
1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
+ | 1 | ||||||
0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
We applied an inversion of bits and we add + 1. So we got the number 0010 1101 which in decimal is:
1 × 25 + 1 × 23 + 1 × 22 + 1 × 20 = 32 + 8 + 4 + 1 = 45
This means that: 1101 0011 (2) = -45 (10)
NOTE: We only use the two’s complement rule when the sign bit is 1!
Let’s see the following table and compare the numbers for signed and unsigned decimal numbers:
Binary number | Signed Decimal (two's complement) | Unsigned Decimal |
---|---|---|
0000 0000 | 0 | 0 |
0000 0001 | 1 | 1 |
... | ... | ... |
0111 1110 | 126 | 126 |
0111 1111 | 127 | 127 |
1000 0000 | -128 | 128 |
1000 0001 | -127 | 129 |
1000 0010 | -126 | 130 |
... | ... | ... |
1111 1100 | -4 | 252 |
1111 1101 | -3 | 253 |
1111 1110 | -2 | 254 |
1111 1111 | -1 | 255 |
One great advantage of using the two’s complement is its direct applicability in addition and subtraction operations, among others as we’ll see later.
For instance, if we have in binary the number 0000 0000, or 0 in decimal, and if we subtract 1, we know that after the “carry 1” operations1, the binary number will be 1111 1111, or -1 in decimal (using the two’s complement). On the other hand, if we have the number 1111 1111 in binary (-1) and if we add 1, after the “carry 1” operations1 we will get 0000 0000 (or 0 in decimal).
Let’s see the following addition operation: 65 + (-45) in binary:
0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | |
+ | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
We have an extra “bit”, the carrier bit and set to 1 but it will be ignored. The carrier is a CPU flag and it is present in the table just to remind you that, in the end of an operation, if we still have a “carry 1”, this flag will become active. So, we have as a result the binary number 0001 0100 which is 20 in decimal. Just notice that the operation is straight forward when we apply to two’s complement, which is a great advantage! We can also see that the sign bit of the first member is 0 because the number is positive and, in the second member, is 1 because the number is negative. The sign bit in the result is 0 because it is positive!
So: 65 + (-45) = 20 in decimal.
Let’s see another example:
-127 + 15 (-127) is in a table above and it is 1000 0001 in binary using the two’s complement)
1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
+ | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
Once again, the carrier is present just to remind you that this bit exists in the CPU. Here we can just ignore it. Let’s look again at the sign bits. In the result we have the sign bit set to 1 which means the result is negative. So, let’s apply the two’s complement to determine the final solution.
1001 0000 → (inverting all bits) 0110 1111 → +1 = 0111 0000 (2) = 112 (10)
This means that: -127 + 15 = -112 in decimal.
Notions of overflow and underflow:
Let’s now imagine we want to make the following sum: 96 + 48:
0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | |
+ | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
You can see we have here two positive numbers but the result appears as negative. If we were working with unsigned numbers the result would be correct bacause 96 + 48 = 144, but we are working with signed numbers! Thus, something is wrong! In fact, if we apply the two’s complement we can verify that:
1001 0000 → (inverting all bits) 0110 0000 → +1 = 0110 0001(2) = 97(10)
The means that 96 + 48 = -97! Which is completely wrong!
Remember that the positive limit in this case is 127 and the real result is greater than this value! 144 is greater that 127! So, we have here a case of an OVERFLOW. This means we exceeded the positive limit!
This would also happen if we were implementing a binary counter with a step of 1 (increasing 1 by 1). When the counter reaches 0111 1111 in binary (127 in decimal) it would turn to 1000 000 in binary (-128 in signed decimal) and then we could also say that an overflow has occurred.
Now, let’s see another operation: -112 + (-32)
And let’s also use this example to see how can we get the binary representation of -32 using the inverse of the two’s complement:
32 (10) = 0010 0000 (2) → -1 = 0001 1111 → (inverting all bits) 1110 0000
1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | |
+ | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Notice that we have both members negative and the result is positive, so something is wrong! In fact, -112 – 32 would be –144, but again it’s below the negative limit of -128. And if we convert the result to decimal, we can conclude that -112 + (-32) ≠ 112! In this case we can say that we have an UNDERFLOW! We exceeded the negative limit!
The same would happen if we were implementing a binady counter with a step of -1 (decreasing 1 by 1). When the counter reaches 1000 000 in binary (-128 in decimal) it would turn 0111 1111 in binary (127 in decimal and then we could also say that an underflow has occurred.
But how can we test these cases?
There are some basic conditions to verify if we exceeded the positive or negative limits:
- If the addition of two positive numbers (sign bits set to 0) returns a negative result (sign bit set to 1) then we have an overflow!
- If the addition of two negative numbers (sign bits set to 1) returns a positive result (sign bit set to 0) then we have an underflow!
Regarding the subtraction it is also possible to verify these errors but with some different rules. Let’s see an equivalent example of an overflow:
96 + 48 = 96 – (-48)
Once again, let’s determine -48 by the inverse process of the two’s complement:
48 (10) = 0011 0000 (2) → -1 = 0010 1111 → (inverting all bits) 1101 0000
Let’s take a look at the calculations:
0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | |
- | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
Notice that we have again: 96 – (-48) ≠ -97
So, here comes a rule for subtraction:
- If the subtrecion of a positive number (sign bit set to 0) with a negative number (sign bit set to 1) – which is the same of the addition of two positive numbers – returns a negative value (sign bit set to 1) then we have an overflow!
Now let’s see an underflow:
-112 + (-32) = -112 – 32
1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | |
- | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
We got again the positive number 112! Which is wrong!
So, here comes another rule for subtraction:
- If the subtraction of a negative number (sign bit set to 1) with a positive number (sign bit set to 0) – which is the same of the addition of two negative numbers – returns a positive number (sign bit set to 0) then we have an underflow!
To end with, when we work with the CPU code (machine code or assembly), we can also check for a general case of an overflow by checking a bit on the flags register implemented by most processors. I’ll show you some examples of this soon.
Footnotes:
- Read the article “Arithmetic operations in binary” for more informations on adding and subtracting binary numbers