Last modified: Sun Jun 14 20:31:01 UTC+0200 2026 © A. Tarpai
SIGNED ARITHMETIC AND OVERFLOW IN THE ADDER
This is Part II. of ALU Investigations
The adder knows no such thing as signed arithmetic. It adds binary numbers and use/produce a carry bit.
Treating numbers and results as signed values is a clever way to use a simple adder to make calculations on positive and negative numbers. In this way the adder performs apparently signed additions and subtractions without the need to change the circuitry.
Later, some additional ALU support for signed arithmetic was added to microprocessors, f. ex. the SIGNED OVERFLOW flag (OF). The adder circuit and operation remained unchanged. This is what originally kick started the whole investigation: what is the OV Flag and how is it working on the hardware level with an adder circuit.
Most of the examples use 4-bit numbers and a simple ripple-carry adder for analysis.
•---------•---------•---------•---------- A[3..0] in
| •-------|-•-------|-•-------|-•-------- B[3..0] in
_|_|_ _|_|_ _|_|_ _|_|_
| A B | | A B | | A B | | A B |
| C|_ | C|_ | C|_ | C|_______CARRY in
CARRY out___|C' | \_|C' | \_|C' | \_|C' |
|__Y__| |__Y__| |__Y__| |__Y__|
| | | |
•---------•---------•---------•--------- Y[3..0] out
Signed two's complement representation/interpretation/notation are synonyms.
Arithmetic- and signed overflow are synonyms. I use mostly signed overflow.
- Signed representation of binary numbers
- Signed two's complement
- Negating
- Signed arithmetical operations and overflow
- ALU support for Signed Two's-Complement Arithmetic
- Signed Overflow and signed arithmetic operations
- What is signed overflow?
- Signed overflow: definition
- Proving the signed overflow definition
- Overflow detection in hardware based on sign of terms
- Overflow detection in hardware by the CY XOR CY-1 method
- Signed Semantics
- Working with the OV Flag
- SIGNED COMPARISON and the CMP instruction (Intel x86 Jcc)
Signed representation of binary numbers
For signed representation the high order bit is interpreted as the sign bit (0 for positive numbers, 1 for negative), the remaining bits store the magnitude of the number:
Signed representation on 4-bits
3 2 1 0
+---+---+---+---+
| | |
+---+---+---+---+
sign magnitude
The definition divides the full binary range into two equal parts:
The upper half of the binary range is denoted to negative values in the two's complement way.
Signed two's complement
Signed representation is based on two's-complement as adding any number to its two's complement value, the adder circuit produces a zero result (ignore carry).
Eg. for 5, the value 11 must be added for a zero result, thus 11 can represent −5 in storage and calculations:
0 1 0 1 = 5
+ 1 0 1 1 = 11 "-5"
-------------
1 0 0 0 0
|
CY
Note that during two's-complement arithmetic we can largely ignore the carry bit.
Signed two's complement pairs on 4-bits:
Two's = Signed two's
complement complement
value notation
0 = 0000 <->
1 = 0001 <----> 1111 = 15 = -1
2 = 0010 <----> 1110 = 14 = -2
3 = 0011 <----> 1101 = 13 = -3
4 = 0100 <----> 1100 = 12 = -4
5 = 0101 <----> 1011 = 11 = -5
6 = 0110 <----> 1010 = 10 = -6
7 = 0111 <----> 1001 = 9 = -7
<-> 1000 = 8 = -8
positive negative
- The range of positive numbers that can be represented is, therefore, from 0 to 7.
- The range of negative numbers that can be represented is from −1 to −8.
On 8-bits the signed range is from −128 to 127, on N-bits from −2N-1 to 2N-1-1.
There are 2 special values: zero and the largest negative number, –8 (i.e. half or 2N-1). Both have a magnitude of zero and both equal their two's complement. Two's complement representation is actually symmetric:
The value of zero is considered positive and equals its negate (i.e. there is no negative zero defined). Adding zero to zero is obviously zero.
The largest negative number, –8 also equals its negate (i.e. there is no positive 8 defined). But two's-complement arithmetic still holds:
- adding –8 to its negate produces zero: 1000b + 1000b = 1 0000b (ignore carry)
- using –8 in calculations f. ex. 2 + –8 = –6 will give correct result:
0 0 1 0 2
+ 1 0 0 0 8 = -8
-------------
1 0 1 0 10 = -6
Negating
In the signed interpretation world, two's-complement pairs represent negated pairs – as adding any number to its negate mathematically equals zero. The two's complement operation changes the sign of a number (except for zero and largest negative number).
The two's complement operation is equivalent to negating:
- invert each bit of the number (producing the so-called one's complement)
- add one to the result, ignoring any carry out of the high order bit position
For zero and the largest negative number there is no sign change, but the negate, which is the same value, arithmetically complements the counterpart number to zero by addition.
Signed arithmetical operations and overflow
Numbers and results are only interpreted as signed positive or negative values – based on the most significant bit. Because of two's-complement, the result of the addition is usually mathematically correct. Usually, because the addition result can overflow on the finite number of magnitude bits. This signed overflow is part of signed arithmetic and determines the interpretation of the result. The signed semantics of additions will be different.
A bunch of addition examples: green positive-, blue negative addendum. Some overflows, some don't. It's quite difficult to see what are the exact cases and how a simple adder can detect signed overflow – so we go into a detailed analysis.
ALU support for Signed Two's-Complement Arithmetic
For signed arithmetic, the adder circuit and operation remained unchanged: the adder performs addition of two arbitrary binary numbers with carry. No more.
These are some basic ALU functions/instructions to support signed two's-complement arithmetic and interpretation:
The SIGN flag: SF
Appeared as early as the Intel 8008 in 1972. Arithmetic instructions set the Sign flip/flop if the msb of the result is '1'. SF can be used for making decisions during program execution, such as branching based on the result in the accumulator.
The NEG instruction
Supports the two's complementing operation and to change the sign of a number.
Up until the 8086 there was no NEG instruction implemented in Intel processors. NEG can be achieved by two equivalent operations:
- complement and increment (in this order!)
- subtract from zero without borrow (clear carry and subtract)
The x86 NEG instruction subtracts the operand from zero and sets the Flags accordingly.
The SIGNED OVERFLOW FLAG: OF
The Overflow Flag is an additional ALU support for signed two's complement arithmetic – first appeared in the 8086 member of the Intel microprocessor line.
What is it, how the hardware implements the OV Flag and how to use it during programming what this article is mainly about.
Signed comparison following CMP
With the help of the OV Flag the adder can detect signed relationship between two numbers following CMP. From the 8086 member, specific conditional jump instructions can test the less-condition (JL/JNL). We will introduce the Less-flag used for signed comparison and more general, for signed overflow/underflow detection following additions and subtractions.
Signed Overflow and signed arithmetic operations
- What is signed overflow?
- Signed overflow: definition
- Proving the signed overflow definition
- About signed subtractions
- Adding numbers with different signs will never overflow
- Addition of two positive numbers cannot be less positive
- Addition of two negative numbers cannot be less negative
- Overflow detection in hardware based on sign of terms
What is signed overflow?
Informally, signed overflow – or underflow – in our 4-bit adder happens when additions exceed 7, or subtractions exceed −8:
F. ex. adding 1 to 7 is 8, but the result in the adder means −8 in signed representation. The value in the adder is not the mathematical result. An overflow has occurred 4and the ALU should signal overflow. It should, but for a plain binary adder these transitions are not really special.
The previous definition is not even complete, additions can turn around and produce correct results, nevertheless.
Signed overflow: definition
A more precise definition of arithmetic overflow is based on the signs of terms. This is also the mathematical approach.
When numbers with same signs are added and there is a sign change in the result, an arithmetic overflow has occurred:
pos + pos --> neg: overflow pos + neg --> cannot overflow neg + pos --> cannot overflow neg + neg --> pos: overflow
We can also define similar rules for subtraction based on subtraction equals addition of negate: when numbers with different signs are subtracted and there is a sign change in the result to the minuend, an arithmetic overflow has occurred – which essentially states the same rule as above:
pos - neg = pos + pos --> neg: overflow pos - pos = pos + neg --> cannot overflow neg - neg = neg + pos --> cannot overflow neg - pos = neg + neg --> pos: overflow
Adding numbers with different signs will never overflow – similar to subtracting numbers with the same signs.
But these are pretty strong statements and need verification..
Proving the signed overflow definition
Because our adder wraps around it is difficult to see the validity of the definition, especially with a carry bit also involved in additions.
In order to fully trust the Signed overflow definition, we have to prove the following statements:
- Adding numbers with different signs will never overflow
- Addition of two positive numbers cannot be less positive, i.e. false no-overflow cannot occur
- Similarly, the result cannot be less negative by adding two negative numbers
About signed subtractions
As described in great details, subtraction is performed by addition of true complement in the adder. That is adding one's complement of B and complement of CY to A:
A - B - CY = A + NOT B + NOT CY
More precisely MOD2n(A - B - CY) = MOD2n(A + NOT B + NOT CY) i.e ignoring carry out
The one's complementing operation certainly changes sign of B, thus subtracting a positive value will be equivalent to adding some negative value and vica versa:
- pos − neg ≈ pos + pos
- pos − pos ≈ pos + neg
- neg − neg ≈ neg + pos
- neg − pos ≈ neg + neg
Meaning after proving Signed overflow for additions, it will also prove the validity of the adder subtractions.
Adding numbers with different signs will never overflow
To put it in another way: is it possible that f. ex. adding a positive value to a negative could yield a more negative result in the adder?
Let's use some modulo math for the adder.
Suppose we have an n-bit adder and signed two's complement interpretation. We consider CY as a bit-extension to the addition range. The n-bit adder calculates the sum of two binary values with carry and has 2n+1 output states (i.e. counts from 0 to 2n+1-1). After the addition the value left in the adder is MOD2n of the sum.
Let M = 2n
Define positive (P) and negative (N) values by dividing the bit range into two equal parts:
min(P) = 0, max(P) = 1/2M-1
min(N) = 1/2M, max(N) = M-1
C is the carry bit.
When adding any pos to neg with carry the range of sum for N + P + C is:
min(N+P+C) = min(N) + min(P) + 0 = 1/2M + 0 + 0 = 1/2M
max(N+P+C) = max(N) + max(P) + 1 = M-1 + 1/2M-1 + 1 = 3/2M-1
when adding any neg to pos with carry the range of sum for P + N + C is:
min(P+N+C) = min(P) + min(N) + 0 = 0 + 1/2M + 0 = 1/2M
max(P+N+C) = max(P) + max(N) + 1 = 1/2M-1 + M-1 + 1 = 3/2M-1
The result is the same for both ranges, as expected, but nice to get verified commutativity using adder arithmetics as well:
CY=1 -->
P N P N
|------------------------|------------------------|------------------------|------------------------|
0 1/2M-1 1/2M M-1 M 3/2M-1 3/2M 2M-1
NO OVERFLOW
|------------------------|------------------------|
1/2M 3/2M-1
min(N + P + C) max(N + P + C)
min(P + N + C) max(P + N + C)
SUM(N + P + C) = SUM(P + N + C)
It can be seen that
- adding any negative to positive, MOD2n of sum will be either negative (the min addendum is 1/2 M) or <= P (the max addendum is M), i.e. sum cannot be more positive
- adding any positive to negative, MOD2n of sum will be either positive (the max addendum is 1/2 M) or >= N (the min addendum is 0), i.e. sum cannot be more negative
In other words, we have proven:
- pos + neg ≈ MOD2n(SUM(P + N + C)) → cannot overflow
- neg + pos ≈ MOD2n(SUM(N + P + C)) → cannot overflow
Addition of two positive numbers cannot be less positive
When adding two positive numbers and there is no overflow according to the definition (the result is positive), the value in the adder is the mathematical result. I.e. it cannot be less positive by somehow wrapping around too much.
Addendum: min(P+C) = 0, max(P+C) = 1/2M
Sum:
min(P+P+C) = 0
max(P+P+C) = max(P) + max(P) + 1 = 1/2M-1 + 1/2M-1 + 1 = M - 1
Sum of two positive numbers and carry
CY=1 -->
P N P N
|------------------------|------------------------|------------------------|------------------------|
0 1/2M-1 1/2M M-1 M 3/2M-1 3/2M 2M-1
OVERFLOW
|------------------------|------------------------|
0 M-1
min(P + P + C) max(P + P + C)
Adding any positive to positive we can see that:
- sum is either the same or some more positive value with no overflow (the min addendum is 0),
- or falls into the N range, which is mathematically wrong, and an overflow occurs.
The result cannot be less positive, because max(P + P + C) = M-1, i.e. it cannot fall into the next P range starting from M, thus verifying the sign-correctness of the overflow definition.
Note that the max addendum is max(P+C) = 1/2M. This is adding plus 8 – or half, 2n-1. It needs some clarification later.
Addition of two negative numbers cannot be less negative
Similar to positive numbers, proof that by adding two negative numbers the result cannot be less negative.
Addendum: min(N+C) = 1/2M, max(N+C) = M
Sum:
min(N+N+C) = min(N) + min(N) + min(C) = 1/2M + 1/2M + 0 = M
max(N+N+C) = max(N) + max(N) + max(C) = M-1 + M-1 + 1 = 2M - 1
Sum of two negative numbers and carry
CY=1 -->
P N P N
|------------------------|------------------------|------------------------|------------------------|
0 1/2M-1 1/2M M-1 M 3/2M-1 3/2M 2M-1
OVERFLOW
|------------------------|------------------------|
M 3/2M-1 3/2M 2M-1
min(N + N + C) max(N + N + C)
Adding any negative to negative:
- MOD2n of sum can fall into P range. It is mathematically wrong, and an overflow occurs, also according to sign overflow definition. It can happen by adding two small magnitude negative values, i.e. larger negatives.
- or falls into N range with no overflow.
We can trust the signed overflow definition, because the result cannot be less negative: max(N + N + C) = M, which is maximum the same MOD2n value as the addend (see the addition of negative zero).
Overflow detection in hardware based on sign of terms
From the definition of signed overflow, one way to extend the adder to detect signed overflow and implement the OV Flag is based on combinational logic of the sign-bit of terms, i.e. a combination of the msb-bits.
The adder adds A, B and C (carry) producing result of Y:
- positive A + B + C either overflows (changes sign) or not (the result stays positive)
- negative A + B + C either overflows (changes sign) or not (the result stays negative)
- for all other cases we have proven that adding different signs will never overflow
SA SB SY Example 4-bit addition 0 0 0 no signed overflow Positive A + B produces positive result (2 + 3) 0 1 0 no signed overflow 1 0 0 no signed overflow 1 1 0 SIGNED OVERFLOW Negative A + B produces positive result (-5 + -4) 0 0 1 SIGNED OVERFLOW Positive A + B produces negative result (2 + 7) 0 1 1 no signed overflow 1 0 1 no signed overflow 1 1 1 no signed overflow Negative A + B produces negative result (-5 + -1)
OF could be implemented with combinational logic f.ex. OF = NOT(SA XOR SB) XOR SY with a few gates:
+-----+
SA --> | |
SB --> | | --> OF
SY --> | |
+-----+
On the hardware level this is not so simple: SA and SB should be latched in flip-flops before adder operation, then after the result sign bit is available can OF derived safely. Luckily there is another way, and this is what the next chapter is about..
Overflow detection in hardware by the CY XOR CY-1 method
The adder performs additions of two arbitrary binary numbers with carry. No more.
This is an investigation into how our simple adder circuit can be extended on the hardware level to support and detect signed overflow after additions and subtractions, when numbers are interpreted as signed two's complement values.
The CY XOR CY–1 method
We are interested in how sign changes happen based on the definition of signed overflow.
Let's divide the addition process into:
- add magnitude N-1 bits and observe CY–1 (overflow on magnitude)
- add msb, the sign bit with CY–1 and observe the result and CY (overflow on sign)
Addition of Y = A + B on 4 bits
2. Add A + B 1. Add A + B
SIGN MAGNITUDE
+---+ +---+---+---+
| s | | m | A
+---+ +---+---+---+
+ | s | | m | B
+---+ +---+---+---+
______________________________________________
+---+ +---+---+---+
CY <-- | s | <-- CY <-- | m | Y
+---+ +---+---+---+
The sign bit (msb) addition happens in the last 1-bit adder and the outcome is dependent on three inputs:
- SA: msb of A input
- SB: msb of B input
- CY–1 from addition of magnitudes
This gives 8 combinations for the outcome of the sign- and final carry bit of the result.
On the left is the truth table of the last adder, where SY = MOD2(SA + SB + CY–1) and CY = DIV2(SA + SB + CY–1) along with an example binary addition for each combination to see if signed overflow occurs in two's complement representation:
I have chosen two B-values to add, 3 and -5, so that the addendum has the same magnitude and only differs in the sign bit. Thus, the first part of the addition, add 3, is identical. Adding magnitude first can affect CY–1 (single-line sign change) or both CY and CY–1 (double-line sign change); while adding msb sign bit afterwards may effect only the CY bit. The adder itself adds either 3 or 11: moves right 3 or 11 values.
There are only 2 cases where the mathematical sum is different from the value left in the adder, in signed two's complement representation. A signed overflow has occurred.
Illustrating these two cases. Left: addition of 6 + 3: sum of two positive numbers yield negative result. Right: addition of -6 + -5: sum of two negative numbers yield positive result.
Logic for signs of SA, SB and SY indeed follows the definition of signed overflow: same signs were added, and the result has a different sign. The boolean equation would be something like this: OF = NOT(SA XOR SB) XOR SY.
But when we solve the truth table for the two CY outcomes - or it is pretty obvious by looking at it - the two cases with signed overflow are when the two highest carry bits differ: CY XOR CY–1 = 1. I.e. the detection of sign-change for signed overflow following addition is equivalent to CY XOR CY–1.
This looks simple and very promising.
If we can prove that this method detects correct signed overflow for all additions as well as subtractions in the adder, on the hardware level, adding a single XOR gate to the adder circuitry will implement the OV Flag, for both additions and subtractions:
•---------•---------•---------•---------- A[3..0] in
| •-------|-•-------|-•-------|-•-------- B[3..0] in
_|_|_ _|_|_ _|_|_ _|_|_
| A B | | A B | | A B | | A B |
| C|_ | C|_ | C|_ | C|____ CARRY in
CARRY out ___|C' | \_|C' | \_|C' | \_|C' |
| |__Y__| ||__Y__| |__Y__| |__Y__|
| | | | | |
| •-----|---•---------•---------•--------- Y[3..0] out
| |
+----XOR---+
|
OF
That would be a truly elegant and fascinating engineering feat!
Proving the CY XOR CY–1 method
We will prove that this method will detect correct signed overflow for:
- additions with carry cleared
- additions with carry set
- subtractions performed by addition of true complement in the adder
Additions with carry = 0
The analysis above has already proven the correctness of the CY XOR CY–1 method. That's how we came up with it.
Additions with carry = 1
We are interested in how a set Carry before the addition can or may affect the outcome of signed overflow detection with the CY XOR CY–1 method. This is important to trust multi-digit additions and the detected signed overflow. It will be also the principle of how subtraction detects correctly signed overflow.
We will prove that adding any B value with set Carry to A will also detect correct signed overflow with the CY XOR CY–1 method.
+---+
| 1 | CY
+---+---+---+---+
| s | m | A
+---+---+---+---+
+ | s | m | B
+---+---+---+---+
________________________________
+---+---+---+---+
CY <-- | s | m | Y
+---+---+---+---+
At first guess, f. ex. adding B = 2 with set carry to 4 vs. adding B' = 3 with cleared carry to 4 should certainly produce the same result (7) in the adder:
The greyed-out bits are calculated by the adder. We're particularly interested in the two highest carry bits in squares during these additions. In this case there is no change, and we can certainly state that adding 2 with carry is identical to adding 3 in the adder when it comes to signed overflow detection with the CY XOR CY–1 method. I.e. we can trust OF when adding 2 with carry.
Statement:
Addition of any B value with carry, where magnitude has one or more zero bits will not affect the outcome of CY–1, and consequently will not affect the outcome of CY. The addition is equivalent to adding B' = B + 1 in the adder without carry, which we know detects overflow correctly with the CY XOR CY–1 method.
Proof:
Let's write all possible additions on 4-bits to some value of A with set carry (B), and compare each to additions with cleared carry (B') to see if the results are equivalent or not:
B B'
add 0000 (0) + CY = add ?
add 0001 (1) + CY = add ?
add 0010 (2) + CY = add ?
add 0011 (3) + CY = add ?
add 0100 (4) + CY = add ?
add 0101 (5) + CY = add ?
add 0110 (6) + CY = add ?
add 0111 (7) + CY = add ?
add 1000 (8) + CY = add ?
add 1001 (9) + CY = add ?
add 1010 (10) + CY = add ?
add 1011 (11) + CY = add ?
add 1100 (12) + CY = add ?
add 1101 (13) + CY = add ?
add 1110 (14) + CY = add ?
add 1111 (15) + CY = add ?
The elimination process:
1. Adding any B value where lsb = 0 with CY set is equivalent to adding a value with lsb set and CY cleared. The 1-bit lsb addition does not change the outcome of the result (y0) and the intermediate carry out (c1).
c: same intermediate- and carry bits
a, b, y: same bits of terms
The modified value is exactly B' = B + 1. This eliminates half of the additions to investigate:
B B'
add 0001 (1) and CY = add ?
add 0011 (3) and CY = add ?
add 0101 (5) and CY = add ?
add 0111 (7) and CY = add ?
add 1001 (9) and CY = add ?
add 1011 (11) and CY = add ?
add 1101 (13) and CY = add ?
add 1111 (15) and CY = add ?
2. Adding any B value where lsb = 01 with CY set is equivalent to adding a value with lsb = 10 and CY cleared. The first addition will certainly set c1 and gives the same result bit y0, but the next one again, will produce equivalent result (y1) and unchanged carry (c2) for the next addition.
The modified value is again, exactly B' = B + 1. This eliminates half of the additions to investigate:
B B'
add 0011 (3) and CY = add ?
add 0111 (7) and CY = add ?
add 1011 (11) and CY = add ?
add 1111 (15) and CY = add ?
3. Similarly, adding any B value where lsb = 011 with CY is equivalent to adding a value with lsb = 100 without CY.
Intermediate carry c3 is our CY–1 bit in question, being the same, eliminates half of the additions to investigate:
B B'
add 0111 (7) and CY = add ?
add 1111 (15) and CY = add ?
4. We ended up with two additions with CY, all one's in magnitude to investigate. These are NEW additions that can be performed only with CY.
Full magnitude additions with carry
The question is what is the meaning of these additions in signed two's complement? Add 7 + 1 equals eight, but 8 is a negative value on 4-bits. For 7 + 1 the sign-bit is not set, so is this a real two's complement positive value? For 15 + 1 = 16, what does this mean in two's complement?
We will see, although signed two's complement representation does not interpret negative zero and positive eight on 4-bits, the adder performs correct signed calculations with these numbers and detects overflow as well.
Positive eight
This addition is new, an addition of one more positive value than the highest positive number.
- adding one more positive, than 7 to positive numbers should certainly overflow (extreme case: 0 + 7 + 1 = 8)
- adding any positive to negative numbers should not overflow (extreme case: -1 + 7 + 1 = 7)
This addition will certainly set CY-1. The final CY and the result bit (sign) is dependent on the msb (sign-bit) of the addend (A):
Add LARGEST POSITIVE with CY to A
The sign bit addition:
C 1 __ C 1 __
A 0 \ A 1 \
B 0 B 0
____________ ____________
C' Y 0 1 C' Y 1 0
A = POS A = NEG
Y = NEG Y = POS
OVERFLOW! NO OVERFLOW
The semantic of this addition is indeed "plus 8" – or plus 2N-1 in an N-bit adder. The adder performs correct addition as if the addendum is positive and the magnitude is maximum. We can see that both methods detect signed overflow correctly:
1. By the CY-method:
- neg A will set CY and no overflow is detected
- pos A will clear CY and overflow is detected
2. By the sign-method:
- B is a positive number
- for neg A the result sign-bit is zero (pos Y): no overflow detected
- for pos A the result sign-bit is one (neg Y): overflow detected
For comparison, consider these two additions: add positive eight and negative eight to 4. Both additions give the same result (12) except intermediate carry bits, thus detecting correct signed overflow by the CY XOR CY–1 method:
- add 7 + 1 to 4 is 12, interpreted correctly as a positive addendum and a result with overflow
- add −8 to 4 is also binary 12, but interpreted as a negative addendum with a correct negative result of −4 without overflow.
Negative zero
This addition is new, an addition of a full circle and results in the same number as A. No signed overflow should be detected:
1. By the CY-method:
This addition will certainly set CY-1 and will certainly set CY. Each 1-bit adder will produce carry regardless of bits of A:
1_ 1 __ set carry
A and so on.. x \ x
B \ 1 \ 1
Y \_1 x \_1 x
Both carry bit is 1 and no overflow is detected regardless the value of A.
2. By the sign-method:
Analyzing the msb addition in the last 1-bit adder:
Add LARGEST NEGATIVE with CY to A
C 1 __ C 1 __
A 0 \ A 1 \
B 1 B 1
____________ ____________
C' Y 1 0 C' Y 1 1
A = POS A = NEG
Y = POS Y = NEG
NO OVERFLOW NO OVERFLOW
There is no sign change based on signs of terms:
- adding to pos will result in pos, which signals no overflow
- adding to neg will result in neg, which signals no overflow
For comparison, addition of negative zero and addition of zero:
- add all one with set carry will set all intermediate- and final carry bit to one, and no overflow will be detected (CY = CY–1 = 1)
- add all zero with zero carry will set all intermediate- and final carry bit to zero, and no overflow will be detected (CY = CY–1 = 0)
Conclusion
On 4 bits, addition of B with carry is equivalent to adding the following B' values in the adder, when it comes to signed overflow detection with the CY XOR CY–1 method. We didn't find equivalent additions for full magnitude numbers:
- certianly 15 or -1 + CY cannot be performed without carry (let's call this negative zero)
- for 7 + CY the intermediate carry bits are different, and the interpretation is new (addition of positive eight or
2N-1)
As seen above, the two new additions will also detect overflow correctly by this method. Note that two's-complement is only an interpretation and adder operation is the same (f. ex. adding 12 or -4 makes no difference).
Equivalent additions for B + CY and B'
2's compl 2's compl
B addition equivalent B'
B B' semantic addition
add 0000 (0) + CY = add 1 add 1 add 1
add 0001 (1) + CY = add 2 add 2 add 2
add 0010 (2) + CY = add 3 add 3 add 3
add 0011 (3) + CY = add 4 add 4 add 4
add 0100 (4) + CY = add 5 add 5 add 5
add 0101 (5) + CY = add 6 add 6 add 6
add 0110 (6) + CY = add 7 add 7 add 7
add 0111 (7) + CY = - add 8 add - No equivalent B'. Add "positive eight"
add 1000 (8) + CY = add 9 add -7 add -7
add 1001 (9) + CY = add 10 add -6 add -6
add 1010 (10) + CY = add 11 add -5 add -5
add 1011 (11) + CY = add 12 add -4 add -4
add 1100 (12) + CY = add 13 add -3 add -3
add 1101 (13) + CY = add 14 add -2 add -2
add 1110 (14) + CY = add 15 add -1 add -1
add 1111 (15) + CY = - add -0 add - No equivalent B'. Add "negative zero"
Signed Semantics
The most interesting find during signed overflow analysis is that there is a semantic difference between additions with carry cleared and carry set around half (unsigned addition does not differentiate between the two):
Add with carry occurs in multi-digit additions. The meaning of these additions is to add one more and it works perfectly for signed interpretation as well, both in semantic and for overflow detection:
- Most of the additions with CY=1 have the semantic as the appropriate addition with CY=0. Overflow detection is correct by both methods.
- Add one more, than −1 can be interpreted as add −0 (vs. 0). No overflow is detected by either method.
- Add one more, than the largest positive (2N-1-1) is indeed an addition of positive value 2N-1. Overflow detection is correct by both methods.
Additions interpreted as subtraction
When using the adder to subtract numbers (by the true complement method), these are additions interpreted as subtraction. The adder has no knowledge whether the same addition operation means add or sub, signed or unsigned values, pos or neg: it operates binary.
We have proven that both the sign- and the CY XOR CY–1 method detects correct overflow for all additions with or without carry. Therefore, overflow detection for additions interpreted as subtraction will be also correct.
The interpretation is simply negated values. We can safely extend the table with the corresponding subtraction interpretations:
ADD/SUB Semantics of the 4-bit adder
Hardware implementation
On the hardware level:
All that means that if we have already wired OF as CY XOR CY–1 in the adder and it works for all signed additions – it will also work for signed subtractions, only if SUB is implemented by adding true complement:
+----------------------------------------------------------------------------+
|SUB |
| +---------------------------------------------------+ |
| |ADD | |
| | +-----------------------------------+ | |
| | | ADDER | | |
| | | | | |
| | | SIGN MAGNITUDE | | |
| _____ | | +---+ +---+---+---+ | | _____ |
CY <-- |-| NOT |<--| CY <--|<--•--| |<-•---| | | | |<-- CY |<--| NOT |--|<-- CY
(BORROW) | |_____| | | | +---+ | +---+---+---+ | | |_____| | (BORROW)
| | | | | | | _____ |
| | | +-- XOR --+ |<-- OP |<--| NOT |--|<-- OP
| | | | | | |_____| |
| | | | | | |
| | +--------|--------------------------+ | |
| | | | |
+-----------+----------------|----------------------------------+------------+
|
OF
Working with the OV Flag
Interpreting signed overflow
Signed overflow after addition or subtraction means the value in the adder is not the mathematical result. But it's still possible to interpret the overflowed signed two's complement value.
Let's look at the result of addition or subtraction of two signed values considering CY as a bit-extension in a 4-bit adder:
OF: overflow flag
SF: sign flag
When OF = 1, the Sign Flag tells in which direction the two's complement overflow has occurred:
- SF=1 → in the positive direction. Adder stores an overflowed positive result. Max overflow in the positive direction: 7 + 7 + CY = 15. Equivalent to 7 - −8 = 15 when subtracting.
F. ex. 3 + 7 = 10. OF is signaled meaning the result is falsely −6. The correct result is 10.
- SF=0 → in the negative direction. Adder stores a two's complement value of an overflowed negative result. Max overflow in the negative direction: −8 + −8 = −16 (that is little special: the result is zero).
F. ex. −6 + −5 = 5. OF is signaled meaning the result is falsely positive 5. Two's complementing 5 → 11. The correct result is −11.
Note. Looking at the fig above, I would ask: why not simply test CF for that? All results with CF=0 looks positive and all with CF=1 looks negative. But consider eg. these additions: 7 + 1 vs 8 + 0 in the adder. Both result is 8, CF = 0, but OF is different! Adding zero to –8 should not signal signed overflow. But adding 1 to 7 should. The reason is that there are several ways to get the same result value in the adder but intermediate carry bits may differ.
0111 7 1000 -8
0001 + 1 0000 + 0
1000 = -8 1000 = -8
CF 0 0
SF 1 1
OF 1 0
There are several important practical implications of the above:
- it is possible to interpret results in the full signed range of -2N – 2N-1
- OF XOR SF functions as an extended sign-bit of an N-bit result
- similar how CF is used in unsigned comparison, OF XOR SF can provide the same function for signed comparison
The Extended Sign Bit: OF XOR SF
When OF=0 but the result is negative (SF=1) – or the result is positive (SF=0) but OF=1 are all negative results. OF is different from SF: OF XOR SF = 1. The exact opposite holds for overflowed or not overflowed positive results: OF XOR SF = 0.
Signed result in the full range of −2N – 2N-1
Following addition or subtraction, the N-bit adder provides signed results in the full range of −2N – 2N-1.
For example, on 8-bit (byte operand) this range is −256 – 255. Although the lowest negative value is −128 on 8-bits, it is still possible to compute let's say −64 + −112 = −176 correctly:
C0 -64
+ 90 -112
= 1 50
The addition overflows in signed two's complement: OF is set. SF=0 means overflow in the negative direction: making the two's complement of 50h = B0h (176). The result is −176.
The interpretation is similar to how an N-bit adder provides an unsigned N+1-bit result considering CY as an extra bit. In signed two's complement arithmetic, the OF XOR SF "bit" will be the sign bit and the magnitude is full range:
Unsigned interpretation following add/sub on N+1-bits range:
+---+---+---+---+---+---+---+---+
| . | . | . | . | . | . | . | . |
+---+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+
| . | . | . | . | . | . | . | . |
+/- +---+---+---+---+---+---+---+---+
_________________________________________
+---+---+---+---+---+---+---+---+---+
| . | . | . | . | . | . | . | . | . | 0 -- 2N+1-1
+---+---+---+---+---+---+---+---+---+
|
CY N-bit adder
Signed interpretation following add/sub on N+1-bits range:
+---+---+---+---+---+---+---+---+
| s | . | . | . | . | . | . | . |
+---+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+
| s | . | . | . | . | . | . | . |
+/- +---+---+---+---+---+---+---+---+
_________________________________________
+---+---+---+---+---+---+---+---+---+
| s | . | . | . | . | . | . | . | . | -2N -- 2N-1
+---+---+---+---+---+---+---+---+---+
|
OF XOR SF N-bit adder
Pseudo code to print out signed result following addition in the 2N range (same for subtraction). When OF XOR SF = 1, the adder stores a negative result. Make two's complement and print out as negative (only watch zero means the largest negative value, –2N):
y = a + b
if (OF XOR SF) /* neg? */
{
print '-'
y = -y
if (y == 0)
{
/* deal with largest negative */
}
}
print_unsigned(y)
The OF XOR SF "Flag"
OF XOR SF is so useful that it's worth implementing it in hardware, which requires only a single XOR gate:
•------------•--------
| •----------|-•------
_|_|__ _|_|__
| A B | | A B |
| C|_ | C|_
_|C' | \___|C' | \_
| |__Y___| ||__Y___|
| | | |
| •--------|---•-------
| | |
•----|----XOR-•
| | |
| •-XOR-•
| | | |
CF SF | OF
|
Extended Sign Bit
or the LESS "Flag"
Although it's not an official flag bit, on the x86, OF XOR SF can be directly tested by Jcc instructions:
JL - jump on less (OF XOR SF = 1) JNL - jump on not less (OF XOR SF = 0)
Worth noting, we have reached the peak functionality of our simple adder by adding only 2 XOR gates: now it's a fully-fledged signed-arithmetic-ready device!
OF XOR SF in signed comparison: the LESS "Flag"
What does it mean, for example, the x < 2 comparison?
Mathematically we say x < 2 when x - 2 < 0, i.e. the difference Δ of two numbers is negative.
Compare is subtraction. When subtraction is performed in the adder, OF XOR SF signals negative results in signed two's complement representation (either overflowed or not). Thus, OF XOR SF = 1 is exactly the LESS condition and can be used to implement signed comparison in hardware.
By adding a single XOR gate, the adder can detect the LESS condition between two arbitrary signed two's complement numbers.
SIGNED COMPARISON and the CMP instruction (Intel x86 Jcc)
Signed comparison is four types of logical relation (true or false condition) between two signed values:
GREATER
LESS OR EQUAL
+-----+ +-----+
| < | | >= |
+-----+ +-----+
+-----+ +-----+
| <= | | > |
+-----+ +-----+
LESS GREATER
OR EQUAL
These terms "greater" and "less" are the same and are used by Intel processors. Greater means a more positive signed value. Less means a less positive (i.e. more negative) signed value.
The CMP (Compare) instruction subtracts the source from the destination. The operands are unchanged, but the flags are updated.
CMP A, B ← is equivalent to:
SUB A, B ← is equivalent to:
A – B
We saw earlier how OF XOR SF is the LESS condition. Implementing other logical relation conditions in hardware can be derived from LESS using a few logic gates:
- the negated condition will be greater or equal (>=), that is NOT LESS
- less or equal (<=) is LESS or the result is zero and the Zero flag is set: LESS OR ZF
- greater (>) is the negated condition of less or equal: NOT(LESS OR ZF)
GREATER
LESS OR EQUAL
+-----+ +-----+
OF XOR SF --+--------> | < | --- NOT ---> | >= |
| +-----+ +-----+
|
| +-----+ +-----+
ZF ----OR-------> | <= | --- NOT ---> | > |
+-----+ +-----+
LESS GREATER
OR EQUAL
Just for completeness, unsigned comparison is very similar, but it is based on the carry flag:
BELOW
BELOW OR EQUAL
+-----+ +-----+
CF --+--------> | < | --- NOT ---> | >= |
| +-----+ +-----+
|
| +-----+ +-----+
ZF ----OR-------> | <= | --- NOT ---> | > |
+-----+ +-----+
ABOVE ABOVE
OR EQUAL
Testing for underflow following subtraction of two signed values in this sense becomes very similar to unsigned underflow:
0
..............|....................
<--------------------
CF = 1 SUB unsigned
LESS = 1 SUB signed
And this is exactly how the eight x86 Jcc instruction opcodes work LINK (details here):
UNSIGNED POS COND UNSIGNED NEG COND OPCODE FLAGS CONDITION B Below NAE Neither above nor equal 0010 CF = 1 AE Above or equal NB Not below 0011 CF = 0 BE Below or equal NA Not above 0110 CF or ZF = 1 A Above NBE Neither below nor equal 0111 CF or ZF = 0 SIGNED POS COND SIGNED NEG COND OPCODE FLAGS CONDITION L Less NGE Neither greater nor equal 1100 LESS = 1 GE Greater or equal NL Not less 1101 LESS = 0 LE Less or equal NG Not greater 1110 LESS or ZF = 1 G Greater NLE Neither less nor equal 1111 LESS or ZF = 0