DISCRETE MATH

ONE’S COMPLEMENT   &    TWO’S COMPLEMENT

 

 

One’s complement representations of integers are used to simplify computer arithmetic.  To represent positive and negative integers with absolute value less than 2n-1, a total of n bits is used.  The leftmost bit is used to represent the sign.  A 0 bit in this position is used for positive integers, and a 1 in this position is used for negative integers.  For positive integers the remaining bits are identical to the binary expansion of the integer.  For negative integers, the remaining bits are obtained by first finding the binary expansion of the absolute value of the integer, and then taking the complement of each of these bits.

 

Two’s complement representations of integers are also used to simplify computer arithmetic and are used more commonly than one’s complement representations.  To represent an integer x with –2n-1  £  x  £  2n-1-1 for a specified positive integer n, a total of n bits is used.  The leftmost bit is used to represent the sign.  A 0 bit in this position is used for positive integers, and a 1 bit in this position is used for negative integers, just as in one’s complement expansions.  For a positive integer, the remaining bits are identical to the binary expansion of the integer.  For a negative integer, the remaining bits are the bits of the binary expansion of 2n-1-½x½.  Two’s complement expansions of integers are often used by computers because addition and subtraction of integers can be performed easily using these expansions, where these integers can be either positive or negative.  Specifically, only two electronic circuits are required—one to invert and the second to add.

 

 

 

 

 

 

 

 

 

In the table below, the two’s complement representations for the integers from –8 to 7 are given using four bits.

 

TWO’S COMPLEMENT NOTATION

VALUE REPRESENTED

FOUR-BIT PATTERN

7

0111

6

0110

5

0101

4

0100

3

0011

2

0010

1

0001

0

0000

-1

1111

-2

1110

-3

1101

-4

1100

-5

1011

-6

1010

-7

1001

-8

1000

 To obtain the results for

-8  £  x  £  -1, first consider the binary representation of ½x½.  Then do the following:

1)     Replace each 0 in the binary representation of ½x½ by 1 and vice versa.  This is the one’s complement of x.

2)      Add 1 (0001 in this case) to the result in step (1).  This result is called the two’s complement of x.

 

For example, to obtain the two’s complement (representation) of –6,

 

Absolute value of –6                                6

 

Binary representation of 6                    0110

 

Interchange the 0’s and the 1’s                             1001

 

Add 1 to prior result                                1001 + 0001 = 1010

 

Note that the binary representation of any positive integer in the table and its one’s complement add to 24 –1.  For example, 

 

0 + (-1) = 0000 + 1111 = 1111 = 24 – 1

1 + (-2) = 0001 + 1110 = 1111 = 24 – 1

2 + (-3) = 0010 + 1101 = 1111 = 24 – 1

3 + (-4) = 0011 + 1100 = 1111 = 24 – 1

4 + (-5) = 0100 + 1011 = 1111 = 24 – 1

5 + (-6) = 0101 + 1010 = 1111 = 24 – 1

6 + (-7) = 0110 + 1001 = 1111 = 24 – 1

7 + (-8) = 0111 + 1000 = 1111 = 24 – 1.

 

In other words, if y is the binary representation of the absolute value of a negative integer, let y’ be the one’s complement of y and y’’ be the two’s complement of y, then y + y’’ = y + y’ + 1 = 24.

 

Rosen (5th edition), 2.5

30) Find the one’s complement representations, using bit strings of length six, of the following integers.

a) 22   [(22)10 = (10110)2  one’s complement representation is 010110.]

b) 31   [(31)10 = (11111)2  one’s complement representation is 011111.]

c) –7   [(7)10 = (111)2  complement 000111 to get 111000 as the one’s complement representation for –7.]

d) –19  [(19)10 = (10011)2  complement 010011 to get 101100 as the one’s complement representation for –19.]

 

31) What integer does each of the following one’s complement representations of length five represent?

a)     11001  [The number is negative because leftmost bit is one.  Complement 1001 to get 0110 which is the binary representation of 6, 11001 is the one’s complement of –6.]

b)    01101   [The number is positive because leftmost bit is zero.  1101 is the binary representation of 13, 01101 is the one’s complement of 13.]

c)     10001   [The number is negative because leftmost bit is one.  Complement 0001 to get 1110 which is the binary representation of 14, 10001 is the one’s complement of –14.]

d)    11111   [The number is negative because leftmost bit is one.  Complement 1111 to get 0000 which is the binary representation of 0, 11111 is the one’s complement of –0 = 0.  Note that there are two one’s complement representations for 0, namely, 11111 and 00000.]

 

36) Find the two’s complement representations, using bit strings of length six, of the following integers.

a) 22   [(22)10 = (10110)2  two’s complement representation is 010110.]

b) 31   [(31)10 = (11111)2  two’s complement representation is 011111.]

c) –7   [(7)10 = (111)2  complement 000111 to get 111000 as the one’s complement representation for –7.  Now add 1 (000001) to 111000 to get  111001 as the two’s complement of –7.]

d) –19  [(19)10 = (10011)2  complement 010011 to get 101100 as the one’s complement representation for –19.  Now add 1 (000001) to 101100 to get  101101 as the two’s complement of –19.]

 

37) What integer does each of the following two’s complement representations of length five represent?

a)     11001  [The number is negative because leftmost bit is one.  Complement 1001 to get 0110 now add 0001 to get 0111 which is the binary representation of 7, 11001 is the two’s complement of –7.]

b)    01101   [The number is positive because leftmost bit is zero.  1101 is the binary representation of 13, 01101 is the two’s complement representation of 13.]

c)     10001  [The number is negative because leftmost bit is one.  Complement 0001 to get 1110 now add 0001 to get 1111 which is the binary representation of 15, 10001 is the two’s complement of –15.]

d)    11111   [The number is negative because leftmost bit is one.  Complement 1111 to get 0000 now add 0001 to get 0001 which is the binary representation of 1, 10001 is the two’s complement of –1.]

 

 

32) If m is a positive integer less than 2n-1, how is the one’s complement representation of –m obtained from the one’s complement of m, when bit strings of length n are used?

ANSWER:

Since the one’s complement of a positive integer is its binary representation, take the complement of the binary representation of m.  That is, every 1 in the binary representation of m becomes a 0, and every 0 becomes a 1.  This is the one’s complement of –m.

 

 

 

 

38) If m is a positive integer less than 2n-1, how is the two’s complement representation of –m obtained from the two’s complement of m, when bit strings of length n are used?

ANSWER:

Since the two’s complement of a positive integer is its binary representation, take the complement of the binary representation of m and add one to it.    This is the two’s complement of –m.

 

 

33) How is the one’s complement representation of the sum of two integers obtained from the one’s complement representations of these integers?

ANSWER:

Assume that n is large enough that the sum represents a number in the appropriate range.  In other words,  –2n-1  <  sum  <  2n-1.  Find the one’s complement representations of the integers that are to be added.  Next, add these numbers using binary addition.  If a one is carried on the left-most column drop the one in the 2nth position and add one to the sum.  This is the one’s complement representation of the sum.

 

 

39) How is the two’s complement representation of the sum of two integers obtained from the two’s complement representations of these integers?

ANSWER:

Assume that n is large enough that the sum represents a number in the appropriate range.  In other words,  –2n-1  £  sum  £  2n-1 –1. Find the two’s complement representations of the integers that are to be added.  Next, add these numbers using binary addition.  If a one is carried on the left-most column drop the one in the 2nth position and add one to the sum.  This is the two’s complement representation of the sum.

 

 

34) How is the one’s complement representation of the difference of two integers obtained from the one’s complement representations of these integers?

ANSWER:

To find a – b use the equation a – b = a + (-b).  Start with the one’s complement representations of a and b.  Use the result of (32) to find the one’s complement of –b from b.  Now use the result of (33) to find the one’s complement representation of the sum based on the one’s complement representations of a and –b.

 

 40) How is the two’s complement representation of the difference of two integers obtained from the two’s complement representations of these integers?

ANSWER:

To find a – b use the equation a – b = a + (-b).  Start with the two’s complement representations of a and b.  Use the result of (38) to find the two’s complement of –b from b.  Now use the result of (39) to find the two’s complement representation of the sum based on the two’s complement representations of a and –b.

 

EXAMPLES:

 

Use 8-bit representations to compute 39 + (-89).

ANSWER:

Convert 39 and –89 to their two’s complement representations.  Since

(39)10 = (100111)2, the two’s complement representation of 39 is 00100111.  Since (89)10 = (01011001)2 ,  the two’s complement representation of -89 is 10100110 + 00000001 = 10100111.  Add these representations in binary notation and drop the one in the 28th position if there is one, i.e.,

00100111 + 10100111 = 11001110.  Find the decimal equivalent of 11001110.  Since the leading bit is 1, the number is a negative integer.  Taking the complement 11001110 becomes 00110001.  Add one to get 00110001 + 00000001 = 00110010 which is   32+16+2 = 50.  So the answer is –50.

 

Use 8-bit representations to compute 39 + (-25).

ANSWER:

Convert 39 and –25 to their two’s complement representations.  Since

(39)10 = (100111)2, the two’s complement representation of 39 is 00100111.  Since (25)10 = (00011001)2 ,  the two’s complement representation of -25 is 11100110 + 00000001 = 11100111.  Add these representations in binary notation and drop the one in the 28th position if there is one, i.e.,

00100111 + 11100111 = 100001110.  Drop the 1 in the 28th position.  Find the decimal equivalent of 00001110.  Since the leading bit is 0, the number is a positive integer, (00001110)2 = (8+4+2)10 = 14.  So the answer is 14.

 

 

 

 

 

  Use 8-bit representations to compute (-25) + (-89).

ANSWER:

Convert -25 and –89 to their two’s complement representations.  Since

(25)10 = (00011001)2, the two’s complement representation of -25 is 11100110 + 00000001 = 11100111.  Since (89)10 = (01011001)2 ,  the two’s complement representation of -89 is 10100110 + 00000001 = 10100111.  Add these representations in binary notation and drop the one in the 28th position if there is one, i.e.,  11100111 + 10100111 =  110001110.  Drop the 1 in the 28th position. Find the decimal equivalent of 10001110.  Since the leading bit is 1, the number is a negative integer.  Taking the complement 10001110 becomes 01110001.  Add one to get 01110001 + 00000001 = 01110010 which is   64+32+16+2 = 114.  So the answer is –114.