Computer Science 161.01

Professor Valente

Monday September 9^th

The Twos Complement Method for Representing Integers

You have now learned two different methods to represent both positive and negative integers.

Each has deficiencies, but the Ones Complement method shows promise by at least being close to correct

in arithmetic problems. But whereas close may be good in horseshoes, computers better be exact with arithmetic.

The Ones Complement method was really “1 off” from being correct in the addition problem we tried.

We will now learn that the Twos Complement method will make up this deficiency.

It will also correct other problems that the other methods had:

no longer will there be two representations for zero,

and thus we will now represent 256 different integers with 8 bits, not 255.

Here’s how it works.

To represent a positive decimal integer, like 38, just do as before with other methods.

Since 38 is 32 + 4 + 2, we can write it down in binary as 00100110.

So its 8-bit representation is the same regardless of the representation method we use.

But how about -38?

We’ll start as we did with ones complement, by inverting the bits.

Thus 00100110 (from 38) becomes 11011001.

Now, since we are really “1 off” from being correct, I’ll “add 1” to this pattern.

For the pattern 11011001, “adding 1” causes it to become 11011010.

Note that the rightmost 1 flipped over to 0, and the 0 just before it becomes 1.

The pattern for -38 is thus 11011010.

(If you add this pattern to the pattern for 38, you’ll be happy to see that you get 00000000!

We’ll talk more next week about arithmetic on a computer).

Now, if you start with 11011010, how do you get -38 from that?

As with ones complement, the left bit 1 indicates that I should get a negative.

So there’s work to be done.

We’ll invert all the bits, giving us 00100101.

Then we’ll “add 1” to this pattern, giving us 00100110.

We’ll see that this leaves us with 38.

So the original pattern represented -38.

At this point, you may find the “add 1” to the pattern a bit unclear.

That’s not surprising, since you need a precise algorithm for it.

ALGORITHM FOR “ADDING 1” TO A BINARY PATTERN:

Step 1: Begin at rightmost bit position.

Step 2: If the bit is 0, change it to 1 and STOP.

Step 3: If the bit is 1, change it to 0.

Step 4: Move left one position and go back to Step 2.

In summary, any trailing sequence of 1’s becomes all 0’s,

and the rightmost 0 in the original pattern becomes 1.

ALGORITHM FOR DECIMAL TO 8-BIT TWOS COMPLEMENT:

Step 1: If the decimal number is zero or positive,

write the binary as you did for unsigned and STOP.

Step 2: If the decimal number is negative (e.g. -38)

write the 8-bits for the positive value (e.g. 38) as you did for unsigned.

Step 3: Invert all the bits in the pattern from Step 2.

Step 4: Use above algorithm to “add 1” to the pattern from Step 3.

Step 5: STOP.

Example 1: Convert +24 to an 8-bit twos complement integer.

Step 1: 24 is 16+8, so as always it is 00011000. That’s my answer!

Example 2: Convert -9 to an 8-bit twos complement integer.

Step 1: skipped, because I have a negative.

Step 2: I’ll remember that +9 is 00001001 because 9 = 8+1.

Step 3: Inverting gives me 11110110.

Step 4: “Add 1” to 11110110 yields 11110111. I’m DONE.

ALGORITHM FOR 8-BIT TWOS COMPLEMENT TO DECIMAL:

Step 1: If leftmost bit is 0, convert to decimal as you did for unsigned and STOP.

Step 2: Since leftmost bit is 1, follow steps 3, 4, and 5:

Step 3: Invert all bits.

Step 4: “Add 1” to the pattern resulting from Step 3.

Step 5: Compute the decimal integer associated with pattern from Step 4.

Your answer is the negative of this decimal integer.

Example 3: Convert 01010110 to a twos complement decimal integer.

Step 1: The leftmost bit is 0, so this is a positive, and it is 64+16+4+2 = 86. DONE.

Example 4: Convert 11101000 to a twos complement decimal integer.

Step 1: Oh boy, the leftmost bit is 1, there is work to do.

Step 3: Inverting the bits gets me 00010111.

Step 4: “Adding 1” gives me 00011000. (Note how the 0111 “rippled over” to 1000).

Step 5: The pattern 00011000 is that of 24.

So my answer is that the original pattern represented -24.

You’ll need practice.

Please use this site yet again, this time selecting Twos Complement at the top.

Here’s an interesting question: what does 11111111 represent in Twos Complement?

Work with that a bit, and go to the site to verify.

IS THE TWOS COMPLEMENT METHOD A GOOD ONE FOR COMPUTERS TO USE?

You bet it is!

As we will discover next week, the arithmetic works out beautifully.

We also want to note something else.

Recall that “negating” using this method has us invert and “add 1”.

Try that with 00000000. What did you get?

If you got 00000000 back, this is good news!

If we negate the pattern for zero, we don’t get a second pattern

as we did with those other methods.

So the 8 bits give us 256 different patterns represent 256 different integers.

How nice. But what’s the range of integers? There must be a new one somewhere.

The largest positive integer is clearly 01111111, which is +127.

Of course, then -127 is 10000001. I got that by inverting and adding 1.

So, what, then, does the pattern 10000000 represent?

Is he the negative of some positive number we can represent?

NO. (Just try inverting and adding 1!).

But he is 1 less than 10000001, which was -127.

So let’s make the pattern 10000000 represent -128!

That will work beautifully for arithmetic, and give us a number we couldn’t represent until now.

PRACTICE makes perfect… or something close to it.