## Binary Addition Algorithm

The rules for addition of binary are easy:

           0    0    1    1
          +0   +1   +0   +1
         ---  ---  ---  ---
          00   01   01   10

The above sums show two-bit results. The left-most bit is used for the CARRY into the next column. For example, here are two four-bit integers being added:

         0 1 1 0      <---- the carries
           0 1 1 0    <---- a number to add
           0 1 1 1    <---- another number
           -------
           1 1 0 1    <---- the result

Notice that there is a carry out of the left-most column. Computers (usually) add two N-bit integers together to produce an N-bit results. Every bit of the N-bit result must have a value. The following shows an 8-bit addition:

            0 0 0 0 1 1 0 0
              0 0 0 0 1 1 1 0
              0 0 0 0 0 1 0 1
              ---------------
              0 0 0 1 0 0 1 1

You should be aware of the values of all 8 bits of the result. On tests and homework you should show all 8 bits, even the leading zeros. This is unlike the usual paper-and-pencil arithmetic where only the number of columns needed are used.

The carry out from the left-most column might be one. The integer aritimetic hardware in the computer cannot make a new column for this carry. The result is still N-bits. (However a program can test if there was a non-zero carry and branch to additional instructions.)

The inputs to the algorithm are two N-bit patterns; the output is a single N-bit pattern and a carry. Both input patterns can be any pattern at all. The result pattern is defined for any inputs. (However if the inputs are regarded as positive integers, some output patterns don't correspond to the correct sum. This is called overflow. But even for overflow, the output pattern is defined.)

Use the calculator to practice this algorithm. Click on the bits of the two operands X and Y to toggle the bits from 0 to 1 and back. Click on "ADD" to perform the 8-bit algorithm. Click on "Single Step" to perform the algorithm one column at a time.

The source.