﻿ TwosComplement

Negative Numbers

Negative numbers represent values less than zero. Everyone knows that. However, negative numbers are a rather modern concept, because the concept of a negative value is not intuitive. You can have five apples, but what of -5 apples?. What are they? One of the first instances of the use of negative numbers is in ancient China (about 202 BCE to 220 CE). Indian mathematicians introduced negative numbers in the 7th century. European mathematicians developed the notion of negative numbers in the 18th century.

Negative numbers are used to represent values that are less than the zero datum; for example, if sea level is zero, then -100m indicates 100 metres below the level of the sea.

If I say I have -\$100 in the bank, it indicates that I owe \$100. In fact, one way of looking at negative numbers is to say that if you have –X then adding X to it results in 0.

Historically, negative numbers were developed I(in Europe) in response to the solutions of equations whose roots were negative.

We represent a negative number by prefixing it with a negative sign; for example, -6.  However, you could argue that the minus sign in -6 is really an indication of how it is to be used. If you perform 8 + -6, you do not carry out addition. Instead, you perform a different operation; that is, subtraction. We will soon see that computers use true negatives in the sense that * + 6 and 8 + -6 are both carried out in the same way be using addition.

Representing Negative Binary Integers

Suppose we use four bits to represent an integer. This gives us the range 0000 to 1111 (or 0 to 15 decimal). How can we represent negative values?

We can’t use a minus sign because that would be quite meaningless. What we can do is to reserve the most-significant bit as a sign bit using 0 for positive and 1 for negative. Now we have a sign and a three bit integer giving us the range

0 000 0

0 001 1

0 010 2

0 011 3

0 100 4

0 101 5

0 110 6

0 111 7

1 000 -0

1 001 -1

1 010 -2

1 011 -3

1 100 -4

1 101 -5

1 110 -6

1 111 -7

The range of numbers is -7 to +7. We have 15 unique values and have been left with two values for 0: a +0 and a  -0 represented by 0000 and 1000, respectively.

This is the sign and magnitude representation of signed numbers and it corresponds to the way people handle negative numbers; that is, the most-significant bit indicates how we handle the number. Computers do not use this system to represent negative integers (although they do use it to represent floating-point numbers like -1.234 x 106).

An alternative technique avoids negative numbers altogether by adding a constant to all numbers so that they are all greater than zero. Consider the previous example with four bits where we add 8 to each number; that is

-8 -8 + 8 = 0 0000

-7 -7 + 8 = 1 0001

-6 -6 + 8 = 2 0010

-5 -5 + 8 = 3 0011

-4 -4 + 8 = 4 0100

-3 -3 + 8 = 5 0101

-2 -2 + 8 = 6 0110

-1 -1 + 8 = 7 0111

0  0 + 8 = 8 1000

1  1 + 8 = 9 1001

2  2 + 8 = 10 1010

3  3 + 8 = 11 1011

4  4 + 8 = 12 1100

5  5 + 8 = 13 1101

6  6 + 8 = 14 1110

7  7 + 8 = 15 1111

In this case we have a range of binary values 0000 to 1111 that correspond to the range 0 to 15 or -8 to +7 if we regard then as signed.

This mechanism is called biased because each number is represented by a value biased by the addition of a constant. In this case, the bias is 8. Note that it is also called excess n notation where n is the value of the bias.

The biased representation of numbers has three advantages; first, there is only one value for 0. Second, it is monotonic because the relative ordering of both the binary integer representation and the biased representation is the same; for example, 0110 is smaller than 1001 irrespective of whether these are unsigned integers or biased values. Finally, the most-significant bit is a sign bit (in this case 1 for positive and 0 for negative).

The biased representation does have one disadvantage. Consider the addition of -2 and +6. This is

0110

1110

10100

This gives a result with a carry out of 16 and the remainder 0100 which is -4. What happened?

If we consider the numbers as X and Y we added their biased forms (X + 8) + (Y + 8) = X + Y + 16. If We require the answer in biased form; that is, X+Y + 8; We ended up with an extra 8. TO demonstrate this, we will subtract 8 from the result we achieved; that is

10100

01000

01100

The answer 1100, when interpreted in biased form is 4, which is what we were expecting. It is easy to see where we went wrong. Adding together two biased numbers, doubles the bias. We then have to remove one to get the expected answer.

So, the biased representation of signed numbers is not used to represent integers. However, it is used to represent the exponent of floating-point numbers.

The system used to university represent signed numbers in integer arithmetic is two’s complement.

Two’s Complement Arithmetic

The two’s complement of a number X is defined as 2n – X, where n is the number of bits used to represent the number. Consider the two’s complement of 3 in four bits. This is 24 – 3 = 16 – 3 = 13 = 1101. We represent -3 by its two’s complement value; that is, -3 is represented by 1101.

In order to understand the significance of this we need to perform an operation; for example, perform 7 – 3. We do this by performing the addition 7 + (-3); that is, we add the two’s complement of 3 to 7.

0111 +7

1101 -3

10100

In this example, we get 10100 which is a carry out of 1 and a result of 0100. If we forget the carryout, the result is correct. What happened?

We added the two’s complement of 3 to 7; that is

7 + (24 – 3) = 24 + 7 - 3 = 24 + 4

Clearly, adding the two’s complement of a number performs subtraction leaving us with a carry out bit that can be ignored.

Two’s complementary arithmetic works for all combinations of values:

X + Y,

X – Y,

-X + Y,

–X – Y.

For example, consider -1 + -2. The two’s complement values of -1 and -2 are 24 – 1 – 15 = 1111 and 24 – 2 = 14 = 1110. Performing the addition of the two two’s complement values, we get

1111 -1

1101 -2

11101

Here we get a carry out and 1101. The expected value is -3 which is 24 – 3 = 16 – 3 = 13 = 1101.

In four bits, the range of values in two’s complement arithmetic is given by:

0000   0

0001  1

0010  2

0011  3

0100  4

0101  5

0110  6

0111  7

1000 -8

1001 -7

1010 -6

1011 -5

1100 -4

1101 -3

1110 -2

1111 -1

The advantages of two’s complement arithmetic are:

The range of values are 2n -1 to +2n-1 -1

The most-significant bit is a sign bit; 0 for positive and 1 for negative

There is only one zero which is represented by 000…0 (all zeroes)

It is very easy to generate two’s complement values: invert the bits and add 1.

The disadvantage of two’s complement arithmetic is that is does not work for multiplication and division. In other words, if you multiple X and –Y you do not get the two’s complement value of –XY. This means that you have to implement two multiplication systems; one for unsigned integers and one for signed integers.

The most important feature of two’s complement arithmetic is that you can form –X without subtraction; that is you do not need subtraction to calculate 2n – X.

An alternative way of forming two’s complement values is to invert the bits and add 1. Consider -3. The 4-bit value of 3 is 0011. If we invert the bits, we get 1100. Adding 1 gives 1101 which is the correct two’s complement representation of -3.

It is important to remember that when using two’s complement arithmetic, you cannot drop leading zeroes. In 8 bits + 5 is 00000101. You cannot write this as 101 because you have to include the sign-bit, the left-most bit.

Arithmetic Overflow

We said that a two’s complement value in n bits has the range 2n -1 to +2n-1 -1. In 4 bits, this is the range -8 to +7. Suppose we go outside this range by adding 5 + 6. We get:

0101 +5

0110 +6

1011

Note that the result is correct if we regard the numbers as unsigned. However, we are using signed two’s complement arithmetic and the result, 1011 is equal to -5.

Adding two positive numbers whose total exceeds 7 leads to a negative result. Similarly, subtracting two negative numbers whose total is more negative than -8 leads to a positive result. Both these results are called arithmetic overflow.

In 8-bit arithmetic the range of unsigned values is 0 to 255 and the range of two’s complement values is -128 to +127.

Summary of Basic Points

Negative integers can be represented in a signed form by means of two’s complement notation.

The value –X is represented in two’s complement form by 2n – X where n is the number of bits in the number.

A two’s complement value, 2nX, can be calculated by inverting all the bits of X and adding 1.

If you add two numbers (with negative values in two’s complement form) negative numbers will be automatically subtracted; that is, you do not need to perform subtraction because subtraction is implemented by adding a complement.

A two’s complement value is a true complement in the sense that adding X + (-X) = 0.

The range of possible values of a signed two’s complement value in n bits is  2n -1 to +2n-1 -1

If you add two positive integers or subtract two negative integers and the value of the result is outside the range of values that can be represented, then arithmetic overflow has taken place.

If you extend the number of bits in an n-bit two’s complement word by k bits (i.e., the new word is n+k bits long), you replicate the sign bit k times inserting k 0s for a positive value and k 1s for a negative value.

Examples of Two’s Complement Problems

1. What is a two’s complement number?

A two’s complement number is a way of representing a negative integer and is defined as 2n – X, where n is the number of bits in the representation and X is the integer.

2. Why are two’s complement numbers used to represent negative integers?

Because  adding the two’s complement of X is the same as subtracting X. This means that you do not need both an adder and a subtractor. To add X and Y you present X and Y to an adder. To subtract X form Y you present Y and the two’s complement of X to the same adder.

It is easy to form a two’s complement number by inverting the bits and adding 1.

3. What other systems (conventions) are used to represent negative numbers?

Sign and magnitude representation uses a sign bit to indicate the sign and then the remaining bits represent the number. This form is used only in the representation of floating point values.

Biased numbers or excess numbers add a constant to the number to be represented to ensure that all representations are positive. This mechanism is used only in floating point arithmetic to represent exponents.

4. What is the range of a two’s complement number in 10 bits?

The range of legal two’s complement values in n bits is -2n-1 to +2n-1-1. If n = 10, the range is 29 to +29-1 or -512 to +511.

5. How can you tell whether a given binary integer is in a two’s complement or an unsigned integer form?

You can’t. In four bits it is impossible to determine whether 1001 represents +9 (unsigned) or -7 (signed). If you are dealing with unsigned integers, you treat the number as +9. If you are dealing with signed two’s complement numbers, you treat the value as -7.

6. What is arithmetic overflow?

Arithmetic overflow takes place in two’s complement arithmetic when the result of an operation falls outside the range or representable numbers. Typically, this means that adding two numbers is greater than the maximum, or subtracting two numbers is less than the minimum.

7. A two’s complement integer in 8 bits is 10111000. This value is to be converted into a 12-bit two’s complement number. What is the new 12-bit value?

To sign-extend a two’s complement number, the sign-bit is replicated. In this case we are going from 8 to 12 bits which requires four additional bits. The sign bit is 1 so we must prepend four ons to the left of 10111000 to get 111110111000.

8. In 8-bit arithmetic, calculate the two’s complement values corresponding to:

a. +5

b. -5

c. -1

d. -129

e. -57

a. +5 00000101 00000101 No change: positive

b. -5 00000101 11111011 Invert bits, add 1

c. -1 00000001 11111111 Invert bits, add 1

d. -129 10000001    Not possible – out of range

e. -57 00111001 11000111 Invert bits, add 1

9. Convert the following values into binary form and carry out the calculations using two’s complement arithmetic in six bits.