Overflow in bitwise subtraction using two's complement

Question

When performing bitwise subtraction using two's complement, how does one know when the overflow should be ignored? Several websites I read stated that the overflow is simply ignored, but that does not always work -- the overflow is necessary for problems like -35 - 37, as an extra digit is needed to express the answer of -72.

EDIT: Here's an example, using the above equation.

35 to binary -> 100011, find two's complement to make it negative: 011101

37 to binary -> 100101, find two's complement to make it negative: 011011

Perform addition of above terms (binary equivalent of -35 - 37):

011101
011011
------
111000

Take two's complement to convert back to positive: 001000

The above is what many websites (including academic ones) say the answer should be, as you ignore overflow. This is clearly incorrect, however.

Answer 1

An overflow happens when the result cannot be represented in the target data type. The value -72 can be represented in a char, which is a signed 8-bit quantity... there is no overflow in your example. Perhaps you are thinking about a borrow while doing bitwise subtraction... when you subtract a '1' from a '0' you need to borrow from the next higher order bit position. You cannot ignore borrows when doing subtraction.

-35 decimal is   11011101 in two's complement 8-bit
+37 decimal is   00100101 in two's complement 8-bit

going right to left from least significant to most significant bit you can subtract each bit in +37 from each bit in -35 until you get to bit 5 (counting starts at bit 0 on the right). At bit position 5 you need to subtract '1' from '0' so you need to borrow from bit position 6 (the next higher order bit) in -35, which happens to be a '1' prior to the borrow. The result looks like this

-35 decimal is   11011101 in two's complement 8-bit
+37 decimal is   00100101 in two's complement 8-bit
                 --------
-72 decimal is   10111000 in two's complement 8-bit

The result is negative, and your result in 8-bit two's complement has the high order bit set (bit 7)... which is negative, so there is no overflow.

Update:I think I see where the confusion is, and I claim that the answer here Adding and subtracting two's complement is wrong when it says you can discard the carry (indicates overflow). In that answer they do subtraction by converting the second operand to negative using two's complement and then adding. That's fine - but a carry doesn't represent overflow in that case. If you add two positive numbers in N bits (numbered 0 to N-1) and you consider this unsigned arithmetic range 0 to (2^N)-1 and you get a carry out of bit position N-1 then you have overflow - the sum of two positive numbers (interpreted as unsigned to maximize the range of representable positive numbers) should not generate a carry out of the highest order bit (bit N-1). So when adding two positive numbers you identify overflow by saying

1. there must be no carry out of bit N-1 when you interpret them as unsigned and
2. the result in bit N-1 must be zero when interpreted as signed (two's complement)

Note, however, that processors don't distinguish between signed and unsigned addition/subtraction... they set the overflow flag to indicate that if you are interpreting your data as signed then the result could not be represented (is wrong).

Here is a very detailed explanation of carry and overflow flag. The takeaway from that article is this

• In unsigned arithmetic, watch the carry flag to detect errors.

• In unsigned arithmetic, the overflow flag tells you nothing interesting.

• In signed arithmetic, watch the overflow flag to detect errors.

• In signed arithmetic, the carry flag tells you nothing interesting.

This is consistent with the definition of arithmetic overflow in Wikipedia which says

Most computers distinguish between two kinds of overflow conditions. A carry occurs when the result of an addition or subtraction, considering the operands and result as unsigned numbers, does not fit in the result. Therefore, it is useful to check the carry flag after adding or subtracting numbers that are interpreted as unsigned values. An overflow proper occurs when the result does not have the sign that one would predict from the signs of the operands (e.g. a negative result when adding two positive numbers). Therefore, it is useful to check the overflow flag after adding or subtracting numbers that are represented in two's complement form (i.e. they are considered signed numbers).