Digital Logic & Gates

A logic gate is the smallest building block of a computer: a tiny circuit that takes one or two bits in and produces one bit out. Each gate is completely defined by its truth table — a list of the output for every possible input. Stack enough of them and you get an entire processor.

The core gates

1. 1AND — outputs 1 only when *all* inputs are 1.
2. 2OR — outputs 1 when *any* input is 1.
3. 3NOT — flips a single bit (the only one-input gate here).
4. 4XOR — outputs 1 when the inputs *differ*; the heart of the sum bit.
5. 5NAND / NOR — AND/OR followed by a NOT; both are universal.

The half adder — adding two bits

Add two single bits A and B and you get a sum and a possible carry. Two gates do it: Sum = A XOR B and Carry = A AND B. That is a half adder — "half" because it cannot accept a carry coming *in* from a previous column.

Half adder truth table:
  A  B | Sum  Carry
  0  0 |  0     0
  0  1 |  1     0
  1  0 |  1     0
  1  1 |  0     1     <- 1 + 1 = binary 10

  Sum   = A XOR B
  Carry = A AND B

The full adder — adding three bits

To add a column inside a real multi-bit number you need three inputs: A, B, and the carry-in from the column to the right. A full adder does this with Sum = A XOR B XOR Cin and Carry = (A AND B) OR (Cin AND (A XOR B)) — effectively two half adders plus an OR. This one cell, repeated once per bit, is exactly what a ripple-carry adder chains together.