Binary Addition
From CDS 130
Contents 
1. Objective
 To be able to do addition in binary.
2. Motivation
 Most scientific computations involve calculations made using the binary representation of numbers.
 Binary addition is the most fundamental calculation operation.
 Adding binary numbers requires the use of a very simple algorithm. Later in the semester, when you write computer programs, you will write algorithms to solve science problems.
3. Priming questions
 What is
37+79
? What algorithm did you use to arrive at an answer? That is, write down a detailed recipe for every step that you took.
4. Notes
4.1. Adding Decimal Numbers
The approach taken here is similar to that in Binary_Representation_of_Numbers:
 Break something easy (reading decimal numbers) down into step a stepbystep process.
 Apply the process to something that is seemingly not easy (translating a series of binary numbers to decimal).
Here we will:
 Break down adding decimal numbers into steps
 Follow same steps for adding binary numbers
4.2. Adding Decimal Numbers
It seems easy, but you are really following a long recipe when you do this.
2 3 6 5 8 + 4 1 2 4 8 _________
4.3. Adding Decimal Numbers
 Before you start, you need to know all possible sums (how many are there?) of two decimal numbers.
Table of all possible sums of decimal symbols 0, 1, ..., 9
0 + 0 = 0 0 + 1 = 1 0 + 2 = 2 . . . 1 + 0 = 1 1 + 1 = 2 . . . 9 + 9 = 18
4.4. Adding Decimal Numbers
The first step is:
 Add the numbers in the first column using the table of all possible sums.
 Is the sum one digit? If yes, write down the digit at the bottom of the first column.
 Is the sum two digits? If yes, write down the rightmost digit at the bottom of the first column and put the leftmost digit on the top of the column to the left of the first column.
 Add the numbers in the first column:
8+8 = 16
. Is the sum one digit?
No
.  Is the sum two digits?
Yes
.
 Is the sum one digit?
1 2 3 6 5 8 + 4 1 2 4 8 _________ 6
4.5. Adding Binary Numbers
 As with decimal numbers, we need a list of all possible sums of two binary numbers to refer to. What are they?
Table of all possible sums of binary symbols 0 and 1
0 + 0 = ? 0 + 1 = ? 1 + 0 = ? 1 + 1 = ?
4.6. Adding Binary Numbers
 What should I put in place of
?
. Hint:2
is not in the list of allowed symbols (only0
and1
are available)
0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = ?
4.7. Adding Binary Numbers
1 + 1 = ?
 Guess
01
... no. (Use table method to check)  Guess
10
... yes! (Use table method to check)
4.8. Example
 Add the numbers in the first column by using the table of all possible sums.
 Is the sum one digit? If yes, write down the digit at the bottom of the first column.
 Is the sum two digits? If yes, write down the rightmost digit at the bottom of the first column and put the leftmost digit of the sum on the top of the column to the left of the first column.
1 1 0 1 1 1 + 0 0 1 0 1 _________ 0
Because 1+1 = 10
in binary.
4.9. Example continued
 Use the same principles as adding two decimal numbers
 Add the two digits
 Carry the results to the next column
1 1 1 0 1 1 1 + 0 0 1 0 1 _________ 0 0
Because 1+1 = 10
in binary
4.10. Example continued
Y 1 1 0 1 1 0 + 0 0 1 1 1 _________ X 0 1
What are X
and Y
?
4.11. Example continued
1 1 1 0 1 1 0 + 0 0 1 1 1 _________ 1 0 1
What are X
and Y
?

X=1
andY=1
4.12. Example continued
 The answer is correct, but you may have noticed that we have not discussed how to handle the sum of three numbers.
 The recipe given earlier only mentions adding two numbers, not three!
 What is the recipe for adding three numbers?
The table of possible addition operations has only four choices. It does not show
1 + 1 + 1
Note 

When developing computer programs, you will encounter a situation similar to this quite often: The answer and recipe is obvious to you, but you need to break down the problem and "explain" it to a computer at a level of detail that you don't often think about. 
4.13. Example continued
Y 1 1 0 1 1 0 + 0 0 1 1 1 _________ X 0 1
The recipe is to break the sum of three numbers into a sum of two numbers:
1 1 1 0 (result of adding the top two 1s) + 1 => + 0 1 (bottom 1 with a leading zero added for clarity) __ _____ 1 1
This is why X=1
(right digit in sum) and Y=1
(left digit in sum).
4.14. Checking your answer
1 0 1 1 0 + 0 0 1 1 1 _________ 1 1 1 0 1
To check your answer, you can convert the binary numbers to decimal numbers and do the addition in decimal.
 The top row
10110 = 22
in decimal using the table method.  The second row
00111 = 7
in decimal using the table method. 
22 + 7 = 29
 The binary answer of
11101 = 29
using the table method.
5. Questions
5.1. Question
Y 1 1 1 0 1 1 0 + 0 0 1 1 1 _________ X 1 0 1
What are X
and Y
?
Answer 

0 1 1 1 0 1 1 0 + 0 0 1 1 1 _________ 1 1 0 1

5.2. Binary Addition I
1 0 0 0 1 1 0 1 1 0 1 + 1 1 1 0 0 1 1 0 1 1 1 _____________________
5.3. Binary Addition II
1 0 1 1 1 1 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 1 + 1 1 1 0 0 1 1 0 1 1 1 _____________________
5.4. Binary Addition III
0 1 1 0 1 + 1 0 0 1 1 ___________
Answer 

1 1 1 1 0 1 1 0 1 + 1 0 0 1 1 ___________ 1 0 0 0 0 0 To check your answer, convert the numbers in each row to decimal 0 1 1 0 1 => 13 + 1 0 0 1 1 => 19 ___________ + __ 1 0 0 0 0 0 => 32 
5.5. Base 3 Addition
 Write out the table of all possible sums of the symbols 0, 1, and 2.
 Use the table to complete the base3 addition:
0 1 2 + 0 2 0 ________
Answer  

0+0=0 1+0=1 0+1=1 1+1=2 2+1=10 (we can't write 3, so we put a 1 in the next column) 2+2=11 Note that we know 2+1 = 10 by following the same pattern that we used in decimal when we ran out of symbols: 9+1=10. We can also verify that 2+2=11 in base 3 using the table method (but instead of raising 2 to a power, raise 3).

5.6. Base 4 Addition
 Write out the table of all possible sums of the symbols 0, 1, 2, and 3.
 Use the table to complete the base4 addition:
0 3 3 + 0 2 0 ________
5.7. Base 2 Multiplication
 Create a table of all possible products of the symbols 0 and 1.
 Use the table to complete the base2 multiplication:
1 1 1 1 x ____
6. Activities
6.1. Extending the addition algorithm
Compute the following and write down any addition steps that you needed to add to the steps covered in the Notes. Check your answer using the method covered in the notes.
1 1 1 1 1 1 + 1 1 ____
Hints  

Adding a stack of three binary numbers was covered in the notes. This process can be extended to handle four binary number. The first column of four ones can be broken into two twodigit "stacks"
The next complication is on how to "carry" the
There are several ways to reason this out:

6.2. Binary Multiplication
What is this product? Use the second approach to check your answer.
1 1 1 1 x ____