Let's Increment i, Logic Gate Style

Last week we looked at the assembly behind incrementing a value. Today, we'll step out of the software world and step into the low-level hardware world: logic gates. Specifically, we want to add two numbers using electricity.

The foundation for modern electronics is, of course, the transistor. Transistors work as a switch either allowing or blocking voltage from flowing through. By combining transistors and resistors in various configurations, you can build logic gates, which is what we'll be focusing on. There are three basic logic gates you are probably already familiar with: and, or and not.

Remember, we are in a world of digital circuits and thus are dealing exclusively with 1s and 0s. A not gate takes a single input. When that input is 1, the output is 0. When the input is 0, the output is 1. Both and and or gates take 2 inputs and have 1 ouput. The output of an and gate will only be 1 if both inputs are 1. The output of an or gate however, will be 1 if either inputs are 1. This visualization of some possible inputs and the resulting outputs for and and or gates should help:

There are a few other logic gates in addition to these three. The one which we are particularly interested in is the xor gate. The output of an xor gate will only be 1 if one, but not both, input is 1. This differs from an or gate which will have an output if either or both inputs are 1.

Before we can start playing with our logic gates, we need to know how to add binary numbers. Hopefully you already know a bit of binary. 0000 is 0, 0001 is 1, 0010 is 2, 0011 is 3, 0100 is 4, 0101 is 5, 0110 is 6 and 0111 is 7. Let's look at some basic examples and see what we can learn:

  0000   (0)
+ 0001   (1)
------------
  0001   (1)


  0001   (1)
+ 0001   (1)
------------
  0010   (2)


  0010   (2)
+ 0001   (1)
------------
  0011   (3)


  0011   (3)
+ 0001   (1)
------------
  0100   (4)

I'm not sure if you see it, but adding binary numbers is a lot like adding decimal numbers. When a column overflows beyond its maximum capacity, we carry over. In decimal, the maximum capacity of a column is 9. In binary, the maximum capacity is 1.

Here's the step by step process for adding 3 to 3. Hit the next button to go through it

    
  0011   (3)
+ 0011   (3)
------------
  

You might not see the pattern, but look at the above closely and consider it with respect to what we've learned about logic gates. On a per-column basis, we have two inputs and a single output. Forget about the carryover for a second. When the two inputs are 0, the output is 0. When either input is 1, the output is 1. When both inputs are 1, the output is 0. Remind you of anything? That's exactly how an xor gate behaves. What about that carry bit? Well, the only time we carry 1 is when both inputs are 1. That's an and gate.

Knowing this, to add two bits together, we need the following circuit (click on the checkboxes to verify the output!):

This is known as a half adder. Given two inputs, we get two outputs. The top gate, which is an xor, gives us the sum, while the bottom and gate gives us the carry value.

There's an obvious reason this is known as a half adder. If you go back to our sample binary addition, you'll notice that in order to add binary numbers, we actually need to support 3 inputs: the two values being added plus the carry value from the previous operation. For this, we use a full adder, which is actually two half adders with an additional or gate:

To add larger numbers, we just need to chain Cout into another adder's Cin.

And that, my dedicated reader, is how computers add numbers! Worth mentioning is that logic gates are used for much more than just basic arithmetics. Much like transistors serve as the building block for logic gates, logic gates themselves serve as the foundation for everything else: registers, memory, multiplexers and so on. When you hear about CPUs containing billions of transistors, that means that they contain hundreds of millions of logic gates.

Cool stuff?