Search code examples
binaryoverflowundertow

Underflow and Overflow in binary addition

In the case of:

0b10001111+0b10011000 = 0b100100111

Is a case of underflow? as the two term are negative and the result it positive?

When will we get an overflow? as the 9th bit will be always 1? when both of the 8th bits are 1

Solution

  • 0b1000 1111+0b1001 1000 = 0b1 0010 0111

    Including the carry as n+1th bit of result in meaningless for 2s complement. What you can do is either to stick on the original size

    0b1000 1111+0b1001 1000 = 0b0010 0111 // invalid

    or extend operands to n+1 bits and get a n+1 bits result.

    0b1 1000 1111+0b1 1001 1000 = 0b1 0010 0111 //valid

    The reason is that 2s complement works by adding 2^n to negative integers to make them positive. (to code a<0=-|a|, use 2^n+a or 2^n -|a|, ie the complement to 2^n of |a|, hence the name of 2s complement).

    This is great, as the coded value is (2^n)+a if a<0 or a if a≥0, and if you ignore 2^n, you can do signed integer addition without worrying on the sign of operands. But you must ignore the carry out (except for what concerns validity).

    To get the precise validity rules, you must consider the different situations:

    1/A,B>=0

    enter image description here

    Result is valid iff MSB=0 ⇒ c_n-1=0 (and we always have c_n=0)

    2/ A,B<0

    enter image description here

    Result is valid iff MSB=1 ⇒ c_n-1=1 (and we always have c_n=1)

    3/ A>=0, B<0

    enter image description here

    Result cannot be too positive or too negative and is always valid. And we always have c_n=c_n-1

    We can see that the global rule that indicates if a result is valid is that c_n==c_n-1 (or c_n ⊕ c_n-1 indicates overflow).

    There are many other equivalent rules. For instance:
    result is valid if (sign(A) != sign(B)) or ((sign (A) == sign(B)) and (sign(A)==sign(A+B))
    which can be expressed in C as
    ((a^b) | (a^~(a+b)))&(1<< sizeof (int) -1)