Binary Arithmetic
Part of Boolean Logic and Gates
Binary arithmetic implements the four mathematical operations — addition, subtraction, multiplication, division — using only Boolean logic gates, connecting pure logic theory to functional calculation hardware.
Why This Matters
Boolean logic theory becomes useful hardware when applied to arithmetic. Addition, the most fundamental operation, is directly expressible as a Boolean equation: Sum = A XOR B XOR Cin; Carry = (A AND B) OR (Cin AND (A XOR B)). From this pair of equations, transistors perform actual addition.
This connection between Boolean algebra and arithmetic is the central insight that makes digital computers possible. Without it, logic gates would be interesting theoretical curiosities but not useful computational tools. With it, a circuit designer can derive an adder from Boolean axioms, then build it from transistors, creating a machine that correctly adds any pair of numbers.
Understanding this connection from the Boolean logic perspective (rather than the hardware perspective) reveals the mathematical elegance underlying computation and enables systematic design of arithmetic circuits from first principles.
Addition as Boolean Logic
Binary addition of single bits follows these truth conditions:
Sum is 1 when an odd number of the three inputs (A, B, Cin) are 1. “Odd number” is exactly the XOR function extended to three inputs: Sum = A XOR B XOR Cin
Carry-out is 1 when two or more inputs are 1 (majority function): Cout = (A AND B) OR (A AND Cin) OR (B AND Cin)
These Boolean equations are provably correct by truth table verification — all 8 input combinations produce the expected sum and carry.
The equations can be derived systematically using the Sum of Products (SOP) method:
- Write the truth table (8 rows for 3 inputs)
- Identify rows where output = 1
- Write a product term (AND of all inputs, negated where input = 0) for each such row
- OR all product terms together
- Simplify using Boolean algebra or Karnaugh map
For Sum, the 1-rows are: (001), (010), (100), (111) — four rows, yielding: Sum = Ā·B̄·Cin + Ā·B·C̄in + A·B̄·C̄in + A·B·Cin
Simplifying with Boolean algebra: = (Ā·B̄ + A·B)·Cin + (Ā·B + A·B̄)·C̄in = XNOR(A,B)·Cin + XOR(A,B)·C̄in = XOR(XOR(A,B), Cin) = A XOR B XOR Cin ✓
Subtraction from Boolean Logic
Subtraction A − B is derived by observing that in two’s complement, −B = NOT B + 1. Therefore: A − B = A + (NOT B) + 1
This converts subtraction to addition with these changes:
- Invert all bits of B (using NOT gates, or XOR each B bit with a control signal “SUB”)
- Force carry-in of the LSB adder stage to 1 (instead of 0 for addition)
The Boolean implementation: route each B input through an XOR gate with a second input connected to the “subtract” control signal (S):
- When S=0 (add): XOR(B_i, 0) = B_i (passes B unchanged)
- When S=1 (subtract): XOR(B_i, 1) = NOT B_i (inverts B)
Simultaneously, force Cin of the first adder stage to S. When S=1, Cin=1 provides the “+1” for two’s complement negation.
This adder-subtractor design adds zero hardware complexity beyond the adder: replace each B input with XOR(B_i, S), use S directly as the first-stage carry-in. One control signal switches between addition and subtraction.
Multiplication as Repeated Addition
Multiplication A × B reduces to a sum of shifted partial products. For each bit of B (from LSB to MSB), if that bit is 1, add A shifted left by the bit position; if 0, add zero.
Boolean implementation of partial product generation: partial_product_i = A × B_i. Since B_i is a single bit, this is an AND gate: partial_product_i[j] = A[j] AND B[i].
For 4-bit × 4-bit multiplication:
- 4 partial products (one per bit of B), each 4 bits wide
- Each partial product is A AND’d with one bit of B, then shifted
- Sum all 4 partial products using 3 adder layers
The resulting circuit: 16 AND gates (one per A-bit × B-bit combination) + 3 levels of 4-bit adders (or adder variants). Output is 8 bits (the product of two 4-bit numbers fits in 8 bits: max 15×15=225, which fits in 8 bits).
This is a combinational multiplier: no clocking, just gates. It produces the correct product after one propagation delay through all levels. The price is circuit size (much larger than an adder) and power (all gates switching on every operation).
Division and Comparison via Boolean Logic
Division is harder to express purely as Boolean logic because it is iterative: the algorithm makes repeated decisions, making it inherently sequential. Hardware dividers use repeated subtraction with decision logic — implementable as combinational logic with recurrence unrolled for a fixed number of iterations (combinational array divider), but the circuit is large.
For comparison (A < B? A = B? A > B?), Boolean logic provides efficient answers:
Equality: A = B when all corresponding bits are equal. For 4-bit values: Equal = (A[3] XNOR B[3]) AND (A[2] XNOR B[2]) AND (A[1] XNOR B[1]) AND (A[0] XNOR B[0])
Unsigned A < B: perform A − B; if carry_out = 0 (borrow occurred), A < B.
Signed A < B: perform A − B; check the N (negative) flag XOR V (overflow) flag — this handles two’s complement correctly for signed comparison.
The 74HC85 is a 4-bit magnitude comparator: given two 4-bit inputs, it outputs A>B, A=B, A<B simultaneously, with cascading inputs for chaining to wider values. One IC per 4 bits, cascaded for 8- or 16-bit comparison.
Boolean Logic and Floating Point
Floating-point arithmetic (real numbers stored as sign × mantissa × 2^exponent) also reduces to Boolean logic, but requires additional circuits for:
- Exponent comparison and alignment (to add mantissas of equal magnitude)
- Mantissa addition/subtraction
- Normalization (shifting result to fit mantissa representation)
- Round, guard, and sticky bits for accuracy
IEEE 754 floating-point hardware is significantly more complex than integer arithmetic, involving dozens of special cases (infinity, NaN, denormal numbers). For a first-generation hand-built computer, implement integer arithmetic completely before attempting floating point. Float can always be implemented in software using integer primitives.