How does an adder perform unsigned integer subtraction?

Question

Suppose that A and B are signed positive integers, then for A-B, it's calculated using A+2's complement of B.

For example, in a 4-bit binary system, for signed integers, we have 7-3=0111-0011=0111+1101=(1)0100, the 1 in the bracket is the carry bit. According to the overflow rule for signed integer, we know there is no overflow and the result is therefore correct.

However, for unsigned integers, what will happen if we calculate 7-3? If we use the same way we mentioned above:

7-3=0111-0011=0111+1101=(1)0100

then, according to the overflow rule for unsigned integers, there is an overflow because of the carry out. In another word, 0100 is wrong because there is an overflow. But in fact, we know the result 0100 is correct.

If my analysis is correct, isn't it wrong to use adder to perform unsigned integer subtraction?

Zig

The interpretation of the carry-out changes for subtraction. – Beckiebeckley

@harold: Exactly, but only at unsigned subtraction inplemented with complement and add. – Francophobe

Answer 1

In this answer to a related question there's sample code in C that shows how to do subtraction via addition. The code sets the carry and overflow flags as well and contains a simple "test" that adds and subtracts a few numbers and prints the results. The numbers are 8-bit.

EDIT: Formal proof that one can use ADD instead of SUB for unsigned integers AND spot unsigned overflow/underflow as if from SUB.

Let's say we want to calculate a - b, where a and b are 4-bit unsigned integers and we want to perform subtraction via addition and get a 4-bit difference and an underflow/overflow indication when a < b.

a - b = a + (-b)
Since we're operating in modulo-16 arithmetic, -b = 16-b. So,
a - b = a + (-b) = a + (16 - b)

If we perform regular unsigned addition of a and 16-b the overflow condition for this addition, which is often indicated by the CPU in its carry flag, will be this (recall that we're dealing with 4-bit integers):

a + (16 - b) > 15
Let's simplify this overflow condition:
a + 16 - b > 15
a + 16 > 15 + b
a + 1 > b
a > b - 1

Let's now recall that we're dealing with integers. Therefore the above can be rewritten as:
a >= b.
This is the condition for getting carry flag = 1 after adding a and (16)-b. If the inequality doesn't hold, we get carry = 0.

Let's now recall that we were interested in overflow/underflow from subtraction (a - b). That condition is a < b.

Well, a >= b is the exact opposite of a < b.

From this it follows that the carry flag that you get from adding a and (16)-b is the inverse of the subtraction overflow, or, in other words, the inverse of the borrow flag you'd get by subtracting b directly from a using the appropriate subtraction instruction (e.g. SUB).

Just invert the carry or treat it in the opposite way.

Erminiaerminie

@GJ.: it's not wrong to use an adder for subtraction. My code shows it. You can inspect the test output to see it. – Erminiaerminie

Not true, this is normal under low level so in assembly, but you must to know rules! Check my explanation! – Francophobe

@GJ.: I've updated my answer with a formal proof that you can use the carry flag after the addition to see whether or not there's an overflow/underflow in the subtraction. You only need to invert the carry flag after ADD to get what you'd get in it after SUB. – Erminiaerminie

Exactly, and question was why is so! – Francophobe

@Alex, thank you. Your answer is easier to understand than GJ.'s :) – Zig

I'm pretty tired and I might be missing something else, but it appears to be incorrect for b = 0 because of the unsigned underflow of b-1. – Amyamyas

@Amyamyas I agree that this explanation fails to treat b = 0 properly. However, the Sbb() function in the linked answer of mine to a different question takes care of it. IOW, the function adds to a 256 (as 255+carry=1) instead of adding 256 AND 255 (0), which always results in the carry flag set after addition. And then the flag is inverted. Hence, adding 0 or subtracting 0 via addition gives carry = 0, no unsigned overflow. – Erminiaerminie

Answer 2

Your analysis is not correct. Actually is CPU ALU unit dependent. :)

In first case you are using 4 bit integer but you forgotten that the highest bit of 4 bit sign integer is sign! So you are checking only the Carry and Overflow status and not also Negative status bit.

In generally binary arithmetic operations add and sub are the same for signed integers and unsigned integers. Only affected flags are different.

Actually you must consider:

• at signed integer arithmetic Carry, Overflow and Negative flags.
• at unsigned integer arithmetic only Carry flags.

Detail explanation:

The mining of complement function is negation, so to get opposite negative number from positive and positive from negative. We can make binary complement on two ways. Lets see both cases for number 3.

1. At unsigned arithmetic is compl (3) = b'0011' xor b'1111' + b'0001' = b'1101' + Carry (Carry is set only at compl (0))
2. At signed arithmetic numbers is comply (3) = b'10000' - b'0011' = b'1101' what is equal b'0000' - b'0011' = b'1101' + Carry (Carry is clear only at compl (0))

In first case function complement also complement the carry bit and we have also the second interpretation of carry flag named borrow.

In second case everything is clear. If we have got carry (overflow) at complement that mean that we need another overflow to normalize the result of subtraction.

Francophobe

That is a great answer! It is often forgotten that unsigned arithmetic only raises carry flag! In addition I think that one has to know that two's-complement takes care of all problems including the sign bit! – Highbred

Hi GJ, thank you. In first case both 7 and 3 are signed integers, so there is no problem with 7-3=4. However, for the 2nd case where 7 and 3 are unsigned integers, as you said we must consider only Carry flags, then 7-3=0111-0011=0111+1101=(1)0100 does generate a carry bit, which means the calculation does overflow. In another word, we get the correct result 4, however, because there is a carry bit for the unsigned arithmetic, it makes us think that the correct result 4 is wrong because of the overflow caused by the carry bit. How to explain this? – Zig

@user1035882: Short answer is: because at unsigned complement the carry flag is also complemented. I have added detal explanation. – Francophobe

@GJ.:Thank you so much. Your answer is a little difficult for me:) I have to take some time to fully understand it. – Zig

Answer 3

This is a bit hard to understand but... I had some VHDL where I did this. I had a CPU with a memory location that was unsigned and an offset value that was signed.

architecture Behavioral of adder16 is
signal temp: std_logic_vector (16 downto 0);
begin
eval: process(vectA,vectB,temp)
begin
temp <=(('0'& vectB)  + (vectA(15) & vectA));
output <= temp( 15 downto 0);
end process;
end Behavioral;

Pulsate

Answer 4

Your analysis is correct.

Use

OVERFLOW = EXOR ( CARRY OUT , ADD'/SUB )

to determine overflow for both unsigned addition and unsigned subtraction( using 2's Complement addition ) for single interpretation.

In unsigned addition overflow is indicated by

CARRY OUT = 1

Correct result is indicated by

CARRY OUT = 0

But

ADD'/SUB = 0

is for addition

So anyway overflow is indicated by 1.

Similarly

In unsigned subtraction overflow is indicated by

CARRY OUT = 0

Correct result is indicated by

CARRY OUT = 1

But

ADD'/SUB = 1

is for subtraction

So anyway overflow is indicated by 1.

Thus we can have single interpretation for overflow in both unsigned addition and unsigned subtraction.

Ocko