Computer Science 161.01
Professor Valente
Wednesday September 11th
READING: Section 4.3 pp. 86-89.
How does a Computer
Do Addition of Two Integers?
The answer is very easily.
For now, we will learn only that it is done column-by-column, from right-to-left with carries.
We will also assume that the integers being added (operands) as well as the result of the addition are
all 8-bit twos complement integers, which is the best scheme for doing arithmetic.
This means that the two operands and the result all must be interpreted as integers in the range -128..+127.
This leads to rather interesting results as you can imagine!
Next week, we will learn how to construct a circuit that does addition.
The Rightmost Column:
What are the possibilities?
There are really only three different cases to worry about:
Two zeroes: 0 + 0 = 0, so record a 0 for the result bit.
A zero and a one: 0 + 1 = 1 + 0 = 1, so record a 1 for the result bit.
Two ones: 1 + 1 = 2. Oops, can’t write that for a bit.
But in binary 2 is 10 (using two bits) so the result bit is 0
and we’ll carry a 1 into the 2nd column from the right.
(This is what you do in base ten addition with say 7 + 3 in a column).
All Other Columns:
First, realize that there are 0, 1, 2, or 3 ones in a column, counting a carry in to the column.
Let’s handle these four cases.
No ones: The result bit is 0 and there is no carry.
One one: The result bit is 1 and there is no carry.
Two ones: The result bit is 0 and there is a carry of 1. (2 is 10 in binary)
Three ones: The result bit is 1 and there is a carry of 1. (3 is 11 in binary).
Let’s try this:
00010110
00110111
-------------
01001101 is your answer.
The first column is simply 0+1=1, no carry.
The second column is 1+1=2, so write down 0 and carry 1.
The third column now has three 1’s, so write down 1 and carry 1.
The fourth column has one 1 (the carry in) so write down 1, no carry.
… etc.
What you just did was illustrate how a computer would do 22+55 and arrive at 77.
All of these integers are represented by 8-bit Twos Complement integers.
How would a computer do 22 + -5?
Well, we need 8 bits for each:
22 = 16 + 4 + 2, so 22 is 00010110 as we saw before.
What about -5? Remember this is Twos Complement.
So, start with 5 = 4+1, which in binary is 00000101.
Now, for -5, invert the bits and “add 1” to the resulting pattern.
That is, 00000101 becomes 11111010, which becomes 11111011.
So, to do 22 + -5 like a computer would, we would do the following column-by-column:
00010110
11111011
------------
00010001
A whole lot of carrying goes on including a carry out of the final bit column.
But the answer 00010001 is 17, which is correct!
We should get the correct answer so long as we don’t overflow.
What does that mean?
That means that if the numbers sum to a number in the range -128..+127, we’ll be ok.
Overflow:
Try 77 + 55 bit-by-bit.
From before, 77 is 01001101 and 55 is 00110111.
Sum them column-by-column:
01001101
00110111
------------
10000100
A lot of carrying happens, but like the hardware,
I do what I am told and mechanically record the bits.
As soon I see the answer, I know it’s wrong.
Why? Because it’s negative as the left bit indicates.
Which negative integer is it?
Invert and “add 1” to find out:
10000100 inverted becomes 01111011;
then “add 1” yields 01111100.
Oh, great, the answer is interpreted as -124.
Is there a method to this madness?
Not surprisingly, there is.
We did a problem where we couldn’t accommodate the correct answer (132)
using 8 bits. The largest positive integer is 127, which is 01111111 in binary.
What if you do 01111111 + 1? What do you get? Yes, you get 10000000.
What is that? Did you say -128? Correct! So we “wrapped back around” to -128.
So consider -128..+127 on a number line, that’s what happens to “overflow”
-128------------------------+127
Anything that overflows the maximum value, namely +127, will wrap back
around to the left end of the number line.
In our example, 77 + 55 is 5 more than 127, so we count 5 beginning at -128,
and get -124. PHEW!
Practice addition (use the PLUS button) at this web site.
Be sure to enter only 8-bit binary patterns for A and B.