How does binary addition work?

Problem Detail: 

I find binary confusing. I have watched minecraft redstone videos on binary adders, real binary adders, diagrams, etc and yet I have not learned much at all. How does electrons flowing through wires made of gold "add/subtract" to make numbers through some logic gates?!

Asked By : Link TheProgrammer

Answered By : alvonellos

It's like magic, isn't it?

Here's a visual depiction for you, and hopefully it will make it easier for you to understand. This circuit is something called a half-adder; a half-adder is a special kind of adder -- the most base level kind of adder -- that takes two values, A and B which are the addend and auged respectively, and outputs them into the sum. If the addend and augend overflow, then the overflow is placed into a special output called $C_{out}$, which means "carry out."

Well, to chain these together, we need to take two half adders and put them together in order to construct something called a full-adder. What makes a full-adder special is that it takes another input, $C_{in}$ as well as the addend and augend, and performs an addition on all three of those bits. Here, the half adder I described above has been put into a "black box" kind of configuration, where the visible details of the circuit are hidden, and the inputs and outputs are provided instead. Notice, just like the half-adder, we have a sum and a $C_{out}$ too.

Well, to construct bigger adders, such as four bit adders, we need to chain those full-adders together, and this is when the pattern becomes even more obvious:

And to construct an 8 bit adder, you put two four bit adders together. To construct a 16 bit adder, you put two eight bit adders together. To construct a ... well, you get the point.

---

So, what's all the 1 and 0 nonsense that I'm hearing about? (Read: how in the heck did someone come up with all of this).

Easy. We have things called "logic gates" which are represented by a couple of symbols to start with, but the simplest way to explain it is in the form of something called a truth table, but what these "True" and "False" values really represent is 1 for true and 0 for false -- but don't worry about that, yet. The first two columns: p|q are a set of truth values that are then evaluated for the other columns. Where $p\wedge q$ represent $p$ and $q$, $p\vee q$ represent $p$ or $q$, and the last column represents $p$ xor $q$

The last operator, xor is a special operator. It is the english equivalent of "I either __ or __" and the implication is that both cannot happen at the same time.

So when we're connecting these in relation to the individual circuit symbols, you can check those out here.

Putting these all together, with the special truth tables that I've shown you, you can clearly see that in the case of the half adder, walking through a set of logic values you can determine what these propositions mean in terms of those two binary truth values.

So, what's all this mean in terms of our base? Our system of counting? Well, as you may know, it is possible to convert a number of an arbitrary base (ours is 10) to another arbitrary base (in the case of the circuit, it is base two). There are many ways to do that, one of which is by using wolfram alpha; however, the manual way is fun too, if you want to learn how.

Let's count:

0 0000

1 0001

2 0010

3 0011

4 0100

5 0101

6 0110

7 0111

8 1000

9 1001

10 1010

11 1011

12 1100

13 1101

14 1110

15 1111

16 10000 <-- Rollover

The set of numbers on the right are binary numbers. The numbers on the left are numbers in our base, base 10. If you'll notice, the far right column, ex. 000[0], is the 'ones' column. This represents one one. The second column, ex. 00[0]0, is the 'twos' column. The third column, ex. 0[0]00, is the fours column. The fourth column [0]000 is the 'eights' column. Notice how the power values are, increasing in powers of two. Make more sense now?

So what makes these circuits work? Consider the half-adder. Those inputs a and b represent some arbitrary value coming from the outside. The first portion of the half adder is a xor gate. Look in the table for what happens when two true values are applied (1's), the output is 0. Therefore the sum is zero. Now consider the and gate, what happens when two true values are applied to the and gate? the output is one. So, we derive the sum from the output of the xor gate (which is 0), and we derive the $C_{out}$ from the and gate which is (1) if A and B are both (1).

---

Edit: More Circuits

I've added these and I've also made YouTube video of them working, just as I promised.

---

---

Videos:

If I get another request, I'll make another video and upload it, showing the internals of what it REALLY looks like as the circuit is going through its cycles.

Here are some adders

Here is a demonstration of the gates

---

Make more sense now?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22413