Data Representation - Two's Complement Numbers

 

Computers use base 2 numbers to represent integers. An integer is stored in a fixed number of bits. The number of bits used varies on different computers. On some computers, an integer is stored in two bytes, or 16 bits. On other computers, an integer is stored in four bytes, or 32 bits, and some computers support integers of both sizes. On MIPS processors integers are stored in 32 bits.

Computers must be able to represent both positive and negative integers. One possible representation is called sign and magnitude. In this representation, the leftmost bit gives the sign of the number, and the other bits contain the base 2 representation of the number. This representation is easy for humans (it's the one we use in base 10). But it makes it difficult for computers to compute the sign of the answer when adding and subtracting. Thus computers use a different representation for integers.

2's Complement Representation

In 2's complement, the leftmost bit is used for the sign of the number. A positive number has a 0 for the sign, and a negative number has a 1 for the sign. To change the sign of a number (i.e., to get the complement), simply flip all the bits of the number (every 1 is changed to a 0, and every 0 is changed to a 1), and then add 1.

Given a number in base 2, convert the number to N bit 2's complement representation as follows. Note that the base 2 number can contain at most N-1 bits; if it contains more than N-1 bits it cannot be represented in N bit 2's complement.

Note that the rules for negating a 2's complement number can be used in either direction. TO change the sign of a 2's complement number (from positive to negative or from negative to positive), flip all the bits and add one.

Examples

Decimal Number Binary Number (Sign and Magnitude Representation) 8 Bit 2's Complement Representation
0 0 00000000
1 1 00000001
-1 -1 11111111
2 10 00000010
-2 -10 11111110
4 100 00000100
-4 -100 11111100
64 1000000 01000000
-64 -1000000 11000000
46 101110 00101110
127 1111111 01111111
-127 -1111111 10000001
-128 -10000000 10000000
-26 -11010 11100110

2's Complement Addition and Subtraction

Once the numbers are converted to 2's complement form, it is easy to add them. Add the two numbers just like you normally add base 2 numbers. The beauty of 2's complement is that it doesn't matter whether the numbers are positive or negative or a mix of both: the rule is the same, just add the two numbers. If there is a carry beyond the leftmost column, ignore it. This carry does not indicate any kind of error.

Notice that this gives us the very desirable (actually essential) characteristic that adding a number p and its complement -p gives us zero. Try it with a couple of the examples given above.

An overflow occurs when the result of an operation does not fit into the memory allocated. This is an error, because the answer will not be correct. The computer may or may not raise an error condition; for many machines it is the responsibility of the programmer to check whether an overflow has occurred. Overflow is possible only when adding numbers of the same sign. Think about why this is true for a minute.

In 2's complement it is easy to detect an overflow after adding two numbers. If the two numbers that are added have the same sign, and the answer has a different sign, then there was an overflow. Otherwise, there was no overflow.

To subtract 2's complement numbers, use the standard rule for subtraction: change the sign of the subtrahend (the number being subtracted) and add:

  1. To change the sign of the subtrahend, flip all the bits and add 1.
  2. Add the two numbers using the addition rules given above.

If the numbers that are added have the same sign, then use the rule given above to detect whether an overflow has occurred.

Examples


     00101110     (46)                   11000011     (-61)
   + 00111101     (61)                 + 00010011      (19)
   ----------                          ----------
     01101011    (107)                   11010110     (-42)




     11000011    (-61)                   00101110      (46)
   + 11011111    (-33)                 + 01011110      (94)
   ----------                          ----------
     10100010    (-94)                   10001100     overflow




     00101101     (45)    --->           00101101      (45)
   - 00010110     (22)    --->         + 11101010     (-22)
   ----------                          ----------
                                         00010111      (23)




     00111101     (61)    --->           00111101      (61)
   - 11110110    (-10)    --->         + 00001010      (10)
   ----------                          ----------
                                         01000111      (71)


Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2009