What is binary addition?

We learned how to represent numbers as a sequence of on or off bits. If not, check it out.

Addition is an important operation and also quite simple. If we place two blocks next to each other, how wide will the resulting block be? One way is to place them next to each other and see the total width. What is the total width of the combined block of black and brown?

Width =

What we really want is a way to determine the sum based on the binary representations of two numbers. So first, what are the widths of each block?

Width =
Width =

Hopefully, you figured out that the sum we want is +.

Width =

You should note that this sum is really just a matter of rearranging the blocks. And changing the order of the blocks does not change the width, so we can rearrange blocks as needed to make the addition easier.

Let's try to determine an algorithm to perform addition without needing to check which arrangement of blocks fits exactly. However, whatever algorithm we create should match the answer generated from measuring the width of the combined block.

Start with the simplest cases. What are +, +, +, and +?

Gray means off so there is no width, so + and + will both simply be . And + = . The more complicated question is the sum of two of the same blocks. The combined width will be twice as wide so the answer is .

Any definition of addition should match the result that is generated by measuring the combined widths, but we want to automate the process so that a computer can use on and off. If you add one of the smallest blocks to nothing then the result will be one of the smallest blocks. So red + gray = red. In fact, gray is the additive identity. No matter what we add to gray, the result does not change. What is red + red? Remember we are only allowed to use each small block at most one time. So combining two blocks of the same size requires the use of the a larger block. In the case of red + red, the next sized block is exactly twice the size so red + red = redgray. We could just keep computing additions and tell the computer all of the answers, but there are way too many possibilities. So we should come up with an algorithm. Using widths of blocks, it should be clear that rearranging the blocks will not change the total width. Instead of using the entire red block and the entire blue block we will arrange them by size. So redgray + blueblue becomes blueredblue. We will work left to right. We need one small purple block to match the one small blue block. Then to match the larger red and blue blocks we use one purple block of the larger size. Treat red and blue blocks of the same size as a pair that should be worked together. If there are two of the same size, add a purple block of the next size. If there is one of a size, then check if there is already a purple block of that size. If so, turn that purple block into a larger purple block. If not, add a purple block of that size. When you are finished, you will have exactly matched the total width without reusing any of the small blocks. And then convert that to binary. A computer can use circuits and a similar type of algorithm to add any two binary numbers very quickly. Multiplication is more difficult, but can be achieved by repeated addition. What about decimals? Not every block will have width that is an exact multiple of the smallest block in our set. If we try to determine the width of such a block then we will reach a point where every block in the set is wider than the remaining width. In order to exactly match the width, we start adding smaller blocks to our set. Each new block will be half the width of the previous block. We keep adding the largest possible block that fits and recording it after the decimal point. If we get tired of adding new blocks we can stop and use the representation as an approximation. Since we are still using the same of idea of blocks of increasing size, addition is the same but we need to keep the decimals aligned to ensure that we are comparing blocks of the same size.