Overflow/underflow in unsigned numbers

Question

So, if you have a carry out of 1 on addition with unsigned numbers, you have overflowed, and if you have a carry out of 0 with subtraction, you have underflowed. Does this work in every case, though?

If you do 5-0: 0101 -0000

= 0101 +(1111 + 1)

= 0101 +0000

= 0101... there is a carry out of zero here, instead of 1. How does one account for this case? Is there a different way to do it?

(using MIPS architecture, or anything else)

---Edit

Thanks Amadan. I understand that part, though. My problem is just that zero seems to be a special case. It does not seem to follow what normal numbers do: in my example above, there is no carry out of 1.

I'm doing circuit design working with an ALU at the moment and trying to implement the overflow detection, when this one case came up that doesn't follow what the others do.

We are assuming that with subtraction, the second operand is preinverted (twos complement) before going into the ALU (then added to the first operand). So, whenever the "invert_b" for subtraction is set to 1, b is inverted and we assume that the case we are checking for is subtraction, which should have a carry out of 1.

Solution 1

I believe the msbit carry out bit on its own covers unsigned and for signed you look to see if the carry in to the msbit and the carry out differ.

5-0 does not overflow because the result fits in the number of bits available. The same way that 15-1 does not overflow a 4 bit system for signed numbers

5 - 0 = 0101 + 1111 + 1

    1
 0101
+1111
=====

11111
 0101
+1111
=====
 0101

so 5 - 0 certainly carries out a 1, since this is a subtract that is not an overflow

15 - 1 = 1111 + ~1 with the carry in set

    1
 1111
 1110
 ====

11111
 1111
 1110
 ====
 1110

a subtract with a 1 out is not an unsigned overflow as you stated

Likewise -1 - 1 = 1111 + ~1 with the carry in bit set

11111
 1111
 1110
 ====
 1110

the carry in to the last bit is a 1 the carry out is a 1 they match, no signed overflow.

8 + 8 = 1000 + 1000 with the carry in clear

    0
 1000
+1000
=====

10000
 1000
+1000
=====
 0000

unsigned overflow.

hmmm 4 + 4

    0
 0100
+0100
=====

01000
 0100
+0100
=====
 1000

unsigned add the carry out is 0 this is not an unsigned overflow. but this is a signed overflow because the carry in to the msbit and carry out differ. +4 + +4 = +8, in a 4 bit signed system you cannot represent +8, so the signed overflow is accurate.

No matter how many bits the weird numbers are all zeros and a one and the rest zeros, 0 and 8 or -8 for a 4 bit system.

Make a chart either with 2, 3, or 4 bit numbers all combinations and manually look through all of them to see that they make sense. whatever you find will scale no matter how many bits wide, a 100 bit adder works like a 10 bit adder...

add           C V  unsigned    signed
00 + 00 = 000 0 0  0 + 0 = 0   0 +  0 =  0
00 + 01 = 001 0 0  0 + 1 = 1   0 +  1 =  1
00 + 10 = 010 0 0  0 + 2 = 2   0 + -2 = -2
00 + 11 = 011 0 0  0 + 3 = 3   0 + -1 = -1
01 + 00 = 001 0 0  1 + 0 = 1   1 +  0 =  1
01 + 01 = 010 0 1  1 + 1 = 2   1 +  1 =  2  signed cannot represent a +2
01 + 10 = 011 0 0  1 + 2 = 3   1 + -2 = -1
01 + 11 = 100 1 0  1 + 3 = 4   1 + -1 =  0  unsigned cannot represent +4
10 + 00 = 010 0 0  2 + 0 = 2  -2 +  0 = -2 
10 + 01 = 011 0 0  2 + 1 = 3  -2 +  1 = -1
10 + 10 = 100 1 1  2 + 2 = 4  -2 + -2 = -4 neither +4 nor -4 will fit in 2 bits
10 + 11 = 101 1 1  2 + 3 = 5  -2 + -1 = -3 neither +4 nor -3 will fit in 2 bits
11 + 00 = 011 0 0  3 + 0 = 3  -1 +  0 = -1 
11 + 01 = 100 1 0  3 + 1 = 4  -1 +  1 = -2 +4 does not fit in 2 bits
11 + 10 = 101 1 1  3 + 2 = 5  -1 + -2 = -3 neither +5 nor -3 fit in 2 bits
11 + 11 = 110 1 0  3 + 3 = 6  -1 + -1 = -2 6 does not fit in 2 bits
sub
00 - 00 = 100 0 0
00 - 01 = 011 1 0  0 - 1 = -1   -1 does not fit in an unsigned result
00 - 10 = 010 1 1  0 - 2 = -2  0 - -2 = +2  
00 - 11 = 001 1 0  0 - 3 = -3
01 - 00 = 101 0 0
01 - 01 = 100 0 0
01 - 10 = 011 1 1  1 - 2 = -1  1 - -2 =  3
01 - 11 = 010 1 1  1 - 3 = -2  1 - -1 =  2
10 - 00 = 110 0 0  
10 - 01 = 101 0 1             -2 -  1 = -3
10 - 10 = 100 0 0
10 - 11 = 011 1 0  2 - 3 = -1
11 - 00 = 111 0 0
11 - 01 = 110 0 0
11 - 10 = 101 0 0
11 - 11 = 100 0 0

The code that generated the above

printf("add\n");
for(ra=0;ra<4;ra++)
{
    for(rb=0;rb<4;rb++)
    {
        rd=(ra&1)+(rb&1);
        rc=ra+rb;
        rd=(rd>>1)&1;
        re=(rc>>2)&1;
        if(re) c=1; else c=0;
        if(rd!=re) v=1; else v=0;

        if(ra&2) printf("1"); else printf("0");
        if(ra&1) printf("1"); else printf("0");
        printf(" + ");
        if(rb&2) printf("1"); else printf("0");
        if(rb&1) printf("1"); else printf("0");
        printf(" = ");
        if(rc&4) printf("1"); else printf("0");
        if(rc&2) printf("1"); else printf("0");
        if(rc&1) printf("1"); else printf("0");
        printf(" %u %u\n",c,v);
    }
}
printf("sub\n");
for(ra=0;ra<4;ra++)
{
    for(rb=0;rb<4;rb++)
    {
        rd=(ra&1)+((~rb)&1)+1;
        rc=ra+((~rb)&3)+1;
        rd=(rd>>1)&1;
        re=(rc>>2)&1;
        if(re) c=0; else c=1;
        if(rd!=re) v=1; else v=0;

        if(ra&2) printf("1"); else printf("0");
        if(ra&1) printf("1"); else printf("0");
        printf(" - ");
        if(rb&2) printf("1"); else printf("0");
        if(rb&1) printf("1"); else printf("0");
        printf(" = ");
        if(rc&4) printf("1"); else printf("0");
        if(rc&2) printf("1"); else printf("0");
        if(rc&1) printf("1"); else printf("0");
        printf(" %u %u\n",c,v);
    }
}

Now your question was talking about unsigned numbers yes? so you may not care about the V bit nor the right half, the signed half.

Here is some HDL/RTL for a small 16 bit processor I implemented:

case 4b0000:
{
    //0000 add rd,rs
    op_a = bundle(1b0,reg[bundle(2b0,inst[4;8])].value);
    op_b = bundle(1b0,reg[bundle(2b0,inst[4;4])].value);
    op_res = op_a + op_b;
    reg[1].value[CBIT] <= op_res[16];
    reg[1].value[NBIT] <= op_res[15];

    if(op_res[16;0] == 16h0000)
    {
        reg[1].value[ZBIT] <= 1b1;
    }
    else
    {
        reg[1].value[ZBIT] <= 1b0;
    }
    if((op_a[15] == op_b[15]) && (op_res[15] != op_b[15] ) )
    {
        reg[1].value[VBIT] <= 1b1;
    }
    else
    {
            reg[1].value[VBIT] <= 1b0;
    }
    reg[bundle(2b0,inst[4;8])].value <= op_res[16;0];
}
case 4b0001:
{
    //0001 sub rd,rs
    op_a = bundle(1b0,reg[bundle(2b0,inst[4;8])].value);
    op_b = bundle(1b0,reg[bundle(2b0,inst[4;4])].value);
    op_res = op_a - op_b;
    reg[1].value[CBIT] <= (~op_res[16]);
    reg[1].value[NBIT] <= op_res[15];

    if(op_res[16;0] == 16h0000)
    {
        reg[1].value[ZBIT] <= 1b1;
    }
    else
    {
        reg[1].value[ZBIT] <= 1b0;
    }
    if((op_a[15] != op_b[15]) && (op_res[15] == op_b[15] ) )
    {
        reg[1].value[VBIT] <= 1b1;
    }
    else
    {
        reg[1].value[VBIT] <= 1b0;
    }
    reg[bundle(2b0,inst[4;8])].value <= op_res[16;0];
}

I have/had seen the msbit thing for signed overflow in other logic and couldnt find a case where it didnt match the carry in vs carry out method when trying every possible combination in a head to head analysis.

If I went overboard with the answer I dont mind clipping it off at the beginning where it shows that 5 - 0 has a 1 as a carry out of 1, which for a subtract is not an overflow. The long answer because it can be hard to wrap your head around signed vs unsigned and how the adder works in logic in general. The adder does not know or care about signed or unsigned, it does care about add vs subtract, with subtract you invert the second operand, invert the carry in to the lsbit and the carry out of the msbit (think about add, add with carry, sub and sub with carry). The signed vs unsigned takes care if itself (the beauty of twos complement). Reducing the above to an unsigned only discussion makes it more than half as simple as the signed overflow is not (as) obvious (as unsigned overflow) to the casual observer.

I sure hope I cut and pasted the debugged HDL , will get a lot of responses/corrections if I didnt...I spent a few days convincing myself of all of the above and comparing to the results of other processors I had access to, etc. Hopefully this saves you a few days.

Solution 2

Not an expert, but the whole statement on subtraction seems wrong.

You can implement subtraction in two basic ways: directly as subtraction, or as addition of two's complement.

If you go with two's complement addition, then it is as you say: carry of 1 is underflow.

5 - 6
= 0101 - 0110
= 0101 + (1001 + 1)
= 0101 + 1010
= (0)1111, carry 0 = underflow

If you subtract directly, then 1 carry is underflow:

0101 - 0110:
0     to    1 is 1
1     to (1)0 is 1, carry 1
1 + 1 to (1)1 is 1, carry 1
0 + 1 to (1)0 is 1, carry 1 = underflow