Logic gates
Tap A, B and Carry in to flip each one between 0 and 1. First read what the four gates put out. Then follow the orange wires through the two circuits below: orange carries a 1, grey carries a 0. The circuits are built from the same gates, and they add. Here XOR is drawn as one ready-made gate, so the half adder shows 2 gates and the full adder 5. On the sheet each XOR is opened up into AND, OR and NOT, which makes the counts 4 and 9.
Mission. In the full adder, find every setting of A, B and Carry in that makes Carry out equal 1. Before you try all eight, guess the rule in plain words.
Answer
Carry out is 1 exactly when at least two of the three inputs are 1. That is four of the eight settings: 110, 101, 011 and 111. Two or three 1s add up to 2 or 3, which is 10 or 11 in binary, and the left digit is the carry.
Four gates
Half adder: A + B
Full adder: A + B + Carry in
What's going on
A gate is a tiny switch circuit with a fixed rule. AND gives 1 only when both inputs are 1. OR gives 1 when at least one is. XOR gives 1 when the inputs differ. NOT has one input and flips it.
Now add two one-digit binary numbers. 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10: write 0, carry 1. Look at the right-hand digit in those four sums. It is 1 when the inputs differ, which is XOR. The carry is 1 only for 1 + 1, which is AND. One XOR and one AND side by side make a half adder.
In a longer sum, each column also has a carry coming in from the column to its right, so it has three things to add. A full adder does that with two half adders and an OR. The first adds A and B. The second adds Carry in to that result. If either half adder produced a carry, the OR passes it on.
Chain 64 full adders, each one's Carry out feeding the next one's Carry in, and you have a circuit that adds 64-bit numbers. Real processors use a faster arrangement of the same gates.
Sheet: Adding with switches.