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

There are several ways of detecting overflow in binary arithmetic.
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:

  (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

The remaining 12 combinations of sign bits 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 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 sign bit becomes
the CARRY flag.)

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).

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.)