Negative Numbers
So far, we have only talked about non-negative values (i.e., positive and zero). We call this unsigned numbers1.
Representations that allow negative values are called signed numbers. By default, in C, all numbers are signed numbers.
There are several problems with trying to represent negative values. Most commonly, how do we actually try to operate on negative numbers? In particular, we are typically interested in adding two (possibly negative) numbers. If we can do that, then we can do subtraction since:
x - y ≡ x + (-y)
The four most common representations are:
For revision, you may look at the summary instead.
Binary Addition
We will start with a simple concept of binary addition.
For now, we will ignore the sign and assume everything is non-negative.
Furthermore, we will illustrate binary addition by first showing our usual addition in base 10.
Simplifying this further, we can ask ourselves how do we do +1?
Add 1
In base 10, for any digit smaller than 9, it is easy to do +1.
We simply change it to the next larger digit.
But with 9, there is no next larger digit!
We have to change this to the smallest digit 0 and carry the value 1 to the next digit.
| Digit | +1 |
Digit | +1 |
|---|---|---|---|
| 0 | 1 | 5 | 6 |
| 1 | 2 | 6 | 7 |
| 2 | 3 | 7 | 8 |
| 3 | 4 | 8 | 9 |
| 4 | 1 | 9 | 0 (with carry) |
We can illustrate that by trying to add 1 to 499.
Since the carry may exceed the number of digits currently available in a number, we may have to put the carry as part of the answer. Think of it like instead of having a number 99, we have a number 099.
You can try playing around with this.
Press +1 to see how it works.
What is special the base 10 is that there are 10 symbols 0-9. In binary, there are only 2 symbols 0 and 1. So, if we try to add 1 to 1, we cannot put the symbol 2. Instead, the behaviour is similar to adding 1 to 9. We put 0 and carry the value 1 to the next digit.
Again, you can try playing around with this.
Press +1 to see how it works.
Another way to do this in a more uniform way is to start with a carry of 0.
Addition
Now we are ready to perform an addition.
Simplistically, adding two numbers A + B is really just doing +1 to A as many times as the value of B2.
That is easy if B is small, but can be tedious if B is extremely large.
But if you remember how to do long decimal addition, the same technique transfers easily to long binary addition. You just have to keep in mind that the largest symbol is 1 instead of 9. Remember, the trick for long addition is to add the respective digit from A with the respective digit from B as well as the carry.
You can test this example by setting the number to 89 and press +1 11 times.
Alternatively, if you are patient enough, set the number to 11 and press +1 89 times.
Again, this also works for binary numbers. In the example below, the result has 1 more bit the inputs. As you will see later, we may need to truncate the result to the required number of bits.
You can test this example by setting the number to 101 and press +1 3 times.