Two’s Complement Overflow Detection Using XOR

This article provides an overview of arithmetic overflow in two’s complement binary representation and explains how digital systems synthesize detection logic using XOR gates. You will learn the mathematical conditions that cause signed overflow, how sign bits and internal carries interact during addition, and why a single XOR gate connected to the most significant carry bits provides an optimal hardware solution.

Understanding Two’s Complement Overflow

In digital circuits, signed integers are predominantly represented using the two’s complement format. In an \(N\)-bit two’s complement system, the range of representable integers is:

\[[-2^{N-1}, 2^{N-1} - 1]\]

The most significant bit (MSB) serves as the sign bit, where 0 indicates a positive value and 1 indicates a negative value.

Arithmetic overflow occurs when the result of adding two \(N\)-bit numbers exceeds this representable range, yielding an incorrect arithmetic result. In signed addition, overflow can only happen under two specific conditions: 1. Two positive numbers are added, and the result is negative (\(0 + 0 = 1\)). 2. Two negative numbers are added, and the result is positive (\(1 + 1 = 0\)).

Adding numbers of opposite signs can never result in an overflow because the magnitude of the result is guaranteed to be smaller than the larger operand, remaining well within the representable range.

Boolean Condition for Overflow

Let \(A_{n-1}\) and \(B_{n-1}\) represent the sign bits of the two input operands, and \(S_{n-1}\) represent the sign bit of the computed sum. The classical Boolean expression for overflow (\(V\)) is:

\[V = (\overline{A_{n-1}} \cdot \overline{B_{n-1}} \cdot S_{n-1}) + (A_{n-1} \cdot B_{n-1} \cdot \overline{S_{n-1}})\]

While this expression directly checks the input and output sign bits using AND/OR gates, modern Arithmetic Logic Units (ALUs) synthesize overflow detection more efficiently using carry bits and an XOR gate.

Carry-Based Overflow Detection

In an \(N\)-bit adder, the full adder at the most significant bit (bit \(N-1\)) receives a carry-in (\(C_{n-1}\)) from the lower stage and generates a carry-out (\(C_n\)).

The relationship between these carry bits and arithmetic overflow is expressed as:

\[V = C_n \oplus C_{n-1}\]

Where: * \(C_{n-1}\) is the carry entering the sign bit position (\(N-1\)). * \(C_n\) is the final carry exiting the sign bit position (\(N\)). * \(\oplus\) denotes the logical XOR (Exclusive OR) operation.

Why the XOR Implementation Works

To understand how \(V = C_n \oplus C_{n-1}\) detects overflow, consider the behavior of the MSB adder cell (\(A_{n-1}, B_{n-1}, C_{n-1}\)):

1. Positive + Positive (\(A_{n-1} = 0, B_{n-1} = 0\))

• No Overflow: If \(C_{n-1} = 0\), then \(S_{n-1} = 0\) (positive) and \(C_n = 0\).
  • \(V = 0 \oplus 0 = 0\) (Valid).
• Overflow: If \(C_{n-1} = 1\), then \(S_{n-1} = 1\) (erroneously negative) and \(C_n = 0\).
  • \(V = 0 \oplus 1 = 1\) (Overflow detected).

2. Negative + Negative (\(A_{n-1} = 1, B_{n-1} = 1\))

• No Overflow: If \(C_{n-1} = 1\), then \(S_{n-1} = 1\) (negative) and \(C_n = 1\).
  • \(V = 1 \oplus 1 = 0\) (Valid).
• Overflow: If \(C_{n-1} = 0\), then \(S_{n-1} = 0\) (erroneously positive) and \(C_n = 1\).
  • \(V = 1 \oplus 0 = 1\) (Overflow detected).

3. Positive + Negative (\(A_{n-1} \neq B_{n-1}\))

• If \(A_{n-1} = 1\) and \(B_{n-1} = 0\):
  • If \(C_{n-1} = 0\), then \(S_{n-1} = 1\) and \(C_n = 0 \implies V = 0 \oplus 0 = 0\).
  • If \(C_{n-1} = 1\), then \(S_{n-1} = 0\) and \(C_n = 1 \implies V = 1 \oplus 1 = 0\).
• Overflow is impossible here, and the XOR condition consistently evaluates to 0.

Hardware Synthesis Advantage

Synthesizing overflow detection via \(V = C_n \oplus C_{n-1}\) requires only a single two-input XOR gate tapped into the carry lines of the final adder stage. This carry-based design reduces gate count, minimizes silicon area, and decreases propagation delay compared to multi-gate sign-bit evaluation circuits.