--------------------------------------------------
Calculating the OVERFLOW flag in binary arithmetic
--------------------------------------------------
- Ian! D. Allen - idallen@idallen.ca - www.idallen.com

Do not confuse "carry" with "overflow".

If you treat the bits in a word as "unsigned" numbers, you must watch
to see if your arithmetic causes a "carry", indicating the result is
wrong.  You don't care about the overflow flag when doing unsigned math.
(The overflow flag is only relevant to signed numbers, not unsigned.)

If you treat the bits in a word as "two's complement" signed values, you
must watch to see if your arithmetic causes an "overflow", indicating the
result is wrong.  You don't care about the carry flag when doing signed,
two's complement math.  (The carry flag is only relevant to unsigned
numbers, not signed.)

The rules for detecting overflow in a two's complement sum are these:

In two's complement arithmetic, the overflow flag is set if the answer
is wrong - you added two positive numbers and got a negative, or you
added two negative numbers and got a positive.

1. If the sum of two positive numbers yields a negative result, the sum
   has overflowed, the "overflow" flag is turned on.
2. If the sum of two negative numbers yields a positive result, the sum
   has overflowed, the "overflow" flag is turned on.

Otherwise, the sum has not overflowed. It is important to note the
overflow and carry out can each occur without the other. In unsigned
numbers, carry out is equivalent to overflow. In twos compliment, carry
out tells you nothing about overflow.

The rules for "overflow" detect this error by examining the sign of
the result. A negative and positive added together cannot overflow,
because the sum is between the addends. Since both of the addends fit
within the allowable range of numbers, and their sum is between them,
it must fit as well.

There are several automated ways of detecting overflow in two's complement
binary arithmetic (for those of you who don't like the manual inspection
method).  Here are two.

========
Method 1
========

Overflow can only happen when "adding" two numbers of the same sign and
getting a different sign.  So, to detect overflow we don't care about
any bits except the sign bits.  Ignore the other bits.

With two operands and one result, we have three sign bits (each 1 or 0)
and one operation to consider.  The operation is either ADD or SUBTRACT;
so, we have only 2**4=16 possible combinations of the three bits and
the operation.  Only four of those 16 possible cases are considered
overflow, and two of those are simple variations of the other two:

Below are just the sign bits of the two operands and result:
        0+0=0
 *OVER* 0+0=1 (adding two positives should be positive)
        0+1=0
        0+1=1
        0-0=0
        0-0=1
        0-1=0
 *OVER* 0-1=1 (subtracting a negative is the same as adding a positive)
        1+0=0
        1+0=1
 *OVER* 1+1=0 (adding two negatives should be negative)
        1+1=1
 *OVER* 1-0=0 (subtracting a positive is the same as adding a negative)
        1-0=1
        1-1=0
        1-1=1

There are 12 combinations of sign bits above that are not overflow.
A computer might contain a small logic gate array that sets the overflow
flag to "1" iff any one of the above four OV conditions is met.

A human need only remember that adding two numbers of the same sign
must produce a result of the same sign, otherwise overflow happened.

========
Method 2
========

When adding two binary values, consider the binary carry coming into
the leftmost place (into the sign bit) and the binary carry going out
of that leftmost place.  (Carry going out of the leftmost [sign] bit
becomes the CARRY flag in the ALU.)

The reason for the rules is that overflow in two's complement may occur,
not when a bit is carried out out of the left column, but when one is
carried into it and no matching carry occurs. That is, when there is
a carry into the sign bit but no carry out of the sign bit.

The OVERFLOW flag is the XOR of the carry coming into the sign bit (if
any) with the carry going out of the sign bit (if any).  Overflow happens
if the carry in does not equal the carry out.

Examples (2-bit signed 2's complement binary numbers):

    11
   +01
   ===
    00

   - carry in is 1
   - carry out is 1
   - 1 XOR 1 = NO OVERFLOW


    01
   +01
   ===
    10

   - carry in is 1
   - carry out is 0
   - 1 XOR 0 = OVERFLOW!


    11
   +10
   ===
    01

   - carry in is 0
   - carry out is 1
   - 0 XOR 1 = OVERFLOW!


    10
   +01
   ===
    11

   - carry in is 0
   - carry out is 0
   - 0 XOR 0 = NO OVERFLOW

Note that this XOR method only works with the *binary* carry that goes
into the sign *bit*.  If you are working with hexadecimal numbers, or
decimal numbers, or octal numbers, you also have carry; but, the carry
doesn't go into the sign *bit* and you can't XOR that non-binary carry
with the outgoing carry.

Hexadecimal addition example (showing that XOR doesn't work for hex carry):

    8Ah
   +8Ah
   ====
    14h

   The hexadecimal carry of 1 resulting from A+A does not affect the
   sign bit.  If you do the math in binary, you'll see that there is
   *no* carry *into* the sign bit; but, there is carry out of the sign
   bit.  Therefore, the above example sets OVERFLOW on.  (The example
   adds two negative numbers and gets a positive number.)