Arithmetic
Turning logic into math: half and full adders that add bits, chained into a ripple-carry circuit that adds whole multi-bit binary numbers.
When logic starts to countThe moment gates do mathAdding two bits is just XOR for the sum and AND for the carry, the moment logic gates stop being abstract and start doing arithmetic.Half adderAdding two bitsA half adder adds two single bits and produces a Sum and a Carry. It is the first arithmetic circuit you build from the logic gates you already have.Full adderHow a computer really addsA full adder adds three bits, A, B, and a carry-in, producing a Sum and a carry-out. Chaining full adders in a row is exactly how a CPU adds multi-bit numbers.Carry-lookahead addersComputing every carry at onceA ripple-carry adder is slow because each bit waits for the carry below it. A carry-lookahead adder derives generate and propagate signals per bit, then computes every carry directly from the inputs in parallel, trading more gates for far less delay.Binary multiplicationShift, add, and the array multiplierBinary multiplication is longhand multiply with the easiest times table there is: each partial product is the multiplicand shifted, or zero. An array multiplier forms all the partial products with a grid of AND gates and sums them with an adder array.ComparatorsGreater, equal, or lessA comparator reports whether one number is greater than, equal to, or less than another. Equality is XNOR per bit ANDed together; magnitude resolves from the most significant bit down, the first differing bit deciding the order.Carry versus overflowTwo flags for two ways of reading the same bitsCarry-out means the unsigned result did not fit; overflow means the signed result did not fit. The same adder bits are read as one or the other depending on whether you meant the numbers as unsigned or signed.The barrel shifterShifting a word in one combinational stepA combinational shifter moves a word's bits left or right by a chosen amount in a single pass of logic. A barrel shifter does a variable shift with a tree of multiplexers, and the three flavors are logical shift (fill with 0), arithmetic shift (right-shift copies the sign bit), and rotate (bits wrap around).Binary divisionShift, subtract, and the quotientDivision is the fourth arithmetic operation and the hardest: hardware does it as long division in binary, shifting the divisor down the dividend and subtracting wherever it fits. Each step produces one quotient bit, and what is left over is the remainder.