Two's Complement Representation of Integers

We have already seen that positive integers are represented in base 2 in a computer. Each different type of computer has a fixed number of bits, called the word size, that a typical integer occupies. On most personal computers today the word size is 32 bits. We have seen (in Chapter 2) that Java allows integers to occupy different numbers of bits. An integer declared as type int occupies 32 bits. Generally in programming languages an integer occupies whatever the word size is for the machine (32 bits on the machines in lab); an integer of type long in Java occupies 64 bits. Smaller numbers of bits are used for integers of type byte and short.

The leftmost bit in the representation of a signed integer is always the sign bit. A sign bit of 0 indicates a positive number; a sign bit of 1 indicates a negative number. There are several different schemes for representing negative numbers. The first that may come to mind is to find the base two representation of the absolute value of the number then put a 1 in the sign bit if the number is negative. Thus, the number -89 on a 16-bit machine would be represented as 1000000001011001 (89 is 1011001 in base 2). This is called the sign and magnitude representation of the number. While it seems straightforward it really isn't the best scheme. The problem comes in performing addition and subtraction on such numbers. Remember all the rules about adding signed numbers? There would need to be lots of tests of the sign bits to determine if the numbers were the same sign or not, then if they weren't a test would need to be done to determine which number was larger in absolute value. Too much work!! A much better representation scheme, and the most common one, is called two's complement. Two's complement representation uses an idea fundamental to basic arithmetic: the sum of a number and its negative is 0. In computer arithmetic, the sum of the two's complement representation of a number and the two's complement representation of its negative is 0 (in the computer).

The n-bit two's complement representation of a positive integer is the base 2 representation of the integer with 0s added to the left to give a total of n-bits.

Example: To find the 10-bit two's complement representation of 52 (base 10), first convert 52 to base 2 (you get 110100) then fill out on the left with 0's to get a 10-bit number. So the 10-bit two's complement representation of 52 is 0000110100.

The n-bit two's complement representation of a negative integer is based on two basic properties: the way computers add and the fact that -x (negative x) is the number you must add to x to get 0 (if x is 3, then -x is -3 because 3 + (-3) = 0 and if x is -4 then -x is 4 because -4 + 4 = 0).

Observe that if a 10-bit computer adds 0000110100 and 1111001100 it gets 0... 

		0 0 0 0 1 1 0 1 0 0        (52)
	+	1 1 1 1 0 0 1 1 0 0
		-------------------
		0 0 0 0 0 0 0 0 0 0
The 1 carried out of the leftmost bit is dropped - there is no room for it in 10 bits so the result is just 0. Thus the bit pattern 1111001100 is the 10-bit two's complement representation of -52.

Now we need to see where this comes from. One way to look at it is to think about how we add: we start on the right, adding bits and, if necessary, carrying to the next position to the left. So, if we start with one bit pattern (a number!) and want to find the two's complement representation of the negation of the number we just figure out what bit pattern added to the first one will give 0. This leads us to the first algorithm for finding the two's complement.

Algorithm #1: To find the n-bit two's complement representation of -m (where m is positive):

  1. Find the base 2 (binary) representation of m.
  2. Add the appropriate number of 0s to the left to get n bits total.
  3. Complement each bit to the left of the rightmost 1. (Complement means change 0 to 1 and 1 to 0).

Observe: If you take the two's complement bit pattern of any integer (positive or negative) and complement each bit to the left of the rightmost 1, you get the negation of the integer. For example, if we start with 1111001100 (which is -52) and complement each bit to the left of the rightmost 1 we get 0000110100 (which is 52 - the negation of -52).

Another way to think of the two's complement is as follows. In the addition above, if there were room for the carry bit, the sum would be 210 = 1024. One further observation gives us a way to find the two's complement. Note that 11110011002 = 97210 and 52 + 972 = 1024! So, the 10-bit two's complement representation of -52 is the base 2 representation of 210 - 52 which is 972. In mathematical terms we say that 972 is the additive inverse of 52 modulo 1024 which means it is the number one must add to 52 to get 0 when using addition mod 1024 (add, then divide by 1024 and take the remainder as the answer). An n-bit computer essentially uses arithmetic modulo 2n because its storage is limited to n-bits (throwing away carry bits is equivalent to dividing by 2n and keeping only the remainder). Hence the general principle is as follows:

Algorithm #2: The n-bit two's complement representation of -m (where m is a positive integer) is the base 2 representation of the positive integer 2n - m. In mathematical terms, this is the additive inverse of m modulo 2n. So, to calculate it: Find the base 2 representation of 2n - m.

Algorithm #3: A third algorithm, related to the first is often used. It is as follows:

  1. First, find the binary representation (base 2) of the absolute value of the number. Fill out the number to the appropriate number of bits with 0s in front.
  2. Next, complement each bit (change 0s to 1s and 1s to 0s) - this is called the one's complement.
  3. Finally, add 1.
Some examples:

(1) Find the 16-bit two's complement representation of -89.

Using Algorithm #1:

  1. Find the base 2 representation of 89 - which is 1011001
  2. Fill out with 0s to get 16 bits: 0000000001011001
  3. Complement each bit to the left of the rightmost 1: 1111111110100111
Using Algorithm #2: The 16-bit two's complement representation of -89 is the base 2 representation of 216 - 89 = 65447. Converting 65447 to base 2 gives 1111111110100111. So, -89 is 1111111110100111 in 16-bit two's complement.

(2) Find the two's complement representation of -24 in 8-bits.

Using Algorithm #1:

  1. Find the base 2 representation of 24 - which is 11000
  2. Fill out with 0s to get 8 bits: 00011000
  3. Complement each bit to the left of the rightmost 1: 11101000
Using Algorithm #2: The 8-bit two's complement representation of -24 is the base 2 representation of 28 - 24 = 256 - 24 = 232. 232 in base 2 is 11101000 so -24 is 11101000 in 8-bit two's complement.

(3) Find the base 10 value of the 12-bit two's complement number 000001011011.

First note that this is a positive number because the sign bit is a 0. Hence, the only thing you need to do is convert the base 2 number 1011011 to binary - which is 64 + 16 + 8 + 2 + 1 = 91. So the base 10 value is +91.

(4) Find the base 10 value of the 12-bit two's complement number 111110010001.

  1. First note that this is a negative number because the sign bit is 1. Hence we must complement it to find the number it is the negative of.
  2. Find the two's complement (complement each bit to the left of the rightmost 1): 000001101111
  3. Convert the complement to base 10 - which gives 64 + 32 + 8 + 4 + 2 + 1 = 111. ANSWER: -111
(5) Add the following 12-bit two's complement numbers. Check the work by converting each value to base 10. 
		1 1 1 1 0 0 1 1 1 1 1 1
	+	0 0 0 0 0 1 0 1 1 0 0 0
		-----------------------
		1 1 1 1 1 0 0 1 0 1 1 1
Check: 111100111111 is negative so we complement each bit to the left of the rightmost 1 to get 000011000001. Now convert this to base 10: 128 + 64 + 1 = 193. Hence the base 10 number is -193.

000001011000 is positive so we just find its base 10 value: 64 + 16 + 8 = 88

Finally the sum 111110010111 is negative so we complement - 000001101001 - and convert - 64 + 32 + 8 + 1 = 105. Hence the sum is -105.

Thus we have -193 + 88 = -105 which is correct!

(6) Add the following 12-bit two's complement numbers and check the work. 

		0 1 1 0 0 0 0 0 0 1 0 0
		0 1 0 1 1 0 0 0 0 1 1 0
		-----------------------
		1 0 1 1 1 0 0 0 1 0 1 0
Without doing any work we know something strange happened!! Two positive numbers were added but the sum is negative! Overflow has occurred. Converting to base 10 we see that 011000000100 is +1540 and 010110000110 is +1414 so the sum should be 2954 which is too large for 12 bits. The computer would report an answer of -1142 (the base 10 value of 101110001010). Note that 1142 + 2954 = 4096 which is 212.

Practice Exercises

1. Convert each of the following numbers from the given base to base 10.
  1. 1000112
  2. 10111000102
  3. 45318
  4. B32F16
  5. 4221305
2. Convert each of the following base 2 numbers to base 8 (octal) and base 16 (hexadecimal):
  1. 100110111
  2. 10111011110101
3. Convert the octal number 74038 to
  1. binary
  2. hexadecimal
4. Convert the hexadecimal number 3C9E716 to
  1. binary
  2. octal
5. Convert the following base 10 numbers to binary, octal, hexadecimal, and base 7.
  1. 528
  2. 4269
  3. 341
6. Determine the largest positive integer that can be stored in a word for each of the following word sizes. Assume the word will store signed integers.
  1. 6 bits
  2. 12 bits
  3. 32 bits
7. Find the two's complement representation of each of the following integers. Assume a 16-bit representation:
  1. -198
  2. 37
  3. -37
  4. -5,235
  5. 9,102
  6. -9,102
8. Suppose each of the following bit patterns is an integer represented in 8-bit two's complement. Find the base 10 value of each.
  1. 01110011
  2. 10001001
  3. 11011110
  4. 00000111
  5. 11111111
9. Show that each of the following would overflow if represented in 12-bit two's complement. Determine the value the computer would report for each (that is the value of the 12-bit pattern).
  1. 2,548
  2. -5,377
10. Find the red, green, blue components (in decimal form) of the color represented by the 32-bit pattern: 00001010 00101110 1110101 10001010