Integer Arithmetic

Signed-Magnitude Representation

In considering arithmetic in the computer, we must be able to represent negative integers. Several methods have been used for expressing negative numbers in the computer. The most obvious way is to convert the number to binary and stick on another bit to indicate sign, 0 for positive and 1 for negative. Suppose integers are stored using this signed-magnitude technique in 8 bits so that the leftmost or most significant bit holds the sign while the remaining bits represent the magnitude. Consequently, 0010 1001₂ represents +41₁₀.

With the leftmost bit being 1, 1010 1001₂ represents -41₁₀.

Early computers used signed-magnitude, but the circuitry for arithmetic was complicated, and the mapping from the signed-magnitude representation to decimal integers was not one-to-one. For example, representing zero as all zero's, (0000 0000) seems natural; but that represents +0. The bit string 1000 0000 indicates -0. Thus, to determine if a variable had a value of zero, the programmer had to check if the variable was +0 or -0

Definition

The signed-magnitude representation of signed integers expresses the number in binary in a fixed number of bits; and the most significant (leftmost) bit indicates the sign, 0 for positive and 1 for negative.

Two's Complement Representation
A method of representing numbers that avoids this problem and simplifies the arithmetic and circuitry is called two's complement notation. We can still determine the sign by looking at the most significant bit. Positive integers have a most significant bit of 0, while this bit for negative integers is 1. Moreover, the two's complement notation for a positive integer is identical to its signed-magnitude representation. For negative numbers, however, the sequence of bits after the most significant bit of 1 is not the magnitude in base 2.

Let us consider the process of obtaining the two's complement representation of a negative integer, such as -41. We first convert the absolute value or magnitude of 41 to binary.

41₁₀ = 0010 1001₂
Then we take the complement of each bit, which is its opposite value. Consequently, ones become zeros; and zeros become ones. This number, 1101 0110₂, is called the one's complement of 41.

Notice that even the sign bit changes.

Definition

The complement of a bit is its opposite value, 0 or 1. The one's complement of binary number is the number with each bit complemented.

Another way to take the one's complement that will be helpful when considering other bases is to subtract the number from all ones. After all, 1 - 0 = 1 and 1 - 1 = 0. Thus,

1111 1111

- 0010 1001

1101 0110

To complete the process of deriving the two's complement, we increment or add one to this one's complement by 1.

-41₁₀ = 1101 0111₂

Algorithm 2.1   Algorithm for Computing the Two's Complement of a Binary Integer:

     find the one's complement by complementing each bit, 0 <-> 1
     increment the result by 1

The two's complement representation of a nonnegative integer (such as 41) is its representation in the binary number system (such as 0010 1001₂). To express a negative integer (such as -41) in two's complement representation, we express the corresponding positive integer (41) in the binary number system (0010 1001₂) and take the two's complement of that binary integer (1101 0111).

Example 2.1 Let us go through this process to express the decimal integers 104 and -104 in 8 bits with two's complement representation. The initial step is to convert 104 to binary.

We place a zero bit at the beginning to show the sign (positive) for the 8-bit number and obtain 104₁₀ = 0110 1000₂. Since 104 is positive, we are through for the first number. With -104, we complement each bit and then add 1.

Thus, -104₁₀ = 1001 1000.

If the computer stores integers using 16 bits, we take the two's complement of 0000 0000 0110 1000₂, yielding 1111 1111 1001 1000₂.

One trick of taking the two's complement of a binary number like 0110 1000₂ is to start at the left, complementing every bit down to, but not including, the rightmost 1. Thus, the four leftmost bits of 0110 1000₂ are each complemented, while those on the right are not.

Rewind Forward
Notice that if we take the two's complement of this representation, 1001 1000 = -104₁₀, we return to its positive counterpart, 0110 1000₂ = +104₁₀. In general, the two's complement of the two's complement is the original number; just as taking the negative of a negative is positive. Two's complement representation not only agrees with this property of numbers; but it is easy to implement in the circuitry of the computer; and there is only one representation for zero.

Example 2.2 If a computer uses 8-bit, two's complement representation for integers, let us determine what decimal numbers the following two's complement integers represent. a. 0000 0101 b. 1111 1011 c. 0111 1111 d. 1000 0000 e. 1111 1111

a. The leading 0 indicates that 0000 0101 is a positive integer, so we can determine immediately that it represents 4 + 1 = +5.

b. With the most significant bit being 1, 1111 1011 represents a negative integer. To determine the magnitude, we take the two's complement by complementing all bits up to but not including the rightmost 1 (or by subtracting the number from 1111 1111 and then adding 1)--- 0000 0101. Consequently, 1111 1011 is the representation for -5.

c. 0111 1111 represents a positive integer that is one less than the unsigned binary integer 1000 0000 = 128₁₀. Thus, our original number is 127.

d. 1000 0000 represents a negative integer. To determine the magnitude of the number, we determine the decimal equivalent of its two's complement. The two's complement of this number, however, is also 1000 0000, which represents 128 in base 2. Thus, the sequence of bits in two's complement notation represents -128₁₀. Moreover, this number is the smallest integer that can be expressed in 8-bit, two's complement representation. Thus, the range of 8-bit signed integers is from -128₁₀ to 27₁₀. We have one more negative integer than positive.

e. The two's complement of 1111 1111₂ is 0000 0001₂, indicating that the original number represents the largest negative integer, -1₁₀.

Example 2.3 Following the same procedure as in Parts c and d of the last example, let us find the range of the decimal integers using 16-bit, two's complement representation. The largest positive integer is

0111 1111 1111 1111 = 32,767
which is one less than the unsigned integer 1000 0000 0000 0000 = 2₁₅ = 32,768. The smallest negative integer is 1000 0000 0000 0000 in two's complement notation. As in Part d above, this integer is its own two's complement. Therefore, -32,768 is the smallest negative integer. Many microcomputers store integers in 16 bits, so that the range of number of type int is from -32,768 to 32,767.

Quick Review Questions

1. Express the decimal number 91 in 8-bit, two's complement representation.
2. Express the decimal number -91 in 8-bit, two's complement representation.
3. Express the decimal number 91 in 16-bit, two's complement representation.
4. Express the decimal number -91 in 16-bit, two's complement representation.
5. The numbers 0111 1100 and 0011 1010 are expressed in two's complement representation. Which is the larger of the two signed integers?

Addition
We did a limited amount of addition using a carry as we counted in base 2. Recall in incrementing, if the digit to which we are adding 1 is the largest in that base, we write down 0 and carry 1. The carry is added to the next position, such as in the following examples:

Base 10	Base 2

Notice how the carry occurs in each problem.

39 + 1 = ((3)(10) + 9) + 1 = (3)(10) + (1)(10) = (4)(10)

100111 + 1	= (25 + 22 + 2 + 1)₁₀ + 1
	= 2⁵ + 2² + 2 + 2
	= 2⁵ + 2² + (2)(2)
	= 2⁵ + 2² + 2²
	= 2⁵ + (2)(2²)
	= 2⁵ + 2³ = 101000₂

Adding numbers other than 1 is similar. Consider the binary sum 1011 + 11.

One of the big advantages of two's complement arithmetic is that we can use the same circuitry for adding positive or negative numbers. Consider the following sum:

	Unsigned	Signed
1011 1110 =	190	-66
+0010 1101 =	+ 45	+ 45
1110 1011 =	235	-21

As unsigned integers, 1011 1110₂ and 0010 1101₂ are 190 and 45, respectively; and their sum is 1110 1011₂ or 235. As an 8-bit, two's complement integer 1011 1110 represents -66; and the sum, which now represents -21, is still correct.

Quick Review Question

6. Perform the indicated operation on the 8-bit, two's complement representations for integers. Convert to base 10 to check your answer.

0010 1011

+ 0101 1101

Subtraction
Subtraction in different bases parallels subtraction in the decimal number system. To subtract y from x in base 10, we change the sign of y and add. For example, 10 - (-7) = 10 + +7 = 17 or 35 - 6 = 35 + (-6) = 29. Similarly, when using two's complement representation, to subtract y from x, we take the two's complement of the code for y and add.

Example 2.4 Let us perform the following subtraction using 8-bit, two's complement integers.

		Check in base 10
0011 1011	0011 1011 =	59
- 1110 1001	� 0001 0111 =	- (-23)
	0101 0010₂ =	82₁₀

Overflow
Suppose we are working on a microcomputer with 16-bit integers, and we have the following statements for int variable i.

	i = 20480;
	i = i + 16384;
	cout << i << endl;

Surprisingly, the value printed will be -28672 instead of the correct answer of 36864.

0101 0000 0000 0000 =	20,480
+ 0100 0000 0000 0000 =	+ 16,384
1001 0000 0000 0000₂ =	-28,672

The problem arises when the leftmost bit, the sign bit, gets the carry from the addition of 1 and 1, converting the result to a negative number. There simply are not enough bits to express the answer; and, consequently, the final answer has the wrong sign. We must be conscious of this problem, called overflow, on any computer; but overflow is more likely to occur on microcomputers because they use fewer bytes to hold numbers than larger computers. Overflow also happens when we add two negative integers and get a positive result. For example, if 8 bits store an integer, addition of -128 and -128 ends in an overflow value of 0.

1000 0000 =	-128
+ 1000 0000 =	-128
0000 0000 =	0

Definition

Overflow is an error condition that occurs when there are not enough bits to express a value.

Exercises
Express each of the decimal numbers of Exercises 1 - 6 in 8-bit, two's complement representation.

1. 115	2. -37	3. -64
4. -151	5. 128	6. -6

7. Express the decimal number -151 in 16-bit, two's complement representation.

8. Find the range of decimal integers that can be expressed with two's complement representation.
a. With 32 bits.
b. With 64 bits.

The numbers in Exercises 9-10 are expressed in two's complement representation. In each case, give the larger of the two signed integers.

9. 0011 1111, 1100 0000

10. 1111 1111, 1001 0011

Find the sums of the unsigned numbers in base 2 in Exercises 11-12.

11. 11 1110 1111 + 10 1101

12. 1111 + 1001 + 1 1011 + 101

For Exercises 13-15 perform the indicated operations on the 8-bit, two's complement representations for integers. Convert to base 10 to check your answer.

13. 1001 1100
+ 0111 0100

14. 1110 0000
+ 1001 1100

15. 0011 0110
- 1111 0110

Section 2 Programming Project
Write a program using sizeof to determine the number of bytes to store an integer on your computer. From this result find the range of integers that your computer can store. Revise the program to print the largest and smallest integers. Then add 1 to the largest integer, subtract 1 from the smallest, and print the results. Be sure to label your output well. Write an explanation of the results using calculations similar to those in this section.