Signed Number Representation in Computers

On paper, we can represent a negative number by prefixing it with a minus sign. But, in computers, we will have to encode the sign in the number itself. This article discusses three prominent methods used for representing signed numbers in computers. All three methods work by treating the leftmost digit as a kind of sign bit.

Sign-Magnitude representation

At first glance, the problem of representing signed numbers in a computer might seem quite straightforward. The most obvious solution would be:

• Reserve one digit, possibly the leftmost digit, for representing the sign of the number.
• Use the remaining digits to represent its magnitude. 

The convention is that a sign-bit of 0 indicates a positive number and a sign-bit of 1 indicate a negative number. This method is known as the sign-magnitude representation. It has been used in some computers in the past but it never gained much popularity.

Let us look at the example of a 4-digit number. After dedicating 1 bit for sign, the remaining 3 bits can represent numbers up to 7. This gives us a range of [-7..+7].

Advantages and Disadvantages

Sign-Magnitude representation is the easiest for humans to understand. But it cannot be implemented efficiently in hardware. For performing addition or subtraction we need to first check the sign and magnitude of the operands. The result of these checks determines which operation we need to perform, the order of the operands, and the sign of the result.

Let us say we want to add 0001 and 1010. Here the first number represents +1 and the second number represents -2. So -(2 – 1)  = -1 is what we are looking for. The opcode of the instruction is Add. But we need to check the sign of the operands to see whether addition or subtraction is required. If subtraction is required, we have more work to do. Next, we have to check the magnitude of the numbers. Only then we know which number should be the minuend and which should be the subtrahend.

The previous paragraph might sound like a repetition of basic signed number arithmetic rules. While it might feel natural to us, computers can’t do it efficiently. 1’s complement and 2’s complement provide a better solution, as we will see.

Another problem with sign-magnitude representation is that it has two representations for zero. In our 4-bit example, both 0000 and 1000 represent zero. This would add a fair amount of complexity to the computer.

1’s complement representation

Positive numbers are represented in the same way in both 1’s complement and sign-magnitude. The leftmost digit of all positive numbers has a sign-bit of zero. The remaining digits represent the magnitude of the number. For negative numbers, we find the 1’s complement of the number and use that instead.

Complement forms exist for numbers of all radices or bases. There are two types of complements:

1. The Radix Complement. Also known as r’s complement where r is the radix. So for binary numbers, r’s complement is the same as 2’s complement. For decimal numbers, r’s complement is the same as 10’s complement.

2. The Diminished Radix Complement. Also known as (r-1)’s complement. This is the same as 1’s complement for binary numbers and 9’s complement for decimal numbers.

How to calculate 1’s complement

The formula for finding (r-1)’s complement is rⁿ-1-N. Where r is the radix, n is the number of digits in the number and N is the actual number.

One way to understand this formula would be like this. rⁿ is the smallest n +1 digit integer. Hence  rⁿ-1 is the largest n digit integer. So to find (r-1)’s complement you just find the largest n digit integer and subtract N from it.

An example should make this clear. Let us say you want to find the (r-1)’s or 9’s complement of decimal number 55. Here n is 2 digits and the largest 2 digit integer is 99. So 9’s complement of 55 is 99 – 55 = 44. Similarly, 9’s complement of 555, would be 999 – 555 = 444.

Now let us look at a 1’s complement example. We want to find the 1’s complement of 6₁₀ = 110₂. There are 3 digits in 110 and the largest 3 digit binary integer is 111. 111₂ – 110₂ = 1₂.

There is an easier way to find 1’s complement. Simply invert each bit in the number using not gates. That is, every 1 in the number becomes 0 and every 0 becomes 1. Thus 1’s complement of 110 is 001.

Decimal to 1’s complement mapping for 4-bit numbers

You may have begun to notice that finding the complement of a number is like counting up from the bottom of a list of numbers.

Like the sign-magnitude table, the rows of this table are in the ascending order of the actual numbers used by the computer, not what those numbers represent. Getting familiar with this ordering will help in understanding how 1’s complement or 2’s complement work. The positive numbers plus one of the two zeros take up the top half of the table. The bottom half of the table is reserved for the other zero and the negative numbers.

Advantage

Now, let us address the most important question. What do we gain by representing numbers this way? The benefit is that we can do additions or even subtractions on signed numbers without bothering to check the sign or magnitude of the numbers. Plus we need only adder units to perform both addition and subtraction

1’s Complement Addition

In 1’s complement, addition is done using a variant of modular arithmetic. In modular arithmetic, the values wrap around once we reach some specified maximum. A clock with only an hour handle and hour 12 labeled as 0 would be an example of modulo 12 arithmetic. Since there are 16 elements in our example list we would be doing modulo 16 arithmetic.

There is one unusual rule which we need to follow in 1’s complement addition. If there is a carry out from the most significant digit, it is not brought down to the left of the result as we usually do. Instead, it is added to the result. This might sound a bit confusing, so let us look at some examples.

Examples

Let us say we want to add 5 and -2. In 1’s complement, these numbers are 0101 and 1101 respectively.

If we had done normal addition the result would have been 10010. If we had done true modular addition the result would have been 0010. But 1’s complement addition gives us a result of 0011. We can verify that 0011₂ is 3₁₀. Why the carry out is handled this way is explained in the How does it work? section. For the moment let us focus on the fact that we just added a negative number and a positive number, without bothering about which number has the higher magnitude and got the right result. Will this work if the negative number had the higher magnitude? What about -5₁₀ + 2₁₀ = 1010₂ + 0010₂ ? Let us see.

Find the original number given its 1’s complement

We don’t need to look up a table every time to find what a 1’s complement number represents. There is a simple formula for finding the original number given its 1’s complement. We just need to find 1’s complement of the 1’s complement. This makes sense because we found the 1’s complement by subtracting the original number from 2ⁿ-1.

1’s Complement Subtraction

Let us look at how subtraction works. For example, what if we wanted 5 – 2. For subtraction, there is an extra step. First, we need to do to find the 1’s complement of the subtrahend. After that, it is the same addition we saw in the first example. The extra step does not complicate the hardware since it is a simple step required by all subtraction instructions.

Disadvantage

Despite the advantages provided by 1’s complement, it is not used in any of the modern computers. Its main drawback is that it has two representations of zero. Modern computers use 2’s complement method since it does not have this limitation.

2’s Complement Representation

2’s complement is the method used for representing signed numbers in pretty much all modern computers. It is quite similar to 1’s complement. Once we know 1’s complement, there isn’t much new to learn.

How to calculate

Remember that the formula for finding diminished radix or (r-1)’s complement was rⁿ – 1 – N. Thus the formula for 1’s complement was 2ⁿ – 1 – N.

For radix complement or r’s complement, the formula is rⁿ – N. Where r is the radix, n is the number of digits in the number and N is the number itself. Thus the formula for 2’s complement is 2ⁿ – N.

To find the 2’s complement of a 3-bit number like 110, we find the smallest 4-bit number which is 1000, and subtract 110 from it.

1000₂ − 110₂ = 010₂

Another method for finding 2’s complement is to find 1’s complement first and then add 1. Let us find the 2’s complement of 110₂ using this method. 1’s complement of 110₂ can be found using the bit inversion method mentioned earlier.

x = 110
1’s complement of x = 001 (Just invert each bit)
And now, to find the 2’s complement:-
001₂ + 1₂ = 010₂

There is one special case to consider when finding 2’s complement. If we try to find the 2’s complement of 0, we get a number that won’t fit our word size. In this case, the extra digit on the left must be discarded.

In 2’s complement, there is only one representation of zero. A sign-bit of 0 means zero or a positive number. The numbers with a sign-bit of 1 represent only negative numbers. This means that there is an extra negative number in 2’s complement representation. In our 4-bit number example, the 2’s complement numbers range from [-8 .. +7].

2’s Complement Addition

Rules for addition in 2’s complement are similar to that for 1’s complement. The only difference is that, carry out, if any, from the most significant digit, is simply ignored. There is no need to increment the result by 1. This means that unlike in 1’s complement, in 2’s complement we do true modular arithmetic.

Please note that throwing away the carry to wrap around does not work in all cases of modular addition. For example, it will not work in the clock example mentioned earlier. The trick works in computers because of the ranges we use. If we are doing n digit addition, the largest number we support would be the largest n digit integer. In our 4-bit example, this would be 1111. If we add 1 to it and throw away the carry we get 0000.

Example

Let us try to add 5 and -2 again, this time using 2’s complement. The 2’s complement numbers are 0101 and 1110 respectively.

The carry out from the most significant digit is ignored.

2’s Complement Subtraction

Subtraction is also similar in 2’s complement. The steps are, find the 2’s complement of the subtrahend and add the numbers using 2’s complement rules. The extra negative number which 2’s complement representation has, does pose difficulties. If we try to find the 2’s complement of the negative number with the largest magnitude, we will get the same number back. In our example, the 2’s complement of 1000 is 1000. We have to watch out for this special case.

How does it work?

Let us take a look at how the complement methods work. I will be focusing on 2’s complement, the principles are roughly the same for 1’s complement. I will mention the differences between the two as we go along.

Let us look at another 4-bit, 2’s complement example. Let us say, we want to subtract +2 from +5. For reference, please take a look at table 3 showing the 2’s complement representation of 4-bit numbers. It is important to understand the order of numbers in that table. It may be a good idea to keep the table accessible in a different browser tab. The number which represents +5 is in 6th position in the table and the number is 0101.

Think of it this way, what we need to do is to go up two positions in the list and reach the number representing +3. But we don’t really like going up the list since that would mean having to subtract. We would like to reach our destination by going down the list, that is, by adding numbers. This is how we can achieve this. Go down the list instead of up. When we cross the last element of the list there will be a carry from the most significant digit. Throw away this carry so that we can jump back to the top of the list.

For example, if we are at the bottom of the list where the number is 1111 and we add one to it, we get 10000 which is a 5-bit number. But if we throw away the carry from the most significant digit the result would be 0000, which is the top of our list.

Our list consists of 16 numbers. If we start at the 6th position in the list and add 16 using modulo 16 addition, we will get back to where we started. What if we add 14 instead? We will reach the 4th position where the number is +3, which is where we want to be.

First, we have to figure out which number to add. We find the 2’s complement of the subtrahend, that is the number representing -2. This number is at the second last position of the list. Note that the distance between -2 and the top of the list is 2 when doing modulo 16 addition. Further note that 2 is the number that we want to subtract from 5. Now, all we need to do is a 2’s complement addition of the number representing -2 and the number representing 5 i.e. 1100₂ + 0101₂. There will be a carry out from the most significant digit. We cycle around the list by ignoring this carry and reach our destination of +3.

Check out the image below showing 2’s complement numbers depicted in a circle. We are allowed to move only in a clockwise direction in this circle.

Carry out in 1’s complement addition

Remember that in 1’s complement addition we did not quite follow the modulo addition rules. When there was a carry out from the most significant digit, we did not throw it away. We incremented the result by one instead. The reason why this is required is that in 1’s complement there are two representations of zero. The first element in the list and the last element in the list are both zeros.

Let say, we add the 1’s complement representations of -1 and +2 and throw away the carry from the most significant digit. We may think we will get +1 as the result, but we won’t because there are two zeros between -1 and +1. So each time we make the jump from the zero at the bottom of the list to the zero at the top of the list we have to compensate for the jump by adding a 1 to the result.

So how do we detect that a 1’s complement addition has lead to a jump from one zero to the other? Remember that ignoring the carry from the most significant digit is the trick we use to jump from the bottom of the list to the top of the list. So, all we need to do is to check if there was a carry out from the most significant digit.

Detecting overflow in 2’s complement addition

One very important point which we haven’t looked at so far is the question of overflow. There needs to be a way for the program to detect an overflow. Detecting overflow is a little tricky in 2’s complement.

The results of 2’s complement additions are often larger than our word length. But exceeding word length does not imply an overflow. We could still get a valid result after chopping off the extra bit from the left. On the other hand, we could get an overflow without actually exceeding our word length. For example, adding two positive numbers might produce a negative number as result.

To detect overflow, we need to look at both the carry in and carry out of the most significant digit. As it turns out, there is a simple rule for detecting overflow in 2’s complement addition. If the carry out and carry in for the most significant digit are different, then there is an overflow.

Let us look at some examples from our 4-bit 2’s complement representation to check if the rule holds up. It also gives us an opportunity to take a closer look at how 2’s complement additions work.

When both operands are positive

If both the operands are positive, the result must also be positive. If we add two positive numbers and get a negative number as the result then there is an overflow.

Example a: 2₁₀ + 3₁₀ = 0010₂ + 0011₂

We added 2 positive numbers and the result is also positive. There is no carry out or carry into the most significant digit, so the rule holds.

Example b: 3₁₀ + 5₁₀ = 0011₂ + 0101₂

We added two positive numbers and veered into territory reserved for negative numbers. +8 is too big to be represented as a signed number in a 4-bit word. Notice that there is a carry into the most significant digit but no carry out. This implies an overflow.

When both operands are negative

Remember that the negative numbers are in the bottom half of our list of numbers. When we add negative numbers there will always be a carry from the most significant digit. Each time we will be throwing away this carry so that we can cycle through the list. To avoid an overflow we must cross the positive territory at the top of the list and get back into negative territory.

You could think of the magnitude of a negative number as a distance from its 2’s complement to zero. This does not make sense for normal arithmetic but it does make sense for modular addition since addition wraps around the list. Take a look at the following examples, the binary numbers are in 2’s complement form.

If we take a negative number which is x distance away from 0000₂ and another negative number which is y distance away from 0000₂ and add the two using modular addition, we will get a number which is x + y distance away from 0000_2.

Example a: -1₁₀ + -2₁₀ = 1111₂ + 1110₂

Here we have two operands with small magnitude. This means that their 2’s complements are large numbers. The result easily gets past the top half of the list and reaches the bottom half. There is a carry of 1 coming in and out of the most significant digit, this implies that there is no overflow.

Example b: -7₁₀ + -5₁₀ = 1001₂ + 1011₂

We added two negative numbers and got a positive number as the result. Also, note that there is a carry out of the most significant digit but no carry coming into it.

When the operands have opposite sign

When the operands are of opposite sign, there won’t be an overflow since the result is guaranteed to have a lower magnitude than both the operands. If the operands are small enough to fit our word size, then the result will fit as well.