CPEN111: Lecture 8 - Overflow

CPEN111: Lecture 9 - Overflow

Reading Material

Page 31 to Page 33 of Yale Patt, Sanjay Patel's book: "Introduction to Computing Systems: From bits and gates to C and beyond" published by McGraw-Hill (2005) © B. Wang, 2025

Recall 2’s Complement

Definition: In computing devices, binary addition and subtraction are performed using the 2’s complement form.
General Rule for 2’s Complement:
- For a 2’s complement binary number with n bits:
- The largest possible value is:
  2^{n-1} - 1
  which corresponds to the binary representation of 0 followed by all 1s.
- The smallest possible value is:
  -2^{n-1}
  which corresponds to the binary representation of 1 followed by all 0s.
Example:
- For a 5-bit 2’s complement:
- Maximum value: 01111 (which is +15 in decimal).
- Minimum value: 10000 (which is -16 in decimal).
Output Bit-width Maintenance: After computing, the output will maintain the same bit-width as the input for fixed-point calculations.

Arithmetic Using 2’s Complement

Example Calculations using 2’s Complement:
- Operation 1:
- Value 1: 1
- Value 2: 6
- True form:
  - Value 1: 0 001 (binary for 1)
  - Value 2: 0 110 (binary for 6)
- Machine Value:
  - Value 1: 1
  - Value 2: 6
- 2’s Complement:
  - Value 1: 0 001
  - Value 2: 0 110
- Summation: 0 111
  - Decimal value is: 7 → right
- Operation 2:
- Value 1: 1
- Value 2: 7
- True form:
  - Value 1: 0 001
  - Value 2: 0 111
- Machine Value:
  - Value 1: 1
  - Value 2: 7
- 2’s Complement:
  - Value 1: 0 001
  - Value 2: 0 111
- Summation: 1 000
  - Decimal value is: -8 → wrong.
  - Discussion: Why this happened? How to detect?
- Operation 3:
- Value 1: -3
- Value 2: -5
- True form:
  - Value 1: 1 011 (binary representation of -3)
  - Value 2: 1 101 (binary representation of -5)
- Machine Value:
  - Value 1: 11 (2's complement format)
  - Value 2: 13
- 2’s Complement:
  - Value 1: 1 101
  - Value 2: 1 011
- Summation: 1 1000 (the sign bit + 4-bit result)
  - Decimal value is: -8 → correct.
- Operation 4:
- Value 1: -3
- Value 2: -6
- True form:
  - Value 1: 1 011 (binary representation of -3)
  - Value 2: 1 110 (binary representation of -6)
- Machine Value:
  - Value 1: 11
  - Value 2: 14
- 2’s Complement:
  - Value 1: 1 101
  - Value 2: 1 010
- Summation: 1 0111 (carry bit + 4-bit result)
  - Decimal value is: 7 → wrong.
  - Discussion: Why this happened? How to detect?

Overflow and Underflow

Definition of Overflow:
- Occurs when the sum of two positive numbers results in a negative value, indicating that the sum has overflowed.
- Occurs when the sum of two negative numbers results in a positive value, indicating that the sum has overflowed.
Evaluation of Overflow:
- If the result does not correspond to the expected sign based on the inputs, overflow occurs.
Reason for Overflow:
- The fundamental reason for overflow is that the result cannot be expressed using the number of binary bits used.
Note on Overflow and Carry Out:
- Overflow and carry out can each occur without the other.
- In unsigned numbers, carry out is equivalent to overflow.
- In 2's complement, carry out provides no information regarding overflow detection.

Consequences of Overflow

Two's Complement Wrap-Around:
- If the computation exceeds the maximum or minimum value for a given number of bits, it wraps around to the other end of the representable range.
Example:
- For 4-bit 2’s complement binary representation, the expressible range is from -8 to +7:
- Count Increase:
  - 0 → +1 → +2 → +3 → +4 → +5 → +6 → +7
- Count Decrease:
  - -1 → -2 → -3 → -4 → -5 → -6 → -7 → -8
Binary Representation Example Sequence:
- Representable range visualization: 0111 to 1100 (binary for +7 to -8).