Binary Arithmetic and Adders

Introduction

Every calculation your computer performs—from rendering graphics to running AI models—ultimately comes down to binary addition. Whether you're calculating 2 + 2 or training a neural network, it all reduces to billions of binary additions happening in the processor's ALU (Arithmetic Logic Unit).

Binary arithmetic is the foundation of all digital computation. In this lesson, we'll learn:

• How binary addition works
• How to build adder circuits from logic gates
• Half adders and full adders
• Ripple carry and fast adders
• Subtraction using two's complement
• Binary multiplication basics

The Heart of Computing

The humble adder circuit is arguably the most important circuit in computing. Everything from your smartphone to supercomputers relies on fast, accurate binary addition. Master this, and you understand the core of digital arithmetic!

Binary Number System Review

Binary Representation

Binary uses only two digits: 0 and 1.

Place Values:

Position:  7    6    5    4    3    2    1    0
Value:   128   64   32   16    8    4    2    1
         2⁷   2⁶   2⁵   2⁴   2³   2²   2¹   2⁰

Example: 10110110₂

= 1×128 + 0×64 + 1×32 + 1×16 + 0×8 + 1×4 + 1×2 + 0×1
= 128 + 32 + 16 + 4 + 2
= 182₁₀

Binary Addition Rules

Binary addition follows simple rules (like decimal, but simpler!):

A	B	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Key Points:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 10₂ (0 with carry 1)

Example: Adding Two 4-Bit Numbers

  Carries:   ¹ ¹ ¹      
             1 0 1 1  (11₁₀)
           + 0 1 1 0  (6₁₀)
           ---------
           1 0 0 0 1  (17₁₀) ✓

Step-by-step:

1. Rightmost: 1 + 0 = 1, carry 0
2. Next: 1 + 1 = 0, carry 1
3. Next: 0 + 1 + (carry 1) = 0, carry 1
4. Leftmost: 1 + 0 + (carry 1) = 0, carry 1
5. Final carry: 1 (becomes MSB of result)

Carries Propagate

Notice how carries "ripple" from right to left, just like in decimal arithmetic. This rippling is key to understanding adder circuits!

Half Adder

The Simplest Adder

A half adder adds two 1-bit binary numbers. It produces a sum and a carry output but cannot accept a carry input.

Inputs: A, B (two bits to add)
Outputs: Sum (S), Carry (C)

Truth Table:

A	B	Sum (S)	Carry (C)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Boolean Expressions:

$$\begin{align*} \text{Sum (S)} &= A \oplus B \\ \text{Carry (C)} &= A \cdot B \end{align*}$$

Observations:

• Sum is XOR: different inputs produce 1
• Carry is AND: both inputs must be 1

Half Adder Circuit

note

Half Adder circuit diagram to be added

Simple Implementation:

• 1 XOR gate
• 1 AND gate
• Only 2 gates needed!

Half Adder Symbol

note

Half Adder block diagram to be added

Limitation of Half Adder

Problem: Cannot handle carry input from previous stage!

Example: Adding middle bits
  1 0 1 1
+ 0 1 1 0
---------
  
Need to add: 0 + 1 + carry(1 from previous)
Half adder can't do this! ✗

Solution: Full Adder

Full Adder

Complete 1-Bit Adder

A full adder adds three 1-bit numbers: two significant bits (A, B) plus a carry input (Cin). It's called "full" because it can handle carries from previous stages.

Inputs: A, B, Cin (carry in)
Outputs: Sum (S), Cout (carry out)

Truth Table:

A	B	Cin	Sum (S)	Cout
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Boolean Expressions:

$$\begin{aligned} \text{Sum } (S) &= A \oplus B \oplus C_{in} \\ \text{Carry } (C_{out}) &= (A \cdot B) + \big(C_{in} \cdot (A \oplus B)\big) \end{aligned}$$

Alternative form for carry:

$$C_{out} = A \cdot B + C_{in} \cdot A + C_{in} \cdot B$$

Interpretation:

• Sum: XOR of all three inputs (odd number of 1s → Sum=1)
• Carry: Generated when at least two inputs are 1

Full Adder Using Half Adders

Clever Design: Build full adder from two half adders!

note

Full Adder circuit diagram to be added

Logic Flow:

1. First HA adds A and B → partial sum and carry
2. Second HA adds partial sum and Cin → final sum and second carry
3. OR gate combines both carries → final carry out

Gate Count:

• 2 XOR gates (from 2 half adders)
• 2 AND gates (from 2 half adders)
• 1 OR gate
• Total: 5 gates

Full Adder Direct Implementation

Alternative: Build from basic gates directly.

note

Full Adder implementation diagram to be added

Full Adder Symbol

note

Full Adder block diagram to be added

Multi-Bit Adders

4-Bit Ripple Carry Adder

To add multi-bit numbers, cascade full adders. The carry "ripples" through each stage.

note

4-Bit Ripple Carry Adder circuit to be added

Operation:

1. FA0 adds LSBs (A0 + B0), produces S0 and C0
2. C0 ripples to FA1 as carry input
3. FA1 adds A1 + B1 + C0, produces S1 and C1
4. Process continues through all bits
5. Final carry C3 indicates overflow (if adding unsigned) or sign issues (if signed)

Example: 1011 + 0110

  Stage:    FA3   FA2   FA1   FA0
            A3B3  A2B2  A1B1  A0B0
            1 0   0 1   1 1   1 0
  Carry in: C2    C1    C0    0
            1     1     1     -
  ---------------------------------
  Sum:      0     0     0     1
  Carry out:C3    C2    C1    C0
            1     1     1     1

Result: 10001₂ (17₁₀) ✓

Propagation Delay in Ripple Carry Adder

Major Limitation: Carry must ripple through all stages!

Total Delay:

$$t_{total} = n \times t_{FA}$$

Where:

• n = number of bits
• t_FA = propagation delay per full adder

Example:

• 32-bit adder
• Each FA has 10ns delay
• Total delay = 32 × 10ns = 320ns
• Maximum frequency ≈ 3 MHz

note

Ripple Carry Adder timing diagram to be added

Speed Bottleneck

The ripple carry adder is slow for large bit widths because of accumulated delay. For modern processors (64-bit), this is unacceptable. Solution: Fast adders!

Commercial Adder ICs

IC	Type	Bits	Features
74HC283	Ripple	4	Fast carry, widely used
74HC83	Ripple	4	Standard 4-bit adder
74LS181	ALU	4	Full ALU with add/subtract/logic
74LS682	Comparator	8	8-bit magnitude comparator

Fast Adders

The Need for Speed

For large bit widths, we need faster addition. Several techniques exist:

Types of Fast Adders:

1. Carry Look-Ahead (CLA) - Most common
2. Carry Select
3. Carry Skip
4. Carry Save

Carry Look-Ahead Adder (CLA)

Key Idea: Calculate all carries simultaneously instead of waiting for ripple!

Carry Generation and Propagation:

For each bit position i:

• Generate (Gi): Position generates a carry regardless of Cin
• Propagate (Pi): Position propagates Cin to Cout

$$\begin{align*} G_i &= A_i \cdot B_i \quad \text{(carry generated)} \\ P_i &= A_i \oplus B_i \quad \text{(carry propagated)} \end{align*}$$

Carry Equations:

$$\begin{align*} C_0 &= G_0 + P_0 \cdot C_{in} \\ C_1 &= G_1 + P_1 \cdot G_0 + P_1 \cdot P_0 \cdot C_{in} \\ C_2 &= G_2 + P_2 \cdot G_1 + P_2 \cdot P_1 \cdot G_0 + P_2 \cdot P_1 \cdot P_0 \cdot C_{in} \\ C_3 &= ... \end{align*}$$

Key Advantage: All carries calculated in parallel based only on inputs A, B, and Cin!

note

Carry Look-Ahead Adder block diagram to be added

Performance:

• Delay: ~2-3 gate delays (vs n×tFA for ripple)
• Tradeoff: More complex hardware

Typical Speedup:

• 4-bit CLA: 2-3× faster than ripple
• 16-bit CLA: 5-8× faster than ripple
• 64-bit CLA: 10-20× faster than ripple

Modern CPUs

Modern processors use variations of CLA (like Kogge-Stone adders) to perform 64-bit addition in just a few nanoseconds—crucial for high-performance computing!

Hierarchical CLA

For very large bit widths (32, 64 bits), use hierarchical approach:

Two-Level Structure:

Level 1: Four 4-bit CLA blocks (generate group G*, P*)
Level 2: CLA for group carries
Result: 16-bit addition much faster than ripple

note

Hierarchical CLA block diagram to be added

Binary Subtraction

Two Methods

Method 1: Direct Subtraction (Complex)

• Build subtractor circuits with borrow logic
• Similar to adder but more complex

Method 2: Two's Complement (Elegant)

• Convert subtraction to addition!
• Used in all modern computers

Two's Complement Representation

Two's complement is the standard way to represent signed integers.

For n-bit number:

• Positive numbers: 0 to 2^(n-1) - 1
• Negative numbers: -2^(n-1) to -1

4-Bit Two's Complement Range:

Binary	Decimal	Notes
0111	+7	Maximum positive
0110	+6
0001	+1
0000	0
1111	-1
1110	-2
1000	-8	Maximum negative

Key Property: MSB indicates sign (0=positive, 1=negative)

Converting to Two's Complement

To negate a number (find -X):

1. Invert all bits (one's complement)
2. Add 1

Example: Find -5 in 4-bit two's complement

+5 = 0101
Invert: 1010
Add 1: 1011
-5 = 1011 ✓

Verification: -5 + 5 should equal 0

  1011  (-5)
+ 0101  (+5)
-------
 10000  (discard overflow bit)
  0000  ✓ Correct!

Subtraction Using Two's Complement

To compute A - B:

1. Find two's complement of B (which is -B)
2. Add: A + (-B)
3. Discard carry out

Example: 7 - 3 using 4-bit arithmetic

Step 1: 7 = 0111
Step 2: 3 = 0011, -3 = 1101
Step 3: Add
  0111  (7)
+ 1101  (-3)
-------
 10100
Discard carry → 0100 = 4 ✓

note

Adder/Subtractor circuit to be added

Hardware Efficiency

Using two's complement, subtraction requires the SAME hardware as addition! This is why all modern CPUs use two's complement—one adder circuit does both operations.

Overflow Detection

Overflow occurs when result exceeds representable range.

For Signed Addition (Two's Complement):

Overflow if:

• Positive + Positive = Negative (overflow)
• Negative + Negative = Positive (overflow)
• Positive + Negative = any (no overflow possible)

Detection Circuit:

$$\text{Overflow} = C_{in(MSB)} \oplus C_{out(MSB)}$$

Example: Overflow in 4-bit arithmetic

  0110  (+6)
+ 0101  (+5)
-------
  1011  (-5 in two's complement) ✗ OVERFLOW!

Expected: +11, but max positive is +7

note

Overflow Flag circuit to be added

Binary Multiplication

Shift-and-Add Method

Binary multiplication uses the same concept as decimal, but simpler!

Example: 1011 × 1101 (11 × 13 = 143)

         1011  (11)
       × 1101  (13)
       -------
         1011  (1011 × 1)
        0000   (1011 × 0, shifted)
       1011    (1011 × 1, shifted)
      1011     (1011 × 1, shifted)
      ---------
      10001111  (143) ✓

Algorithm:

1. For each bit of multiplier (from right to left):
   • If bit = 1: Add multiplicand (shifted appropriately)
   • If bit = 0: Add nothing
2. Accumulate partial products
3. Result has double the bit width

Hardware Multiplication

note

Sequential Multiplier circuit to be added

Fast Multipliers:

• Array Multiplier: Parallel array of adders (fast but large)
• Booth's Algorithm: Reduces number of additions
• Wallace Tree: Parallel reduction of partial products

Modern CPUs have dedicated multiplier hardware optimized for speed.

ALU (Arithmetic Logic Unit)

The Complete Package

An ALU combines all arithmetic and logic operations in one unit.

Typical ALU Operations:

Mode	Operation
0000	A AND B
0001	A OR B
0010	A XOR B
0011	NOT A
0100	A + B (add)
0101	A - B (subtract)
0110	A + 1 (increment)
0111	A - 1 (decrement)
1000	Shift left
1001	Shift right
...	More operations

note

ALU block diagram to be added

Status Flags:

• Zero (Z): Result is zero
• Carry (C): Carry out from addition
• Overflow (V): Signed overflow occurred
• Negative (N): Result is negative (MSB = 1)

Commercial ALU IC: 74LS181

• 4-bit ALU
• 16 logic functions
• 16 arithmetic functions
• Cascadable for larger widths
• Classic IC, widely studied

The CPU's Core

The ALU is the computational heart of every processor. Everything from adding numbers in a spreadsheet to rendering 3D graphics ultimately executes in the ALU. Understanding it means understanding how computers actually compute!

Summary

Binary arithmetic is the foundation of all digital computation:

✅ Half Adder: Adds two bits, no carry input
✅ Full Adder: Adds three bits including carry
✅ Ripple Carry: Simple but slow for large widths
✅ Carry Look-Ahead: Fast parallel carry generation
✅ Two's Complement: Elegant subtraction method
✅ ALU: Complete arithmetic and logic unit

Key Takeaways:

1. XOR for sum, AND for carry: Basic building blocks
2. Full adders cascade: Multi-bit addition
3. Ripple delay: Major speed limitation
4. CLA optimization: Parallel carry calculation
5. Two's complement: Subtraction = Addition + Inversion
6. Overflow detection: Critical for correctness

Next Steps

We've mastered arithmetic—the processing side of digital systems. Next, we'll explore memory—where data is stored. RAM, ROM, Flash—understanding these completes our digital systems knowledge!

Further Reading

• "Computer Organization and Design" by Patterson & Hennessy
• Datasheet: 74HC283 (4-bit adder), 74LS181 (ALU)
• Advanced topics: Kogge-Stone adder, Brent-Kung adder
• Floating-point arithmetic (IEEE 754)

---

Practice Problems:

1. Design 8-bit ripple carry adder using 74HC283 ICs
2. Calculate propagation delay for 16-bit ripple adder (tFA = 12ns)
3. Add: 10110101 + 01011110 (show all carries)
4. Find two's complement of 01101001 (8-bit)
5. Compute: 0110 - 1001 using two's complement (4-bit)
6. Design overflow detection circuit for 8-bit adder
7. Multiply: 1101 × 1010 using shift-and-add
8. Compare gate count: 4-bit ripple adder vs 4-bit CLA