Adding binary numbers (using logic)

As you see Derek has already made two posts about blender, so i thought i should also do something to brighten (or darken) your day. I will do more technical topics on this blog, so if you dont like tech and math you should skip my stuff.

I'd like to start with an explanation on how to add binary numbers. With this i dont mean just add pure numbers in your head, but i want to show you how the computer does it. Knowledge of binary numbers greatly helps understanding this post.

Binary numbers only have two numerals, 0 and 1. Here a picture to compare our normal decimal system with the binary system:

Here you see how our numbers are made up. Can you calculate what the binary number is? (spoiler: its 181). At this point i assume that you know how to add binary numbers (its the same as with decimal numbers. not that different). As we want to add binary numbers using logic, we treat 0 as 'false' and 1 as 'true'.
Now you may wonder how that is going to help us. Well there is such a thing called 'Boolean algebra' (http://en.wikipedia.org/wiki/Boolean_algebra). Its about how to work with the boolean values 'true' and 'false.
Now this formula stuff looks a bit complicated and is not that much fun, but there is something called logic gates. With these you can display complicated logical circuits. But before displaying stuff we need to know what to do.
We want to add binary numbers. As we only have 1 and 0 we can create some rules for what should happen when we add two of those bits.
Lets write it down in sentences, as a formula isn't going to make things easier. We have the input values X and Y and the output S (for Sum):
"If both X and Y is 0, S will be 0. If either X or Y is 1, S will be 1."
So far so good, but what happens if we add 1 and 1? We get the binary number 10, but we only have one output. Lets think about how we add numbers.
We use a carriage if the addition of two number results in a value that cant be displayed by one digit and add this carriage to the left. So to accomodate this, we add another input Cin and another output Cout. We now have to adjust our rules. As we have 3 inputs now we get a few more combinations:
"If X,Y and Cin are 0, S will be 0 and Cout will be 0"
"If either X,Y or Cin is 1, S will be 1 and Cout will be 0"
"If 2 of X,Y or Cin are 1, S will be 0 and Cout will be 1"
"If X,Y and Cin are 1, S will be 1 and Cout will be 1"
Now we have the theory, so lets start using some gates:

Lets start with the carriage output. Cout is 1 if X and Y are 1. This can be done using a AND gate. Its output will only be 1 if all of its inputs are 1. In this picture X is 0 and Y is 1, so as predicted by our rules, Cout is 0.
Now we need something to accomodate our other rules. Something that is only 1 if only one of its inputs is 1. Some people mightve guessed it: a XOR. A XOR is only 1 if exactly one of its inputs is 1.

As you see its output is 1 while only one of its inputs is 1. now we should combine these two:

I labeled the inputs and the outputs here. You see that when we add 1 with 0 we get 1 and no carriage. Which is what we wanted. What we have here is called a 'half adder' (http://de.wikipedia.org/wiki/Halbaddierer im giving you the german page here, because the english one has a super strange notation for the gates and you wouldnt understand my blogpost then). 'Half' because it does only half of what we need. We are missing something to process Cin. Well lets just use another half adder then.

Now we are processing our Cin too, but we have 3 outputs. Now lets remember our rules. If 2 or 3 of our inputs are 1, Cout must be 1. We dont have that many combinations here, so when we test them,
we will see that for each those combinations, at least one of the Couts is 1. So we need a gate that is 1 as soon as 1 or more of its inputs are 1. This would be an OR gate. Lets add this to both our Couts:

Now we have a so called 'full adder' which does everything we wanted. Now we can add 2 bits, but we wanted to add whole binary numbers. To do this we only have to chain our full adders:

Here you see a 4 bit adder (sorry its a mess. I dont have a proper algorithm to place the lines in my program. it just places them like this). X is 10 and Y is 11. When we add these we get 21, which does not fit in 4 bit so we get 5 as result for S. As you see i labeled the last Cout as 'Overflow'. It will always be 1 if the resulting number of the addition is too big to fit in 4 bits. 

And there we have it. Binary additions using pure logic.

This is only kinda how a computer does additions. The computer uses signed numbers using the 2s complement. So a overflow is detected a bit differently.

If you came this far your brain is probably melted. This may be because im bad at explaining stuff in english (which is not my mother language). So if you think you are missing some information to understand the topic, leave a comment and tell me what i forgot to explain!