Logic Gates

A logic gate is a tiny rule that takes one or two bits in and gives exactly one bit out. Wire enough of them together and you get adders, memory and, in the end, a whole processor.

Why everything comes down to 0 and 1

Inside a chip, a bit is a voltage on a wire: low means 0, high means 1. Two levels are easy to tell apart even when the signal is a little noisy, which is why computers count in binary rather than in ten levels of voltage.

A gate is a small circuit, built from a handful of transistors, that reads the voltage on its input wires and sets the voltage on its output wire. It has no memory and no clock of its own. Change an input and the output follows a moment later.

Each gate is described by a truth table: every possible combination of inputs, and the output for each one. With two inputs there are only four rows, so you can learn a gate by learning its table.

The three basic gates

AND

AND outputs 1 only when both inputs are 1. A single 0 on either input makes the output 0.

Think of a door that needs a key card and a PIN. Either one alone gets you nowhere.

OR

OR outputs 1 when at least one input is 1. The only way to get a 0 out is to put 0 in on both sides.

Note the last row. Logical OR is 'inclusive': both inputs being 1 still counts. That differs from everyday English, where 'tea or coffee?' usually means one or the other.

NOT

NOT has a single input and flips it: 1 becomes 0, 0 becomes 1. It is also called an inverter. On its own it looks trivial, but put one on the output of AND or OR and you get two new gates.

XOR, NAND and NOR

XOR: the odd one out

XOR (exclusive OR) outputs 1 only when its inputs are different. Matching inputs, both 0 or both 1, give 0.

That makes XOR a 'not equal' test for single bits. It is also the everyday sense of 'or': one or the other, but not both. Chain XORs across many bits and the result is 1 when an odd number of them are 1, which is how simple parity checks catch a flipped bit in transmitted data.

NAND and NOR: the flipped versions

NAND is AND with a NOT on its output. Where AND gives 1, NAND gives 0, so NAND outputs 0 only when both inputs are 1.

NOR is OR with a NOT on its output. It outputs 1 only when both inputs are 0.

Here are the three pairs side by side:

XNOR, the flipped XOR, outputs 1 when the inputs match. It wasn't in the video, but you will meet it in the same tables.

Why NAND matters so much

NAND and NOR are each universal: you can build every other gate from NAND gates alone, or from NOR gates alone. Wire both inputs of a NAND to the same signal and you get NOT. Put a NOT after a NAND and you get AND. With a few more you get OR and XOR.

It matters in hardware too. In CMOS, the technology most chips use, NAND and NOR are cheaper to make than AND and OR, which are usually built as a NAND or NOR followed by an inverter.

From gates to arithmetic

Gates become useful when you wire them together. The classic first example is adding two single bits.

Adding two bits gives four cases: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10 in binary (two). The answer needs two output bits: a sum bit and a carry bit.

Look at the two output bits. The sum bit is 1 when exactly one input is 1: that is XOR. The carry bit is 1 only when both inputs are 1: that is AND. So one XOR and one AND, sharing the same two inputs, make a half adder:

Feed it 1 and 1: XOR gives 0, AND gives 1. Read as carry then sum, that is 10, which is two in binary.

A half adder can't take a carry coming in from the column to its right. Join two half adders with an OR gate and you get a full adder, which can. Line up 64 full adders, each passing its carry to the next, and you can add two 64-bit numbers. Real CPUs use faster arrangements that work out the carries in advance, but they are still made of the same gates.

Memory works the same way. Cross two NOR gates so each one's output feeds the other's input and you get a latch: a circuit that holds on to a 1 or a 0 after the input that set it has gone. Registers and caches are built from that idea, scaled up.

The same gates in your code

Most languages expose gates as bitwise operators, which apply a gate to every bit position of two numbers at once. In Python and JavaScript, & is AND, | is OR, ^ is XOR and ~ is NOT.

a, b = 6, 3        # 110 and 011 in binary
 
print(a & b)       # 2  (010)
print(a | b)       # 7  (111)
print(a ^ b)       # 5  (101)

The half adder is two lines:

def half_adder(a, b):
    return a ^ b, a & b  # (sum, carry)
 
print(half_adder(1, 1))  # (0, 1)

And a full truth table for every two-input gate fits in a loop:

gates = {
    "AND":  lambda a, b: a & b,
    "OR":   lambda a, b: a | b,
    "XOR":  lambda a, b: a ^ b,
    "NAND": lambda a, b: 1 - (a & b),
    "NOR":  lambda a, b: 1 - (a | b),
}
 
for a in (0, 1):
    for b in (0, 1):
        row = [f"{n}={g(a, b)}" for n, g in gates.items()]
        print(a, b, *row)

The first line it prints is 0 0 AND=0 OR=0 XOR=0 NAND=1 NOR=1.

Common mistakes

• 'One or the other, but not both' describes XOR. OR is still 1 when both inputs are 1.
• NAND means NOT applied to the result of AND. If you flip both inputs and then AND them, you get NOR instead. This is De Morgan's law: NOT (A AND B) equals (NOT A) OR (NOT B).
• ~ is a poor way to flip a single bit. In Python, ~1 is -2, because ~ flips every bit of the whole integer, sign included. For one bit, use 1 - a or a ^ 1; for a boolean, use not.
• Bitwise and logical operators are easy to mix up. & and | work on every bit and always evaluate both sides. and/or in Python, or &&/|| in JavaScript, work on whole truth values and stop early once the answer is known.

Key takeaways

• A logic gate takes one or two bits and outputs one bit, following a fixed rule you can write as a truth table.
• AND needs both inputs to be 1, OR needs at least one, NOT flips its input, and XOR needs the inputs to differ.
• NAND and NOR are AND and OR with the output flipped, and either one alone can build every other gate.
• An XOR and an AND make a half adder; chained adders, latches and the rest of a CPU are gates wired together.
• In code, &, |, ^ and ~ are the same gates applied to every bit of a number.