Logic Gates & Circuits

A logic gate is a tiny electronic circuit (made of transistors) that takes one or more bits as input and produces a bit as output. Billions of them inside a CPU perform every calculation your programs do.

#Truth tables

NOT has one input: NOT 0 = 1, NOT 1 = 0.

#Building circuits

Connect gates and you get a circuit for any Boolean expression. Explore one:

That expression, (A AND NOT B) OR (NOT A AND B), is exactly XOR.

#Adding binary numbers

Binary addition follows simple rules: 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 10 (0, carry 1), 1 + 1 + 1 = 11 (1, carry 1).

    1 0 1 1   (11)
  + 0 1 1 1   ( 7)
  ---------
  1 0 0 1 0   (18)

#Half adder

Adds two bits A and B:

• Sum = A XOR B
• Carry = A AND B

#Full adder

Adds two bits plus a carry in, so adders can be chained for multi-bit numbers:

• Sum = A XOR B XOR Cin
• Carry out = (A AND B) OR (Cin AND (A XOR B))

Chain 32 or 64 full adders, each passing its carry to the next, and you have the adder inside a CPU's ALU — a ripple-carry adder:

def full_adder(a, b, carry_in):
    s = a ^ b ^ carry_in
    carry_out = (a & b) | (carry_in & (a ^ b))
    return s, carry_out

def add_bits(x, y, width=8):
    carry, result = 0, 0
    for i in range(width):                       # from the least significant bit
        bit, carry = full_adder((x >> i) & 1, (y >> i) & 1, carry)
        result |= bit << i
    return result, carry

for x, y in [(11, 7), (100, 55), (200, 100)]:
    total, overflow = add_bits(x, y)
    print(f"{x:3} + {y:3} = {total:3}  (binary {x:08b} + {y:08b} = {total:08b}, carry out {overflow})")

 11 +   7 =  18  (binary 00001011 + 00000111 = 00010010, carry out 0)
100 +  55 = 155  (binary 01100100 + 00110111 = 10011011, carry out 0)
200 + 100 =  44  (binary 11001000 + 01100100 = 00101100, carry out 1)

The last line shows overflow: 300 does not fit in 8 bits, so the result wraps to 44 and the carry-out bit is 1.

#Beyond adders

• Multiplexers select one of several inputs (the hardware version of switch).
• Flip-flops use feedback between gates to remember a bit — the basis of registers and memory.
• Combining adders, multiplexers and flip-flops with a clock gives you a CPU.