Two's Complement | ACCA4021

Overview

Computers store everything as patterns of 0s and 1s, including negative numbers. This worksheet shows how they do it using a method called two's complement. You will start with ordinary binary, see why the obvious way of storing a minus sign goes wrong, then learn to read, write, add and subtract 8-bit two's complement numbers. There is no programming in this worksheet. Work through it with a pen and paper, and use the interactive diagrams and the Check Answers buttons to test yourself as you go.

Learning Objectives

By the end of this lab you will be able to:

Explain why a computer needs a special method to store negative numbers
Convert between 8-bit two's complement binary and denary (ordinary base 10) numbers
Find the two's complement of a number using the flip and add 1 method
State the smallest and largest numbers an 8-bit two's complement number can hold
Add and subtract two's complement numbers and spot when overflow has happened

Concept

A computer stores every number as a pattern of bits, each one either 0 or 1. There is no extra symbol for a minus sign, so the computer needs an agreed way to store negative numbers using bits alone. The obvious idea, using the first bit as a plus or minus flag, causes real problems. It gives two different patterns for zero, and ordinary binary addition then produces wrong answers. Two's complement fixes both problems with one small change. In an 8-bit number the leftmost bit, called the most significant bit (MSB), is given a place value of -128 instead of +128. Every other column keeps its usual positive value. To read a two's complement number you add up the column values exactly as you would for ordinary binary, remembering that the first column counts as -128. If the MSB is 0 the number is zero or positive. If it is 1 the number is negative. To turn a positive number into its negative there is a simple two-step rule. Write the positive number in 8-bit binary, flip every bit (each 0 becomes 1 and each 1 becomes 0), then add 1. Because negatives are stored this way, a computer can subtract by adding a negative number, using the same adding circuit it already has. With 8 bits the numbers run from -128 up to +127. A result outside that range causes overflow, and the answer comes out wrong.

Tasks

Task 1 - Warm up with ordinary binary

Before looking at negative numbers, make sure ordinary 8-bit binary feels comfortable. Each column is worth double the column to its right.

128	64	32	16	8	4	2	1
0	0	1	0	1	1	0	1

To convert to denary, add up the column values that have a 1 under them. For 00101101 that is 32 + 8 + 4 + 1 = 45. To convert the other way, start at the left and ask "does this column fit into what is left?". For 37: 128, 64 and 32... 32 fits, leaving 5. Then 16 and 8 do not fit, 4 fits leaving 1, 2 does not fit, 1 fits. That gives 00100101.

00001010 in denary is

01000001 in denary is

11111111 in denary is

10000000 in denary is

23 in 8-bit binary is

100 in 8-bit binary is

Task 2 - Why not just use a sign bit?

A first idea for negative numbers is called sign and magnitude. The leftmost bit is used as a sign (0 for plus, 1 for minus) and the other seven bits hold the size of the number.

Number	Sign and magnitude
+5	`0 0000101`
-5	`1 0000101`
+0	`0 0000000`
-0	`1 0000000`

This looks sensible, but notice the last two rows. There are two different patterns for zero, which wastes a pattern and makes "is this zero?" harder to check. A bigger problem appears when you try to add. Here is +5 added to -5 using normal binary addition.

carry             1   1
          0 0 0 0 0 1 0 1    (+5)
        + 1 0 0 0 0 1 0 1    (-5)
        -----------------
          1 0 0 0 1 0 1 0

In sign and magnitude, 10001010 means -10. The answer should be 0. A computer using this method would need extra, more complicated circuits just to subtract correctly.

In 8-bit sign and magnitude, how many different bit patterns mean zero?

A. 1 B. 2 C. 8 D. 128

Both 00000000 (+0) and 10000000 (-0) mean zero.

What is the main reason computers do not use sign and magnitude for whole numbers?

A. It cannot store positive numbers B. It needs more than 8 bits C. Ordinary binary addition gives wrong answers with it D. It is too hard for people to read

Adding +5 and -5 with normal binary addition gave -10 instead of 0.

Task 3 - Meet the -128 column

Two's complement makes one change to ordinary binary. The leftmost column is worth -128 instead of +128.

-128	64	32	16	8	4	2	1

You read the number in exactly the same way as before, by adding up the columns that have a 1. The formula below says the same thing, where b₇ is the leftmost bit and b₀ is the rightmost.

\text{value} = -128\,b_7 + 64\,b_6 + 32\,b_5 + 16\,b_4 + 8\,b_3 + 4\,b_2 + 2\,b_1 + 1\,b_0

Worked example 1. 10000101

-128	64	32	16	8	4	2	1
1	0	0	0	0	1	0	1

-128 + 4 + 1 = -123

Worked example 2. 11111111

-128	64	32	16	8	4	2	1
1	1	1	1	1	1	1	1

-128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -128 + 127 = -1

Worked example 3. 01111111

The MSB is 0 so the -128 column adds nothing. 64 + 32 + 16 + 8 + 4 + 2 + 1 = 127. A number that starts with 0 reads exactly the same as ordinary binary.

Task 4 - Explore with the bit flipper

Click any bit below to switch it between 0 and 1. The diagram shows the sum of the columns, the value if you read the pattern as ordinary binary, and its two's complement value. The gold box is the MSB, worth -128.

Use it to answer these questions.

Make the largest number you can. What pattern is it, and what is its value?
Make the smallest (most negative) number you can. What pattern is it?
Find the pattern for -1.
Set any pattern that starts with 1. Is its two's complement value ever positive?
Compare the two's complement value with the ordinary binary value for a few patterns that start with 1. What is the difference between them every time?

Question 4 above. What can you say about every pattern whose first bit is 1?

It is always negative. The -128 column is bigger than all the other columns put together (64 + 32 + 16 + 8 + 4 + 2 + 1 = 127), so once -128 is included the total can never get back above zero.

Question 5 above. What is the difference between the ordinary binary value and the two's complement value for patterns starting with 1?

It is always 256. The MSB counts as +128 in ordinary binary and -128 in two's complement, a difference of 256. For example 11111111 is 255 as ordinary binary and -1 in two's complement.

Task 5 - Read two's complement numbers

Convert each 8-bit two's complement number into denary. Remember to include the minus sign for negative answers, for example -7.

Tip: check the MSB first. If it is 0, read the number as ordinary binary. If it is 1, start at -128 and add the other columns.

00010110 =

01100100 =

10000000 =

11111110 =

10010000 =

11000011 =

Task 6 - Making a negative number with flip and add 1

Reading two's complement is just adding columns. To write a negative number, use this rule.

Write the positive version of the number in 8-bit binary.
Flip every bit. Each 0 becomes 1 and each 1 becomes 0.
Add 1.

Worked example: -6

Write +6	`00000110`
Flip every bit	`11111001`
Add 1	`11111010`

Check it with the -128 column: -128 + 64 + 32 + 16 + 8 + 2 = -6.

Worked example: -20

Write +20	`00010100`
Flip every bit	`11101011`
Add 1	`11101100`

Check: -128 + 64 + 32 + 8 + 4 = -20.

The rule also works backwards. Flip and add 1 on a negative number and you get its positive version. That is a handy way to read a negative number if you prefer it to the -128 column.

Try it on the bit flipper below. It starts at +6. Press Flip every bit, then Add 1, and watch the value become -6. Press both buttons again to get back to +6.

Task 7 - Practise writing negative numbers

Write each number in 8-bit two's complement. Use flip and add 1, then check your answer with the -128 column before pressing Check Answers.

-1 =

-5 =

-12 =

-50 =

-100 =

-127 =

11110110 is the two's complement of which number?

10110101 is the two's complement of which number?

Task 8 - A quicker shortcut

Once flip and add 1 makes sense, there is a faster way to do it in your head.

Write the positive number in 8-bit binary.
Starting from the right, copy the bits down unchanged up to and including the first 1.
Flip every bit to the left of that 1.

Worked example: -20

Write +20	`00010 100`
Copy up to the first 1 from the right	`_____ 100`
Flip the rest	`11101 100`

This gives 11101100, the same answer as in Task 6.

The shortcut works because adding 1 to the flipped bits ripples a carry back through all the trailing 1s, turning them back into 0s, until it reaches the first 0, which becomes 1 again.

Use the shortcut. -24 =

Use the shortcut. -40 =

Use the shortcut. -96 =

Task 9 - How big can the numbers get?

With 8 bits there are 2⁸ = 256 different patterns. In ordinary binary they stand for 0 to 255. In two's complement half of them are used for negative numbers, so the range is shifted down.

The wheel below shows all 16 patterns of a 4-bit two's complement number, which is small enough to see all at once. Counting up means going clockwise. Look at what happens after +7.

For any number of bits n, the range of two's complement is given by this rule.

-2^{\,n-1} \;\le\; \text{value} \;\le\; 2^{\,n-1} - 1

For 8 bits that is -2⁷ = -128 up to 2⁷ - 1 = 127.

The smallest 4-bit two's complement number is and the largest is

The smallest 8-bit two's complement number is and the largest is

In 8-bit two's complement, -128 is written as and 127 is written as

The smallest 16-bit two's complement number is and the largest is

Why is there one more negative number than positive number in two's complement?

Half of the patterns start with 1 and are negative (-1 down to -128). The other half start with 0, but one of those is used for zero, leaving one fewer for the positive numbers (1 up to 127). Unlike sign and magnitude, zero only has one pattern.

Task 10 - Adding two's complement numbers

The big advantage of two's complement is that you add numbers with ordinary binary addition, whether they are positive or negative. The rules for each column are below.

Column sum	Write	Carry
0 + 0	0	0
0 + 1 or 1 + 0	1	0
1 + 1	0	1
1 + 1 + 1 (with a carry in)	1	1

Worked example: 7 + (-3)

carry   1 1 1 1 1 1 1 1
          0 0 0 0 0 1 1 1    (+7)
        + 1 1 1 1 1 1 0 1    (-3)
        -----------------
        1 0 0 0 0 0 1 0 0    = 4

A carry comes out of the left-hand end, making a ninth bit. The number is only 8 bits wide, so that carry is simply thrown away. The 8 bits that remain are 00000100, which is 4. Correct.

Now look back at Task 2. In two's complement, -5 is 11111011. Adding it to +5 gives this.

carry   1 1 1 1 1 1 1 1
          0 0 0 0 0 1 0 1    (+5)
        + 1 1 1 1 1 0 1 1    (-5)
        -----------------
        1 0 0 0 0 0 0 0 0    = 0

Throw away the carry and the answer is 0, as it should be.

Work out each sum in binary, then give the 8-bit answer.

00001100 + 00000101 = which is in denary

00001010 + 11111100 = which is in denary

11111000 + 11111010 = which is in denary

00000011 + 11110111 = which is in denary

Task 11 - Subtracting by adding a negative

A computer does not need a separate subtraction circuit. To work out a - b it finds -b using flip and add 1, then adds.

Worked example: 9 - 12

Rewrite it as 9 + (-12).
+12 is 00001100. Flip gives 11110011. Add 1 gives 11110100.
Add the two numbers.

carry                  
          0 0 0 0 1 0 0 1    (+9)
        + 1 1 1 1 0 1 0 0    (-12)
        -----------------
          1 1 1 1 1 1 0 1    = -3

There is no carry out this time. The answer 11111101 starts with 1 so it is negative. -128 + 64 + 32 + 16 + 8 + 4 + 1 = -3. Correct.

20 - 7. First write -7 in 8 bits:

Now add it to 20 (00010100). The 8-bit answer is which is in denary

5 - 9. First write -9 in 8 bits:

Now add it to 5 (00000101). The 8-bit answer is which is in denary

30 - 45. First write -45 in 8 bits:

Now add it to 30 (00011110). The 8-bit answer is which is in denary

Task 12 - Overflow

An 8-bit number cannot hold anything above 127 or below -128. If the true answer to a sum is outside that range, the result is wrong. This is called overflow.

Worked example: 100 + 50

carry     1 1          
          0 1 1 0 0 1 0 0    (+100)
        + 0 0 1 1 0 0 1 0    (+50)
        -----------------
          1 0 0 1 0 1 1 0    = -106

The true answer is 150, which is too big for 8 bits. The carry has run into the MSB, so the computer reads the result as -106. Two positive numbers have produced a negative answer. Look back at the number wheel in Task 9. Counting past the top of the range wraps round to the most negative numbers.

There is an easy way to spot overflow without working out the true answer.

Two positive numbers that give a negative answer have overflowed.
Two negative numbers that give a positive answer have overflowed.
Adding a positive and a negative number can never overflow.

Do not confuse overflow with the carry you threw away in Task 10. A carry out of the left-hand end is normal and does not mean the answer is wrong. Overflow is only about whether the sign of the answer makes sense.