This chapter covers binary arithmetic operations—specifically addition and subtraction using two's complement representation. Understanding these operations is fundamental since all computer arithmetic is ultimately performed in binary.
Binary addition follows four simple rules:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10 (0 with carry of 1)
1 + 1 + 1 = 11 (1 with carry of 1, when carry from previous)
Add binary numbers just like decimal, but carry occurs at 2 instead of 10.
1010 (10)
+ 0011 (3)
──────
1101 (13) ✓
10010 (18) ✓
#### Step-by-Step Process
1 0 1 1 (11)
- 0 1 1 1 (7)
─────────
Position 0: 1+1 = 0, carry 1
Position 1: 1+1+carry(1) = 1, carry 1
Position 2: 0+1+carry(1) = 0, carry 1 Position 3: 1+0+carry(1) = 0, carry 1 Position 4: carry(1) = 1
Result: 1 0010 (18)
### Overflow in Unsigned Addition
**Overflow** occurs when the result exceeds the maximum value for the bit width.
8-bit example (max = 255): 11111111 (255)
- 00000001 (1)
The beauty of two's complement: Addition works the same way regardless of sign!
+ 00000011 (+3)
──────────
<!-- License moved to dedicated LICENSE file -->
00000101 (+5)
+ 11111101 (-3)
──────────
100000010
Discard carry → 00000010 (+2) ✓
11111011 (-5)
+ 11111101 (-3)
──────────
111111000
Discard carry → 11111000 (-8) ✓
Always discard any carry beyond the word size in two's complement arithmetic!
The carry out of the MSB does NOT necessarily indicate overflow.
Subtraction is addition of the negative:
A - B = A + (-B) = A + two's_complement(B)
- Find the two's complement of the subtrahend (B)
- Add it to the minuend (A)
- Discard any carry beyond the word size
Step 1: Find -4 in two's complement
+4: 00000100
Flip: 11111011
+1: 11111100 (-4)
Step 2: Add 9 + (-4)
00001001 (+9)
+ 11111100 (-4)
──────────
100000101
Step 3: Discard carry
00000101 (+5) ✓
Step 1: Find -9 in two's complement
+9: 00001001
Flip: 11110110
+1: 11110111 (-9)
Step 2: Add 4 + (-9)
00000100 (+4)
+ 11110111 (-9)
──────────
11111011
Step 3: Result is negative (MSB=1)
11111011 = -5 ✓
Overflow happens when the result is too large or too small to fit in the available bits.
| Operation | Overflow Condition |
|---|---|
| Positive + Positive | Result appears negative (MSB=1) |
| Negative + Negative | Result appears positive (MSB=0) |
| Positive + Negative | NEVER overflows |
| Different signs | NEVER overflows |
Overflow = (Sign of A = Sign of B) AND (Sign of Result ≠ Sign of A)
8-bit two's complement (max = +127):
01100100 (+100)
+ 00110010 (+50)
──────────
10010110 (-106?)
✗ OVERFLOW! Two positives cannot equal a negative.
Actual result (+150) exceeds +127.
8-bit two's complement (min = -128):
10000000 (-128)
+ 11111111 (-1)
──────────
101111111
Discard carry → 01111111 (+127?)
✗ OVERFLOW! Two negatives cannot equal a positive.
Actual result (-129) below -128.
01111111 (+127)
+ 10000000 (-128)
──────────
11111111 (-1) ✓
No overflow! Different signs can't overflow.
Important Distinction:
- Carry: Bit carried out of MSB (unsigned overflow indicator)
- Overflow: Result out of range for signed arithmetic
Example:
11111111 (-1)
+ 11111111 (-1)
──────────
111111110
Carry out = 1 (ignore)
Result = 11111110 (-2) ✓
No overflow (negative + negative = negative)
For numbers larger than word size, add byte-by-byte carrying between bytes.
High Byte Low Byte
00010010 11010110 (4822)
+ 00001100 01011001 (3161)
─────────────────────
00011111 00101111 (7983) ✓
↑
Carry between bytes
By the end of this chapter, you should be able to:
- Perform binary addition with proper carry handling
- Add both positive and negative numbers in two's complement
- Convert subtraction to addition using two's complement
- Detect overflow in signed arithmetic
- Distinguish between carry and overflow
- Understand why two's complement simplifies arithmetic
- Perform multi-byte arithmetic operations
Run the interactive example:
python ch08_binary_arithmetic.py- Basic Binary Addition: Unsigned addition with carries
- Two's Complement Addition: Positive, negative, and mixed
- Binary Subtraction: Using two's complement method
- Overflow Detection: Recognizing invalid results
- Carry vs Overflow: Understanding the difference
- Step-by-Step Process: Detailed walkthroughs
- Verification: Checking results against decimal
============================================================
CHAPTER 8: Binary Addition and Subtraction
============================================================
--- Example 1: Unsigned Binary Addition ---
1010 (10)
+ 0011 (3)
──────
1101 (13) ✓
--- Example 2: Two's Complement Addition (Positive + Negative) ---
00000111 (+7)
+ 11111101 (-3)
──────────
100000100
Discard carry: 00000100 (+4) ✓
...
- ALU (Arithmetic Logic Unit): Performs all integer addition/subtraction
- Address Calculation: Memory address arithmetic
- Increment/Decrement: Program counter, loop counters
- Pointer Arithmetic: Adding offsets to pointers
- Integer Arithmetic: All
+and-operations - Array Indexing: Calculating element positions
- Time Calculations: Adding/subtracting timestamps
- Financial Software: Currency calculations (after conversion to integers)
- Adder Circuits: Ripple-carry, carry-lookahead, carry-select
- Subtractor Circuits: Using two's complement and adders
- Counters: Up/down counters for timing and control
- Accumulators: Sum registers in CPUs
- Sensor Data: Adding/averaging sensor readings
- Control Algorithms: PID controllers, state machines
- Communication: Checksum calculations
- Real-Time Systems: Time-critical arithmetic
Q: Why do we discard the carry in two's complement addition?
A: The carry out of MSB doesn't indicate overflow in signed arithmetic. It's normal and expected in some valid operations (like positive + negative).
Q: How do computers detect overflow?
A: By checking if the signs of the operands match and differ from the result's sign. This is implemented in hardware with XOR gates.
Q: Can overflow occur when adding numbers of different signs?
A: No! If signs differ, the magnitude of the result is always between the operands, so it always fits.
Q: What happens when overflow occurs?
A: The result "wraps around." Many systems set an overflow flag that software can check. Some languages throw exceptions.
Q: Why is binary addition the same for signed and unsigned?
A: Two's complement was designed this way! The bit patterns work for both. Only the interpretation (and overflow detection) differs.
Each bit position:
- Sum = A XOR B XOR Carry_in
- Carry_out = (A AND B) OR ((A XOR B) AND Carry_in)
For each bit position i from 0 to n-1:
Sum[i] = A[i] ⊕ B[i] ⊕ Carry[i]
Carry[i+1] = (A[i] ∧ B[i]) ∨ ((A[i] ⊕ B[i]) ∧ Carry[i])
- Carry-Lookahead: Calculates all carries in parallel
- Carry-Select: Computes both possible sums (carry 0 or 1)
- Carry-Save: Multiple operands with delayed carry resolution
- ➕ Binary addition follows simple rules: 0+0=0, 0+1=1, 1+1=10
- Two's complement addition works the same for signed and unsigned
- ➖ Subtraction = Addition of two's complement: A - B = A + 2's(B)
- 🚫 Discard carries beyond word size in two's complement
- Overflow occurs when: (same signs) AND (result sign differs)
- Positive + Negative never overflows
- Carry out ≠ Overflow (different concepts)
- Hardware uses same adder for addition and subtraction
- Add 1011₂ + 0110₂
- Add 11110000₂ + 00001111₂
- Does 11111111₂ + 00000001₂ overflow (8-bit unsigned)?
- Add (+15) + (+20) in 8-bit two's complement
- Add (+30) + (-25) in 8-bit two's complement
- Add (-40) + (-50) in 8-bit two's complement (detect overflow)
- Calculate 25 - 17 using 8-bit two's complement
- Calculate 10 - 30 using 8-bit two's complement
- Show step-by-step: 01100100₂ - 00010110₂
- Detect overflow: 01111111₂ + 00000001₂ (8-bit two's complement)
- Detect overflow: 10000000₂ + 11111111₂ (8-bit two's complement)
- Explain why 01111111₂ + 10000000₂ cannot overflow
- Learn about multiplication and division in binary
- Study different adder architectures (CLA, CSA)
- Explore saturating arithmetic (clamping instead of overflow)
- Investigate floating-point arithmetic (Chapter 9)
- Learn about SIMD (Single Instruction Multiple Data) operations
Course Navigation:
← Previous: Chapter 7 - Signed Numbers | Next: Chapter 9 - Floating Point →
Authored by Maxwell Hauser on November 19, 2025
MIT License