Binary Addition

Let us consider first the problem of doing addition in decimal. Firstly we need to develop the decimal addition table:

  0 1 2 3 4 5 6 7 8 9
0000102030405060708 9
1010203040506070809 10
20203040506070809 10 11
303040506070809 10 11 12
4040506070809 10 11 12 13
50506070809 10 11 12 13 14
606070809 10 11 12 13 14 15
7070809 10 11 12 13 14 15 16
80809 10 11 12 13 14 15 16 17
909 10 11 12 13 14 15 16 17 18

Where in each square we have two parts:

Carry
Digit
Units
Digit
 

 

The algorithm for integer (whole number) addition is then:

  • Treat blanks as 0;
  • Arrange the two numbers to be added so that their lowest order digits are aligned one above the other;
  • Reserve a blank row above the two numbers (the carry row);
  • Reserve a blank row below the two numbers to receive the result:

    Carry
    Addend 1
    Addend 2
    Units

  • Starting from the rightmost column of digits, repeat:
    • Use the addition table to determine the "carry digit" and the "units digit";
    • Place the units digit in the result row below the two digits being added;
    • Place the carry digit in the carry row in the column to the left of the two digits being added;
  • Until all the columns of digits have been added together;
  • Repeat the same process again using the carry row of digits and the result row until the carry row is empty. [**]

For more help on arithmetic number tables and arithmetic in various bases click here.


** What is the complexity of this algorithm?

[TOC][Next]


Last updated 2002/02/05
© J.A.N. Lee, 2000-2002.