Binary Addition

From CDS 130

Jump to: navigation, search

Binary Addition

Contents

  1. Objective
  2. Motivation
  3. Priming questions
  4. Notes
    1. Adding Decimal Numbers
    2. Adding Decimal Numbers
    3. Adding Decimal Numbers
    4. Adding Decimal Numbers
    5. Adding Binary Numbers
    6. Adding Binary Numbers
    7. Adding Binary Numbers
    8. Example
    9. Example continued
    10. Example continued
    11. Example continued
    12. Example continued
    13. Example continued
    14. Checking your answer
  5. Questions
    1. Question
    2. Binary Addition I
    3. Binary Addition II
    4. Binary Addition III
    5. Base 3 Addition
    6. Base 4 Addition
    7. Base 2 Multiplication
  6. Activities
    1. Extending the addition algorithm
    2. Binary Multiplication
  7. Resources

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 step-by-step 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 right-most digit at the bottom of the first column and put the left-most 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.
        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 (only 0 and 1 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 right-most digit at the bottom of the first column and put the left-most 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 and Y=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

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?


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
    ___________

5.5. Base 3 Addition

  1. Write out the table of all possible sums of the symbols 0, 1, and 2.
  2. Use the table to complete the base-3 addition:
   0 1 2
 + 0 2 0
 ________

5.6. Base 4 Addition

  1. Write out the table of all possible sums of the symbols 0, 1, 2, and 3.
  2. Use the table to complete the base-4 addition:
   0 3 3
 + 0 2 0
 ________

5.7. Base 2 Multiplication

  1. Create a table of all possible products of the symbols 0 and 1.
  2. Use the table to complete the base-2 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
  ____

6.2. Binary Multiplication

What is this product? Use the second approach to check your answer.

   1  1
   1  1
 x ____

7. Resources

  • "A study of mathematical concepts for the elementary education major using tactile models and appropriate technology" [1]
  • Using a template-like method to determine if a credit card number is valid [2].
Personal tools